数ある中に……

PKUには、よく似た問題もあれば、なんと全く同じ問題もある。
今回教えてもらったのはこいつ。

2397を解いた後に、問題文を全く読まずに同じプログラムを3003で走らせてみると、見事にAccept出てきましたよw

問題自体は、一例としては動的計画法を用いる問題。表れる高さは高々1000なので、0から500までの高さに対して

ということを保存しながら、ステップを繰り返して解きます。

最初は全ての経路を動的に生成してたけど、この方法だとメモリ超過。また、1を20個入れるだけでも1秒近く時間が掛かっていたから、やはりよろしくないと思われる。

PKUを解く際の方法とか練習とかは、おそらく有名であろう実践的プログラミングを参考にさせてもらっている。
こういうところでコードを見てると、本当みなさん短いのよね…
私は短すぎると考えがまとまらないので長く書くのですが、それだとタイピングが遅くなるしなぁ……

また、経路の保存などだと、下手な配列を使うより文字列を利用した方が便利だということがある。いくつかの問題でも、文字列を利用したほうが簡潔に書ける場合があるので、このことも心にとどめておきたい。