全国統一プログラミング王決定戦本戦-E Erasure

N個のブロックが並んでおり、幅K+1以上の全ての区間がある。区間の数をM個とすると区間の選び方は $2^M$ 通りある。全てのブロックを選択できる区間の使い方は何通りか。

素直なDPをする方法と包除原理を用いる方法がある。

seicaさんから掲載許可を頂いた画像が非常にわかりやすい。

f:id:olphe:20190220184537j:plain

これを参考にしたAC提出

ixmelさんに教えていただいた。

dp[i][j]を、i番目のブロックまで見て、i番目のブロックを(未来永劫)使わず、[0,i]でj個以上のブロックを使っていない場合の数と定義する。

分かりやすさのために、0番目のブロックとN+１番目のブロックを用意すると良い。

そうすると、dp[k][j]からdp[i][j+1]に遷移したいときに区間の幅とKから(k,i)での区間の選び方が求められる。

このままだと状態数が $O(N^2)$ 、遷移の種類が $O(N)$ で $O(N^3)$ だが、二次目を偶奇のみ持つことで状態数を $O(N)$ まで減らすことができ全体で $O(N^2)$ となるので間に合う。

この解法でのAC提出

olpheの競プロ帖