CODE FESTIVAL 2015 あさプロ Middle D - 立方体とペンキ

解法

正面から見た面積と、上から見た面積は簡単に求まる。問題になるのは横方向の表面積。

まず、横方向の表面積は隣合う2つのブロックの高さの絶対値の総和になっていることがわかる。とりあえず絶対値の最小化として問題を見ることにする。

高さだけを抽出して折れ線グラフを作ってみた。これはA=[8,8,4,9,6,4]の場合を表している。適当な点を下げてみたときの絶対値の変化を調べてみると、極大になっている点以外を動かしても絶対値は変化しないか増加するだけであることがわかる。そのため極大になっている点を下げていけばいい。
f:id:pekempey:20151115143329p:plain

2つ以上並んでいると極大が考えにくい。そこで高さをランレングス圧縮してみた。図には点の上に連続している点の数を書いてある。連続している点の数をこれからは重みと呼ぶことにする。
f:id:pekempey:20151115143639p:plain

さて極大点が2つあるが、どちらを下げるのが最適だろうか。重み2の点の高さを1下げるというのは、2つのブロックの高さを同時に1下げるということを意味している。つまり重ければ重いほど点を下げるのにコストが掛かる。高さを1下げたときの絶対値の減少量は重みによらず2なので、重みが小さい極大点を下げるのが最適となる。

f:id:pekempey:20151115144708p:plain

右側の点の高さまで下げる。同じ高さになったので点をひとつにまとめておいた。次の候補はどちらも重みが2だからどっちを選んでも最適。左上に書いてあるのは操作回数。

f:id:pekempey:20151115144934p:plain

f:id:pekempey:20151115145016p:plain
左も右も同じ高さになったので、両方とも一点にまとめた。

f:id:pekempey:20151115145023p:plain
K=27だと思って操作をやめた。

操作を行うごとに点の数が少なくとも1つ減るので操作の回数は高々n回。極大点の候補選びにpriority queueを使えばO(nlogn)でできる。点をまとめるという操作は双方向リストの要領で頑張る。

ソースコード

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;
 
template<class S, class T>
vector<pair<S, int>> rle(T first, T last) {
    vector<pair<S, int>> res;
    T seek = first;
    while (seek != last) {
        T start = seek;
        int cnt = 0;
        while (seek != last && *seek == *start) seek++, cnt++;
        res.emplace_back(*start, cnt);
    }
    return res;
}
 
typedef pair<ll, int> P;
ll a[101010], w[101010], l[101010], r[101010];
 
int main() {
    ll n, k;
    cin >> n >> k;
    rep (i, n) scanf("%lld", &a[i + 1]);
    ll S = n;
    n += 2;
    rep (i, n - 1) S += abs(a[i + 1] - a[i]);
    rep (i, n) S += a[i] * 2;
    S -= k * 2;
 
    auto enc = rle<ll>(a, a + n);
    n = enc.size();
    rep (i, n) tie(a[i], w[i]) = enc[i];
 
    rep (i, n) {
        l[i] = i - 1;
        r[i] = i + 1;
    }
 
    priority_queue<P, vector<P>, greater<P>> q;
    rep (i, n - 2) {
        if (a[i] < a[i + 1] && a[i + 1] > a[i + 2]) {
            q.emplace(w[i + 1], i + 1);
        }
    }
 
    while (!q.empty() && k > 0) {
        int i = q.top().second; q.pop();
        ll dist = min(a[i] - max(a[l[i]], a[r[i]]), k / w[i]);
        a[i] -= dist;
        k -= dist * w[i];
        S -= dist * 2;
        if (a[l[i]] == a[i]) {
            w[i] += w[l[i]];
            l[i] = l[l[i]];
            r[l[i]] = i;
        }
        if (a[r[i]] == a[i]) {
            w[i] += w[r[i]];
            r[i] = r[r[i]];
            l[r[i]] = i;
        }
        if (a[l[i]] < a[i] && a[i] > a[r[i]] && k >= w[i]) {
            q.emplace(w[i], i);
        }
    }
    cout << S << endl;
    return 0;
}

感想

注意力が必要な実装は朝やるときつい。