競技プログラミング用 知識集積所
B - Frog 2
最終更新:
sport_programming
-
view
問題
必要知識
ABCのB以下レベルの内容は省略
考え方
前問と考え方自体はほぼ同じ。
「2通りのうち小さい方」が「最大k通りの中での最小」に変更となるだけ。
問題は、もらうDPでも配るDPでも、実装方法を少し考えないといけない点。
「2通りのうち小さい方」が「最大k通りの中での最小」に変更となるだけ。
問題は、もらうDPでも配るDPでも、実装方法を少し考えないといけない点。
もらうDPの場合、前問では最初の2つを特別扱いしていた。
しかし、特別扱いする個数がk個と不確定になってはそうもいかない。
そのため、ループの範囲をmax(未作成)関数などを使って工夫することになる。
しかし、特別扱いする個数がk個と不確定になってはそうもいかない。
そのため、ループの範囲をmax(未作成)関数などを使って工夫することになる。
配るDPの場合、後ろに大量のダミー足場を付けるなら、いくつ付ければ足りるのか考えなければならない。
また、(今回は影響がないが)メモリや計算時間も確認が必要になる。
あるいは、ダミー足場を用意せずにループをきっちり止める実装だとしても、止め方を考えなければならない。
また、(今回は影響がないが)メモリや計算時間も確認が必要になる。
あるいは、ダミー足場を用意せずにループをきっちり止める実装だとしても、止め方を考えなければならない。
いずれにせよ二重ループ(未作成)を書くことになるし、範囲外アクセスの慎重な対応が必要で、実装はちょっと大変。