2019-05-28

AtCoder AGC 011 D - Half Reflector (赤色, 900 点)

AtCoder AtCoder900点 AGC-D 収束性に着目するほとんどのところで値が一定値に決まる実験ランレングス圧縮データ構造テク：差分更新データ構造テク：全体に反映させる値を別にもつ(遅延評価) パリティ 0と1の問題操作赤色diff >< 操作後の結果を求める問題操作をちょうどK回行う

この問題が解けた勝因は、「実験しよう」と思えたことな気がする。

問題へのリンク

問題概要

高橋君は，ある特殊な装置をたくさん持っています．
この装置は筒状で，左右からボールを入れることができます．また，この装置には 2 種類の状態 A, B があります．各状態について，装置にボールを入れたときの動作は次のようになっています．

状態 A の装置にボールを入れると，入れた側と同じ側からボールが飛び出してきて，その後すぐに装置の状態は B に変化します．
状態 B の装置にボールを入れると，入れた側と反対側からボールが飛び出してきて，その後すぐに装置の状態は A に変化します．

装置の状態の変化はとても速いので，1 つの装置にボールを入れた後，次にボールが入ってくるまでの間には必ず状態の変化は終わっています．

高橋君は，この装置を N 個つなげたものを作りました．左から i 番目の装置の最初の状態は，文字列 S の i 番目の文字で表されます．

次に高橋君は，一番左の装置の左端からボールを入れ，ボールがどちらかの端から出てくるまで待つということを K 回行いました．ここで，ボールがいつまで経っても出てこないということは起きないことが証明できます． K 回ボールを入れた後の各装置の状態を求めてください．

制約

$1 \le N \le 2 \times 10^{5}$

実験して収束性を掴む

とにかく最初はいろんなケースを手で実験してみた。そのうちにある程度規則性が見えてきた気持ちになりつつ、十分回数重ねるとどうなるんだろうというのを、実際にコンピュータで実験してみた。そうすると規則性は割と一目瞭然だった！！！！！

0: BABABBABABBABABABBBBBBAAAABABABBABABB
1: BABAABABAABABABAAAAAABBBBABABAABABAAA
2: BABBABABBABABABBBBBBAAAABABABBABABBBA
3: BAABABAABABABAAAAAABBBBABABAABABAAABA
4: BBABABBABABABBBBBBAAAABABABBABABBBABA
5: ABABAABABABAAAAAABBBBABABAABABAAABABA
6: BBABAABABABAAAAAABBBBABABAABABAAABABA
7: ABABBABABABBBBBBAAAABABABBABABBBABABA
8: BBABBABABABBBBBBAAAABABABBABABBBABABA
9: ABAABABABAAAAAABBBBABABAABABAAABABABA
10: BBAABABABAAAAAABBBBABABAABABAAABABABA
11: ABBABABABBBBBBAAAABABABBABABBBABABABA
12: BBBABABABBBBBBAAAABABABBABABBBABABABA
13: AABABABAAAAAABBBBABABAABABAAABABABABA
14: BABABABAAAAAABBBBABABAABABAAABABABABA
15: BABABABBBBBBAAAABABABBABABBBABABABABA
16: BABABAAAAAABBBBABABAABABAAABABABABABA
17: BABABBBBBBAAAABABABBABABBBABABABABABA
18: BABAAAAAABBBBABABAABABAAABABABABABABA
19: BABBBBBBAAAABABABBABABBBABABABABABABA
20: BAAAAAABBBBABABAABABAAABABABABABABABA
21: BBBBBBAAAABABABBABABBBABABABABABABABA
22: AAAAABBBBABABAABABAAABABABABABABABABA
23: BAAAABBBBABABAABABAAABABABABABABABABA
24: BBBBAAAABABABBABABBBABABABABABABABABA
25: AAABBBBABABAABABAAABABABABABABABABABA
26: BAABBBBABABAABABAAABABABABABABABABABA
27: BBAAAABABABBABABBBABABABABABABABABABA
28: ABBBBABABAABABAAABABABABABABABABABABA
29: BBBBBABABAABABAAABABABABABABABABABABA
30: AAAABABABBABABBBABABABABABABABABABABA
31: BAAABABABBABABBBABABABABABABABABABABA
32: BBBABABAABABAAABABABABABABABABABABABA
33: AABABABBABABBBABABABABABABABABABABABA
34: BABABABBABABBBABABABABABABABABABABABA
35: BABABAABABAAABABABABABABABABABABABABA
36: BABABBABABBBABABABABABABABABABABABABA
37: BABAABABAAABABABABABABABABABABABABABA
38: BABBABABBBABABABABABABABABABABABABABA
39: BAABABAAABABABABABABABABABABABABABABA
40: BBABABBBABABABABABABABABABABABABABABA
41: ABABAAABABABABABABABABABABABABABABABA
42: BBABAAABABABABABABABABABABABABABABABA
43: ABABBBABABABABABABABABABABABABABABABA
44: BBABBBABABABABABABABABABABABABABABABA
45: ABAAABABABABABABABABABABABABABABABABA
46: BBAAABABABABABABABABABABABABABABABABA
47: ABBBABABABABABABABABABABABABABABABABA
48: BBBBABABABABABABABABABABABABABABABABA
49: AAABABABABABABABABABABABABABABABABABA

