【28日目】DP2日目

昨日の続きのDP。結構似たような問題が続く。

40　JOI 2012 予選 4 - パスタ

i日目までの場合の数は直近二日間(9通りの場合分け)にのみ依存することから漸化式を立てられる。条件が複雑なので実装がやや面倒くさかった。こういうのもっと手早く実装できるようになるといいな。

41　JOI 2013 予選 4 - 暑い日々

前問と似ている。というかJOIの全部似ている。こちらは前日にのみ依存するので実装は簡単。DPっていつも初期値をどうすればよいかで結構考え込んでしまう。。

42　JOI 2015 予選 4 - シルクロード

そろそろ飽きてきたJOI4問目。今までのDPの問題でフィボナッチの次に簡単な気がしている。JOIの問題ってAtCoderとかに比べると、全体的に問題設定が複雑なものが多い気がする。正直あまり好きではない

43　パ研杯2019 D - パ研軍旗

これも左の列から愚直にやっていけばよい。

44　AOJ 1167 - ポロック予想

最初に1~10⁶まで全部計算する方針で。途中何回か方針を変えたせいで時間がかかってしまった。ひょっとしたらTLEするかな…？と思ったけれど大丈夫だった。TLEしそうかな、と思ってもやってみるといけることって意外と多い。まあ採点機が優秀なんだろうな。