mayoko’s diary

プロコンとかいろいろ。

CODE FESTIVAL 2015 あさぷろ Middle C - 一次元オセロ

あさプロの時はものすごく混乱してて結局解けなかったんだけど, 今やったらめっちゃあっさりだった。

解法

N は奇数なので, 最後にすべてのコマが同じ色になる時コマは絶対に白色になっています。よって, 例えば右側を 1 回裏返して黒色にした場合はもう一回裏返して 白色にする必要があるわけです。

ということで, 結局この問題は「合計で N/2 回, 左or右から黒で裏返す->白で裏返す という作業をやるので, 裏返す回数を最小化しよう」という問題になります。これは貪欲法でやれば良いです。つまり, 左側から裏返す場合の回数と右側から裏返す場合の回数を計算して, 少ない方を貪欲に選ぶということを繰り返せば良いです。

と, ここまではいいんですが, 裏返す回数を計算するのがなんか混乱したんですよね。
絵を書くと簡単です。今までに左側で裏返すことで白色になったコマの枚数を L として, 裏返す枚数を考えると, 下図のようになりますよね…
f:id:mayokoex:20151126233917j:plain
で, これを裏返したら, 「今までに左側で裏返すことで白色になったコマの枚数」は, L+a+b+2(2 は, 黒->白 と裏返すことで出来た石の個数)になりますよね。ということでこれで計算しましょう。

const int MAXN = 100010;
ll A[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    ll L = 0, R = 0;
    int l = 0, r = N-1;
    ll ans = 0;
    for (int t = 0; t < N/2; t++) {
        ll ln = 2*L+2*A[l]+A[l+1]+1;
        ll rn = 2*R+2*A[r]+A[r-1]+1;
        if (ln < rn) {
            ans += ln;
            L += A[l]+A[l+1]+2;
            l += 2;
        } else {
            ans += rn;
            R += A[r]+A[r-1]+2;
            r -= 2;
        }
    }
    cout << ans << endl;
    return 0;
}