ダブリング～AGC036-B "Do Not Duplicate"～

問題

700点問題

AtCoder ProblemsにおけるDifficulty（コンテスト中にACした場合の最低レート） : 1707

方針

ダブリングを使う。（ということでダブリングについて書く。とはいえ、あとで「つまずきポイント」に書く通り、公式解説で「ダブリングしたらあとは楽勝」みたいな雰囲気出てるほど簡単な話ではない。少なくとも緑下位の自分にとっては他にも詰まるポイントが多数あった）

なぜダブリングを使おうと考えるのか？

ダブリングを使うのはどういう時かというと、ある操作を沢山したらどうなるかを知りたいとき。今回で言えば、数列の各数値を1つずつ見ていって、手持ち配列に加えたり削除したりすること。他にも、ある頂点から1つずつ遡って祖先を探す（ダブリングの典型であるLCA）とかがあるらしい。

使える条件は、「1回進んだ時の状態」は簡単に分かるが、ずっとず～～～っと先に進んだ状態を知ろうとすると計算時間が全然足りない、という時。

ダブリングとはどんな手法か？

前処理

1.「状態jからスタートして、2^i回操作を繰り返したときの状態」を DP[i][j] と定義する

-- この時点だと「は？」という感じ

2. （重要！）DP[0][各j]を求める

-- Q. DP[0][各j]って一体何？

-- A. 「状態jからスタートして、2^0=1回だけ操作したときの状態」、つまり「ある状態から1回だけ操作をするとどうなるか」を全ての状態について求める。これはO(N)でいける。

3. （超重要！）遷移式 DP[i+1][j] = DP[i][ DP[i][j] ] を用いて、全てのi, jについてDPの値を求める

-- Q. さっぱり意味が分からないんだが？

-- A. 例えばi=3とする。DP[3][j] とは、「状態jからスタートして、2^3=8回操作をしたときの状態」である。すると、そこから更に2^3=8回操作をすれば、16=2^4回操作をしたことになる。つまり、「状態jから2^4回操作をしたときの状態 = 状態jから2^3回操作をしたときの状態から再スタートして更に2^3回操作をしたときの状態」ということ。

4. これで前処理が完了

DPの値を使って、目的のものを求める

例えば、「状態jからQ回操作をしたときの状態を知りたい」とする。

ダブリングを使わず愚直にQ回回せば当然O(Q)なので、Qが大きければTLEする。

Q. ここでダブリングを使うとなんで間に合うの？

A. 「2^i回操作したらどうなるか」が分かっているから、Qを2進数で見たときに立っているbit（kとする）」について、DP[k][hoge]を足していけばいい。

Q. は？

A. 例えば、Q=13（つまり13回操作をしたときの状態を知りたい）とする。

13を２進数として見ると 1101 なので、k=0, 2, 3のときにbitが立っている。

（ここ重要！）このとき、「2^0=1回操作をする→2^2=4回操作をする→2^3=8回操作をする」という風に考えると、ダブリングで作ったDPを活用できる。

2の累乗を使っているので、O(logQ)で処理できる。

Q回操作をしたときの状態を知るためのコード（C++）

int state = 0; // 初期状態 // Qのbit桁数回ループする
for (int i = 0; (Q >> i) >= 1; i++){
  if ( Q & (1 << i) ){
    // i番目のbitが立っていたら、
    // stateに「状態stateから 2^i 回操作をしたときの状態」を代入
    state = DP[i][state];
  }
}

まとめ

ダブリングとは、「1回操作をしたときの状態」は簡単に分かるとき、DPテーブルを前処理しておくことで、「Q回操作をしたときの状態」をO(logQ)で計算できる手法！！

つまずきポイント

ACコードに至る過程において、緑下位(参加当時)の自分にとって非自明であった部分（自分がどこでつまずいたか）

自分のACコード

ダブリングは分かったけど、答えが求められない

ダブリングの考え方は分かった。「Q回操作をしたとき」、つまり「Q回空にしたあとどうなるか」がO(logN)で求められるんでしょ。でもそのQはどうやって決めるのか？ N*K回数値を見なきゃいけないことは分かるけど、それまでに何回数列が空になるか分からないから、ダブリングを活用するところまで持っていけない。

-- A. 決め打ち二分探索を使う。

つまり、「空にする過程で飛び越えた数値の合計がN*Kを超えない、最大のQを求める」と考える。そこから先は、愚直にシミュレーションをすれば間に合う。詳しくはコード参照。

また、二分探索、決め打ち二分探索については以下がオススメ。

二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜 - Qiita

「答えを決め打つ」タイプの二分探索を使いこなそう - ARMERIA