AtCoder Beginner Contest 116

atcoder.jp

競プロを再開してから初めてABCで解けない問題があった。悲しい。

C問題は書くだけ。しかし10分くらいかかった。

D問題が解けなかった。DPかなと思ったのだが制約が厳しくて愚直な方法では通らない。そこからDPを効率良くできないかと考えてしまったのが良くなかった。

p種類のネタを使ったときの最大値を考えるという発想はあったのだが、想定解法に至らなかった。確かに解説を読んでしまったらなぜ思いつかなかったのか不思議だが、DPだという先入観があったので良くなかった。