最終的には "...BABABABA" が後ろからどんどん伸びているのがわかる。色々実験してみても、からなず最後はそうなる。もう少し細かくみると

S が偶数文字のときは、十分回数を重ねると、"BABA...BA" に収束して変化しなくなる
S が奇数文字のときは、十分回数を重ねると、"BBABA...BA" と "ABABA...BA" を繰り返すようになる

ということがわかる。この時点で、 $K$ は $2N$ (この $2N$ は別途ちゃんと要証明) とかなにかそのくらいの回数でバウンドしてよいことがわかる。

細かい規則

さらによく見ると、

S の先頭が B のときは、それが A に置き換わっておしまい
S の先頭が A のときは、"AAAABBBBBAAA" とかは "BBBAAAAABBBA" というように、
- 先頭の A を削って
- A と B を反転させて
- 最後に A をくっつける

という風になっていることがわかる。この処理は

ランレングス圧縮して
スタートが A か B かは別にフラグとしてもつ

という風にすれば $O(1)$ で更新できることがわかる。よって、最大で $2N$ 回程度まで $O(1)$ の更新を繰り返せばよいので全体として $O(\min(N, K))$ で解くことができる。

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
using Data = deque<pair<char,int> >;

char conv(char c, int change) {
    if (change & 1) return (c == 'A' ? 'B' : 'A');
    else return c;
}
    
string recon(const Data &v, int change) {
    string res = "";
    for (auto p : v) for (int i = 0; i < p.second; ++i) res += conv(p.first, change);
    return res;
}

int main() {
    int N, K; string S;
    cin >> N >> K >> S;
    Data v;
    for (int i = 0; i < S.size();) {
        int j = i+1;
        while (j < S.size() && S[j] == S[i]) ++j;
        v.push_back({S[i], j-i});
        i = j;
    }
    int LIMIT = (int)S.size() * 10;
    if ((K - LIMIT) & 1) ++LIMIT;
    if (K > LIMIT) K = LIMIT;
    int change = 0;
    for (int i = 0; i < K; ++i) {
        char c = conv(v[0].first, change);
        if (c == 'A') {
            auto p = v[0];
            v.pop_front();
            if (p.second > 1) v.push_front({conv('A', change), p.second - 1});
            v.push_front({conv('B', change), 1});
        }
        else {
            ++change;
            v[0].second--;
            if (v[0].second == 0) v.pop_front();
            v.push_back({conv('A', change), 1});
        }
    }
    cout << recon(v, change) << endl;
}