http://agc011.contest.atcoder.jp/tasks/agc011_d

問題概要

左右からボールを入れられるN個の装置が横一直線に並んでいる。装置は状態Aか状態Bのどちらかである。状態Aの装置にボールが入ってくると、入ってきた方向にボールを跳ね返し状態Bに変化する。状態Bの装置にボールが入ってくるとそのまま逆側からボールを排出し状態Aに変化する。各装置の初期状態が与えられるので、一番左の装置の左側からボールを入れるという操作をK回繰り返した後の各装置の状態を求めよ。

N <= 2×10⁵, K <= 10⁹

解法

小さいNで実験してみると、ボールを一回入れるごとに以下のような規則的な変化をすることがわかる（わからない）。

先頭の装置がAの場合、先頭の装置がBに変わるだけ (AABBBAB -> BABBBAB)
先頭の装置がBの場合、全部の装置の状態が反転して左にひとつシフトした形になる。先頭のBは末尾に回ってAになる (BABBBAB -> BAAABAA)

後者のパターンで変化が起きるとき最後尾にくっつくのは必ずAになるので、十分に長いKをとると最終的にはBABABABABA...のような互い違いの形に収まる。この形になると、Nが偶数の場合必ずBが先頭に来るのでBABABAの形で一切変化が起こらなくなる。Nが奇数の場合はAが一度先頭に来るので ABABAB -> BBABAB -> ABABAB -> ,,, のように先頭のABだけが切り替わりつづける振動状態になる。

あとはこの規則をシミュレートしていけばいい。いま先頭がどこかと反転状態はどうかだけ持っておけばO(N)でできる。列を舐めきってもKが余っていたらあとは上の最終パターンにはまるのでNの偶奇によってよしなにやる。

解法は以上だが一応こうなる理屈を（公式解説を見て）考えてみる。変化が起きるのは先頭がBのときだけなので、このパターンだけを考える。先頭2つがBAのときボールが左から入ると、oBA -> AoA -> AoB -> BoB -> BAo という変化でボールは右へ出ていく。次に先頭2つがBBのときは oBB -> AoB -> AAo という変化でやはりボールは右へ出ていく。つまり右がAのときは一回ボールが跳ね返ってくるので左は元のBに戻り、右がBのときはボールが戻ってこないので左は一回反転したAのままになる（＝左の装置は右の装置の反対の状態になる）。右へ出ていく直前、右の装置は必ずBの状態を取っているので、以降のすべての隣接2要素においてもまったく同様の変化が発生する。つまりボールが2マス以上戻ってくることはなく、必ず右に送られていくことになる。そして最後に右から出ていくとき右の装置は必ずAになっているので、先頭のBがcyclicにシフトして最後尾のAになるとみなせる。この変化を言い換えると上でいう左シフトということになる。

感想

実験ゲーかと思いきや証明パートも確かにそうやなあという感じだった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto K = s[1];
    auto S = readln.chomp.map!(a => a == 'A').array;
    foreach (i; 0..N) S ~= [0, 1];
 
    int p = 0;
    bool flip = false;
 
    while (p < N && K > 0) {
        int c = S[p] ^ flip;
        if (c) { // 先頭がA
            K -= 1;
            S[p] ^= 1;
        } else {
            p += 1;
            flip ^= 1;
            K -= 1;
        }
    }
 
 
    auto ans = new int[](N);
 
    if (K == 0) {
        foreach (i; 0..N) ans[i] = S[p+i] ^ flip;
    } else if (N % 2 == 0) {
        foreach (i; 0..N) ans[i] = i % 2;
    } else {
        ans[0] = S[p] ^ flip ^ (K % 2);
        foreach (i; 1..N) ans[i] = 1 - i % 2;
    }
 
    ans.map!(a => a ? 'A' : 'B').writeln;
}

nebukuro09の日記

AtCoder Grand Contest 011 D - Half Reflector

問題概要

解法

感想

コード (D言語)