AtCoder ABC 145 - こんちゅう

覚え書きのために，競プロの解けなかった問題の簡単な説明を記録することにした．
いつまで続くかな．

ABC145E

atcoder.jp

最後のT-1秒にいくらでもコストのかかる注文ができることがミソ．
ただしナイーブなdp

dp[x][y][z]:注文1~xまで，y時間以内に完食，ただし注文zはT-1秒で注文

では $O(N^2T)$ なので間に合わない．困った．

解き方１

dp1[x][y]:注文1~xまで，y時間以内に完食できるもののうち満足度最大
dp2[x][y]:注文x~N-1まで，y時間以内に完食できるもののうち満足度最大

とすると，T-1秒に注文するものをiとして,dp[i-1][t]+dp[i+1][N-t-1]+A[i]についてiとtに関する最大が答えになる．

解き方２

とある注文セットを考えたとき，そのうち一番長い料理についてT-1秒で注文するようにしても問題ない．
よってA[i]を昇順ソートして,
dp1[i][T-1]+A[i+1]
のiについての最大が答え．かしこいなあ．

解き方3

dp3[x][y][b]:注文1~xまで，y時間以内に完食，T-1秒に注文したかどうか

というdpを考えると答えはdp3[N][T-1][1]となる．よくあるテクニックらしい．

ABC145F

atcoder.jp

難しいよう．

まずK=0のときを考えると答えは
$\sum_{i=0}^{N-1} max(0,H_{i+1}-H_i)$
となる．K>0のとき，プレイヤーは $H_i$ をその前or後ろのやつに揃えるのが最適．よって問題は $H_i$ をK本消したときのコストの最小値がなんぼかということになる．

ここからも厄介で，N本からK本消すのではなく0本からN-K本までHを生やすと考えたほうが漸化式が立てやすい．コスト最小のみを考えればいいので,例えば

dp[x][y]:生えているHの一番左のindexがx，合計y本生えているうちコスト最小

とすると，dp[x][y]になり得る候補は，y-1本生えているとき，一番左のindexがx'>xとなっており，そこからH_xを生やすような状況しかない．y-1本生えているとき，一番左のindexがxで，そこからx'>xなるx'に対してH_x'を生やすような状況も考えられるが，それは前者の状況に還元される．これによって前までの生えている場所の情報を考えることなく更新できる．すごいなあ．