水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

COLOCON -Colopl programming contest 2018-:D - すぬけそだて――トレーニング――

問題

atcoder.jp

解法

dp(i, j) := i 番目の候補の時刻から先で j 回起動するときの解の最大値

と DP をおく.このとき,愚直に全ての候補を選んでいては O(N^3) になってしまう.ここで,「今の時刻 + X を超える時刻のうち一番早いもの」と「今の時刻 + X を超えない時刻のうち一番遅いもの」の2通りについて考えれば十分なので(スタミナを上限の X のまま長く放置するのも,スタミナが上限の X に全然達しないときに選ぶのも,得にはならないから),O(N^2) に落とすことが出来る.

解答

atcoder.jp

2通りのところの考察が不十分で WA をいくつか出してしまった.

f:id:babcs2035:20181228164256p:plain