ABC 017 D サプリメント
考えてもよくわからなくて解説を見ました. 見て理解した気になって脳死実装したものの, サンプル以外WA（！）. なんでよ〜とかいいながらあちこちのブログを回ると, 自分の考察の穴がわかり, それを改善するとACできました. にしてもこれかなり難しいと思います...
解答
DPを考えます（どんなDPができるのか, それが思いつきにくいところですが...）
こんなDPができます.
こんな1次元DPで大丈夫なの？？？と思ってしまいますが, 遷移を考えてからそれを検証しましょう.
遷移および基底は,
例えばに対応している場合の数は,
番目までのサプリを前日に飲んでおり, 次の日に
番目のサプリを飲むという事象に対応しています. これを, 同じ日に飲むことができないサプリの番号まで足しあわせていっています. なんとなく遷移の形はよさそうです.
しかし, DPをこの実装で提出すると, なんとサンプル以外すべてWAになります（！）.
実は, 上のの設定が非常にまずい場合を含んでいます.
具体的には, 下のような場合です.
サプリの種類が
1 2 1 1 1 2
となっているとき, 6番目の"2"に対して上のルールでを計算すると,
となります. しかし, サプリの番号が3,4,5のものは同じ種類なので, 一日で一度に食べることができません. よってDPは不適当なことがわかります.
上のルールを改善するには, を拡張する必要があります. 具体的には, 以下のようにします.
は, しゃくとり的に右側にスライドしていくような感じになります.
は単調に増加し, 常に
と比べて大きいものを採用するので, 同じものが2つ以上重複するようなことにはならないことがわかります.
これで部分点が獲得できます.
dpを累積和しておくと, 満点解法になります.
感想
いやーむずい
