ARC056

最近ブログ書いてなかったので備忘録的に書いておこう

かなり反省した。

A:書いてそのまま出したら最後K個買ったほうが安いのを忘れていてWA

B:割とすんなり後ろからunionfindが思いつけてよかった.(xに行くとき,x未満は全て埋まっているとして良い.(a(<x)が埋まってないとしたらそもそもsからaには辿りつけないのでsからxに行く時にaが埋まってようが埋まってまいが関係ない) ので,逆からやると使える辺が増えていくunionfind)

C:慣れていれば思考要素は0.部分集合を列挙するbit演算を使う(0を入れないように注意)

D:1時間以上余ってたのに解けなかった・・・
まず貰うDPを考えます.dp[i]=iで飲んだ直後の嬉しみの最大値 とすると,dp[i] = max dp[j]+cost(j,i) for j<i となります,where cost(j,i)=jで飲んだ次にiで飲んだ時の増えるうれしみ.
iを増やした時のcost(j,i)の変わり方は,各酒ごとに注がれる時間が来たら区間addで更新 とできるので,区間maxとaddの出来るstarryskytreeを使えばOK.

dpの更新はsegtreeでできるなあ と思っていたのに配るDPしか頭になくて解けなかった.
冷静に考えてオーダーが落ちるとしたらどこかの処理まとめるしかなくて,くばるのが無理なら貰うしかないですね.
というかcost(j,i)を得られるsegtreeとその更新までは考えてたんだからあとはmaxとるだけなんだけどなあ・・・

今度からちゃんと貰うDPを考えよう,というか閉じた式で書こうとすると貰うDPになって,閉じた式で書けるならその形が嬉しいことが多いから,はい,書きましょう.

コンテスト後に書いたD なぜか2000msピッタリでACだったんだけどこれ結構危険じゃないですか(そんなに定数倍遅い方でもないと思うんだけど)
Submission #780932 - AtCoder Regular Contest 056 | AtCoder

まあscanfにしたら速くなるかもだけど