競プロ日記

コード
https://yukicoder.me/submissions/304205


確か初めての競プロはyukicoderだったので、再開ということで初心に戻って雑に★2～★3あたりを解いていこうの巻。
やったことある感じがする、DPかな？という第一印象。
この場合のDPの書き方がすぐに出てこなかったから、誰かが愚直に書くのも勉強になるよと書いていたのを思い出しDFSで書いてみるもWA。
町nまでコストcで行くための関数をsolve(n,c)とすると、solve(n-i,c-[iからnまでのコスト])を1≦i<nで回して最小を取ればいいのではという方針。
今度は配列数を多めに取ってもだめだった。

解説曰くダイクストラ法で解くらしい。
高校の頃の記憶を掘り返してダイクストラ法を考えるのもしんどいし、一度勉強し直してから解き直そう。
今の知識量だと再帰でも解けるだろうとは思うけれど、ダイクストラ法でないと解けないのかもしれない。
やはり一度その辺りの知識をつけるのが良いか。



12/16 23:30 追記
コード
https://yukicoder.me/submissions/304478


問題文を見落としていた。
スタートの町とゴールの町が同じでも道は2種類以上あるかもしれない。
これに対応するためにVectorを3重にしたらTLE。
テストケースを見る限り答えは合ってそう。
もうちょっと良い対応の仕方があると思うんだけど思いつかない。
もはや経験不足しか感じない。
次はダイクストラ法を学ぶ。