ARC096

C - Half and Half

変数が3個ある問題怖いよね。おまけに、開始前「DP」という文字列を見ていたため、5000という微妙な制約に色々考えてしまう(いや、何も考えてないんだけど)。この問題で複雑なのは、Aが値段で、A円を何枚分払うかの枚数と同じ単位の変数はXなのだ(なに言ってんだかわからんね)。まあなんか混乱していた。ていうかAピザの値段がA円てのがアレなのか。
解法としては、どれかを固定すればいいんじゃないかと思って、まずはAの枚数を固定した。しかし、Bピザに影響する変数が2個も残っている。じゃあABピザの枚数か。なるほど、これなら残りのAとBを何枚買えばいいかが簡単にわかる。全探索の範囲は、ABピザだけで十分な量になるmax(x, y)*2まで。あとは単に値段の最小値だが、ABピザだけで既に十分なAピザがある場合は、Aピザの必要量が0枚になる(マイナスにはならない)という点に注意が必要。制約はintで行けそうな雰囲気を出しているが、思考停止ll。マクロは嫌だけどusing ll = long long;なら許される(?)ことに気づいた。long longは0LLと型が同じになるのが良い(int64_tは実質が同じでも型は違うかもしれない)。

D - Static Sushi

円形で寿司、絶対に回ると思うじゃん。「時計回り」という言葉が出てきたときも、「じゃあ回転方向はどっちなんだろう」と確認事項を頭の中で追加しながら読み進めていた。今気づいたけど、問題名がStaticだったね。これなら、(回転寿司ではなく)止まった寿司だとわかる。問題文の「停止寿司」を見たときは停止問題を連想してしまった(回っていたのがどこかで止まる問題だと思っていた)。
まず、一直線に進んで店を出る場合を考えた。つまり、進む方向を一度も変えない場合。それは簡単に書ける。中身を2回実行するfor文を書き、末尾でreverseする。xとvはstructに入れてxでソート(入力がソート済みであることに気づかず、Cより小さいことはちゃんと確認していた)。サンプルでデバッグして、向きを変えないケースのコードは書けた。
O(N^2)でいいなら解法がわかった。そもそも、道なりに歩いていくしかないので、どの寿司を選ぶかO(2^N)かけて探索する必要がない。どうやら、1回しか進行方向は変わらない。最初は確信が持てなかったけど、コードを書いて必要な考察をやっているうちに90%くらいの確信にはなっていた(いいのかそれ)。で、これはO(N)に落とせそうだとも思った。状況がそんなに変わらないのでO(N)個のデータを保存しておけばよさそうだ。具体的にそれが何かというのが難しい。区間で最大値がわかればいい。累積和じゃないけど雰囲気は累積和。そうなると、保存する値がN+1個あることになる。そのうちN個しか要らないのだけど、どっちに1ずらしたらいいのか。こういうのも苦手。結局はACしたけど、サンプルデバッグをけっこうやった。

E - Everything on It

包除原理は浮かんだけどね。使えないのでね。でも考えてみたんよ。Aが0個の場合の数からこつこつと。対称性あるしワンチャンあるかと思ったけど完全に気のせいだった。各トッピングについて対称でもけっこう色々な状況があるのね。N=2のケースだとABの重なる部分が10通り(全体で16通り)と思ったより多かった。