(問題概要は省略)
実装してて頭ぐちゃぐちゃになったので思考整理。
この問題において、 \(B\) がざっくり \(20\) 個強あれば必ずすぬけ君を敗北させられる。(何故なら、すぬけくんの移動可能範囲を \(1/2\) ずつ減らしていけるから)
なので、数えるものを数えやすそうな「すぬけくん生存ルート」にして、全事象からそれを引く方針を取る。
ここで、すぬけくんが「今、直後に \(B\) を置かれても確保できる移動範囲について、その長さだと多くともあといくつ \(B\) を置かれると負けるか?」 という量を、「すぬけくんの余命」と定義する。例えば、#xy.z...#について、 \(x\) の位置にいるなら余命は \(1\) 、 \(y\) の位置なら余命は \(2\) 、 \(z\) の位置なら \(3\) という具合。
最初、すぬけくんの余命は \( \infty \) である。
ここで、以下のDPを考える。
dp[次に見るのが \(i\) 文字目][すぬけくんの余命]={場合の数} (実装では後者だけkeyとして持てばok)
ここで、このdpの遷移は以下のような形になる。
Bか?に出くわしたとき、dp[ \(i\) ][ \(j\) ]を、
- dp[ \(i+k\) ][ \(1\) ] に \(1 \le k \le 1\) について加算
- dp[ \(i+k\) ][ \(2\) ] に \(2 \le k \le 2\) について加算
- dp[ \(i+k\) ][ \(3\) ] に \(3 \le k \le 4\) について加算
- dp[ \(i+k\) ][ \(4\) ] に \(5 \le k \le 8\) について加算
- ...
- 但し、文字
Bを跨ぐような遷移は、Bの位置までで中断し以降の遷移も全て破棄する。(この遷移は、Sが続いた場合のものなので)- さらに、2つ目のkey(すぬけくんの余命)が \(j\) 以上の遷移については、すべて \(j-1\) へと遷移する。(ブロックを置かれるとすぬけくんの余命は確実に縮むので)
「すぬけ君が勝つ」⇔「すぬけくんの寿命が \(1\) 以上である」です。
最初のすぬけくんの寿命は、 \(23\) あたりでもとってやれば十分大きいです。
結局、この遷移はdel[ \(i\) 文字目終了時点に][すぬけくんの余命 \(j\) について]={それ以降のdp[すぬけくんの余命]をどれだけ変動させるか} として、累積和的に処理可能です。
Bか?に出くわしたときのdelへの計算を愚直に行っても \(O(N \log^2 N)\) 、工夫すると \(O(N \log N)\) となり、この問題を解くことが出来ます。(TL=4sというのもあり前者の実装で余裕をもってAC可能です)
Submission #19004101 - AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)
…あかん、まとめたはいいけど余計頭ぐちゃぐちゃなった…
