AtCoder Regular Contest 096

AtCoder Regular Contest 096に参加しました！
ABC095 旧版:
abc095.contest.atcoder.jp
ABC095 beta:
https://beta.atcoder.jp/contests/abc095/beta.atcoder.jp
ARC096 旧版:
arc096.contest.atcoder.jp
ARC096 beta:
https://beta.atcoder.jp/contests/arc096/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 095 / Regular Contest 096
rated 1200 / 2800
4/14(土) 21:00 ～ 22:40 (100分)
100-200-300-500(300)-900(600)-900 (6問)
ペナルティ: 5分

方針

C,D問題を解き、E問題は部分点を取得したいところ。
というかDはDP問題(累積和もDPと見做す)でしょこの配点……。

A - Something on It

要は、三文字中の'o'の数*100 + 700円が答えです。
文字列の操作に関しては過去問で勉強してみてください。

B - Bitter Alchemy

まず、全てのドーナツを先に1個ずつ作ってしまいます。
後は、最もお菓子の素の消費量が少ないドーナツのみを作れば良いです。
O(N)ですね

C - Half and Half

まず、2C>A+Bならば普通に作った方が安いです。
そうで無い時、まずmin(X, Y)個のピザを2C * min(X, Y)円で作るべきです。
そうすると後残ったピザは一種類なので、そのピザを普通に作る値段と2Cを比較して、安い方で残ったピザを作るべきです。
O(1)問題ですね。

D - Static Sushi

まず、寿司の無いと分かり切っている場所を歩くことに意味が無いです。
とすると、2回引き返すことは絶対に意味がないことが分かります。
ということは、0回か1回しか引き返しません。
まず、引き返さないとしたとき、寿司iまでの獲得カロリーは時計周りに寿司i-1への獲得カロリー-(寿司iの距離-寿司i-1の距離)、
もしくは反時計周りに寿司i+1への獲得カロリー-(寿司i+1の距離-寿司iの距離)であると分かります。
つまり、これは漸化式として表すことができるので、累積和を用いることで寿司iまでの獲得カロリーをO(1)で取得できます。
つまりO(N)で求めることができますね。
次に、どこで引き返すかを考えます。
時計回りを最初にする時、ある寿司のある地点iにおいて引き返すとすると寿司Nから寿司i+1までを反時計周りに取った時の最大の摂取カロリーを取りに行きたいはずです。
ということは、これを前もって計算しておけば各寿司についてO(1)なので、全寿司を考えてO(N)、間に合いますね。
反時計周りも同様です。

結果

oxxx 1完(300点) 04:58(0WA)
621位 パフォーマンス: 1299
レート: 1801→ 1759(-42)

感想

……青色辞めたら？
C問題はただの算数なので間違える要素すらないです。
そしてD問題も累積和なことは見りゃ分かるって位簡単なのに……なんでバグらせたし。
しかもこの解説書いているときもまだWA残ってるし。
というかWAなのに解説してどうすんのよ、せめて正解してから解説してどうぞ。