ARC065-F:Shuffling
解説と考え方がちょっと違った。
問題
考察・解法
まず、操作列の左端が単調増加であることに注目してみる。となる部分があったときに、
から
文字目の並びは、
回目以後の操作の影響を受けない。よって、この時点でこの区間の文字の並べ方の数を数える必要がある。この区間における文字の並べ方の数は、この区間に1が何個あるかで決まるから、なんとなく1の数を状態に持ちながらdpをすればいいのではないかという気持ちになってくる。
当然このままでは右端のことを何も考えていないのでうまくいかない。しかし、それぞれの位置について、「その位置が最後に操作されるのは何回目か」という情報はわかるので、各操作について「何か所の位置がその操作以後の影響を受けないか」という情報がわかる。これがわかるのであれば、同様の考え方で数え上げていけそうな気持ちになれる。
このような数え方を実現するためには、もう少し考察が必要である。ある位置の1に注目し、この位置が
回目の操作で始めてシャッフルされるとき、位置
の1を「拾う」と言うことにする。また、ある位置
について、
回目の操作がその位置がシャッフルされる最後の操作であるとき、
に1を配置することを、「置く」と言うことにする。すると、
を「
回目の操作まで終わって、今持っている(拾った後どこにも置いていない)1の数が
個のときに、それまで確定している位置における文字の並びの数」というdpがうまくいくことが、
の単調性から示せる。
回目の操作において、その操作以後に影響を受けない位置が存在するとき、それらの位置は操作
で操作される区間の中で、左側と右側に分かれる。操作の左側に1を置くときは明らかであろう。右側に置く場合が不安になるが、
回目以後の操作は「
]の内側で行われる」か「
より右側で行われる」かのどちらかである(
に単調性がない場合、これが成り立たない)。前者の場合、保持している
の個数が同じ状態は、
回目の操作以後すべて同じ状態とみなせる。後者の場合は、そのような操作が行われるときには、今まで拾った1はすべてどこかに置くことになるので問題ない。もし
に単調性がない場合、例えば
のような操作列を考えると、1回目の操作で今持っている1をどこに置いて管理するかが問題となり、単に持っている1の個数が同じというだけでは同一の状態とみなせない、ということが起こり得る。
dpの遷移は、「回目の操作で拾う1の数」「
回目の操作が最後になる位置の数」(ギャグか？)を前もって計算しておく必要がある。細かいところは実装を参照。
