Codeforces #403 (Div. 2) F: Innokenty and a Football League

行列の累乗みたいなことをするには、

O(ビット数*n^3)

で間に合わない。

実はbitsetを使えば十分速度が出せる。

メモリや実行速度が十分でないbool変数を使った解法は、bitsetを使うだけで間に合う場合がある。

最大の移動回数を求めるには、

0111<1000 (2進数表記)

のように、全てのビットが立っている数よりも、それより1桁多い数のほうが必ず大きいので、2進数で貪欲に上位の桁から決めていけばよい。

P->PB->PBBP->PBBPBPPB (1)

が問題文に書かれている。

これを反転したもの

B->BP->BPPB->BPPBPBBP (2)

も考えてみる。

解が0000...0???? (2進数)の形をとるとする。

つまり、いま解の2進数表記で下から4桁目を決めようとしている。

4桁目が立つならばそのルートは

PBBPBPPBから始まる。

そうでない場合を考えると、

ルートは空であるかP,PB,PBBPのいずれかから始まる。

よって、1桁ずれた部分問題

(??? (2進数), PBBP)

が得られた。

次にPBBPBPPBから始まる場合、つまり解が

0000...01??? (2進数)

の形をとる場合、

PBBPBPPBを反転したものはBPPBPBBPであり、

ルートの続きは空、B,BP,BPPBのいずれかとなる。

問題

(??? (2進数), BPPB)

が得られた。

これは(2)が(1)を反転したものであることから、(??? (2進数), PBBP)と同様に解ける。

P=>PB=>PBBPを作るのに、B=>BP=>BPPB=>...を使うことに気づく。

適切に問題を表す

ここでは(d桁目以下が未定、P/Bから始まる)

反転から、似たような小さい問題に持っていけることに気づく。