JOI本選 - ぴょんぴょん川渡り ペンキの色
2008年の予選・本選の問題はこれで全完(?)しました
ぱっと見やるだけDP、やってみるとやるだけDP
AOJ特有の複数データセットのおかげでvectorの初期化を忘れており死んでいて無限に時間が吸われたのでAOJに感謝ですね
i 行目の 左から j 番目の石から i + 1行目の k番目に渡る時のコストと今までのコストを足したものが先のコストより小さいなら値を更新、みたいなDP(m回まで1行飛ばしで進めるのでその分もうまく使いますが)
forでDPを解くのを避けてきていたけどそろそろ避けるのをやめていきたいと思ったのでfor で解いた
問題見た瞬間「あ!これ魚の生息範囲で見たやつだ!*1」となった
こんな感じの座圧は一度しか解いていなかったけどこれがわかったことには成長を感じています
座圧していい感じに処理した後は深さなり幅なりで数えあげて終了(完)
どちらの問題も比較的簡単だった気がする(ほんまか)
ペンキの色は座圧だ!となってから時間がかかってしまったのでイメージだけでなくきちんと紙などに書きながら考察していきたい
JOI頑張るJOI
*1:進研ゼミでゎなぃ