みんなのプロコン2019 D - Ears
すぬけ君一体どういう生物、、
まだこのレベルはコンテスト中に解けない気がする。
解法
すぬけ君が行ったり来たりする中で、石が数がどんどん増えていき、一つも石が入っていない耳ももちろんある状態。どれだけ石が入るかは散歩の仕方によるけれど、偶数/奇数に着目すると散歩の仕方の制約から、番号が若い耳から0個ゾーン、偶数ゾーン、奇数ゾーン、偶数ゾーン、0個ゾーンに分かれる。幅が0のゾーンもあることに注意する。
雑な図だけど散歩をsで始めてeで終わった場合の、各耳の石の数を表してみた。
ゾーンの幅はゼロの場合はあるけど右から左に移ることはないので、左から順に番号つけてそれを一種の状態とみなす。そして座標iとゾーンの状態でdpをしていく。
遷移のイメージはこんな感じ。実装する時には右側の矢印の塊みたいなイメージでやるとdpテーブルの長さをL+1にしなくても実装しやすい。
https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4230647
参考にしたサイト
http://drken1215.hatenablog.com/entry/2019/02/10/014800
https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4229534
