AOJ 1619 Making Lunch Boxes (ICPC Domestic 2017 D)
まず問題を見た時点でDPだということが分かる。そして、制約がなので、
が
くらいになることがわかる。
想定解法はおそらく場合分けしてDPと全探索の二通りの解法で書くんだろうなと予想していて、実際に講評の解法の1個目はそうなっていた。しかし、上の制約からDPの（実際に登場する）状態数が小さいことがわかるので、mapを使えば1つの手法で実装が済むということがわかる。これは講評の2個目の解法になっていて、考察としては完璧だった。
ただのDPなので20分くらいで実装が終わったが、制限8秒のところ14秒くらいかかっていた。細かいことは分からない（ちゃんと調べたい）がmapが結構遅いということは知っていたので、色々と定数倍高速化して頑張ってみたが間に合わなかった。結局、が小さい場合には普通のDPに書き換えることで通した。この6秒を絞り出すのに80分くらいかかってしまった。本番では通るので、この問題については悪くなかったということにしておく。
