naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉ARC 058 E - 和風いろはちゃん / Iroha and Haiku (700)


1から10までの数がN(≦40)個並んだ10^N通りの数列の中に、部分列の和が5,7,5(あるいはそれに代わるX,Y,Z)になっている区間があるパターンがいくつあるか数え上げる問題。

DPしたんだけどサンプルケース#3,#4で答えが合わないまま時間切れ。

解説読むよ

どこにもXYZを含まない数列の個数をbitDPで数える方法が載ってる

  • 直前に現れた値を合計が16以下となる範囲でだけ保存
  • bit列:2^(n-1)を積み上げていく感じで16ビットに収めてbitDP
寝て起きてから再考

自分のDPだと、例えば57575みたいなのを2回カウントしてしまっているってことだよね…
直近のX+Y+Z以内(未満)の状態を保持する形でbitDP書いてみる

  • 100001001000 みたいに(2^(n-1)を積み上げて)表現することで、575が成り立っていたら必ず5ビット目&12ビット目&17ビット目が立っていることを利用してチェックできる。
  • 保存すべきは575が完成していない状態数(最大16ビット)。
  • 40×65536×10=26214400 だし余裕で間に合うっしょ

→AC
https://beta.atcoder.jp/contests/arc058/submissions/2740760