AGC #005-D ~K Perm Counting - 問題解決の宝石箱

日本語につき問題文は略。

agc005.contest.atcoder.jp

包除原理の適用

いくつかルールがあり、その全てorどれか1つを満たす*1方法を数え上げる問題には、包除原理が使える。この問題の場合、ルールとは

${ a_{i} = i+K }$ または ${ a_{i} = i-K }$ を満たすこと

である。各 i について合計 N 個のルールがあり、0〜N個のルール採用方法のパターン数がそれぞれ計算できれば、包除原理が適用できて問題が解ける。

ルールを満たすパターンの数え上げ

a[0]からa[N-1]まで順番にルールの採否を決めて処理しようとすると、選んだ数の履歴が必要に思える。ところが、この問題は観察により回避できる。突破口への鍵を探すため、具体例で考えよう。

例えば、N=10, K=2 としてみると、各 i について a[i] のルールは以下の通り。 a[i] の値が i-2 または i+2 の行と一致するとき、「ルール採用」と考える。

i	1	2	3	4	5	6	7	8	9	10
i-2	-	-	1	2	3	4	5	6	7	8
i+2	3	4	5	6	7	8	9	10	-

上の表で、例えば a[1] = 3 に決めたとする。すると、a[2], a[3], a[4] までは a[1] での決定にかかわらず自由にルール採否を決められる。次に a[1] の決定が関わってくるのは a[5] となる。

a[1] = 3 を選んでいた => a[5] = 7 or 不採用
a[1]でルールを不採用 した => a[5] = 3 or a[5] = 7 or 不採用

という具合。次に a[5] が関係するのは a[9] であり、このとき a[1] での決定は忘れて良い。

選択の依存関係を図にすると一目瞭然だ。

f:id:hama_DU:20161006232445p:plain

↑依存する位置を同色で塗り分けた図。a[1] での選択は a[5] の選択に影響を与えている。

K=2 に限定せず、図を一般化すると以下のようになる。

f:id:hama_DU:20161006233238p:plain

↑2*Kで割った余りが同じグループが依存関係となる。

DP

DPの状態は、(ルール採用個数, 現在見ている場所, 直前に i+K のルールを採用したかどうか) 。「現在見ている場所」は 1, 2, 3, ... , N という順番ではなく、mod 2*K 順に処理する。例えば N=14, K=3 なら (1 -> 7 -> 13) -> (2 -> 8 -> 14) -> (3 -> 9) -> (4 -> 10) -> ... となる。

遷移ルールは次の通り。