5完。あまりにも苦手セット。苦手なのはいいけどC問題までが面白くないのに時間食われて最悪だった。
A - Apple
A問題らしくループを使わない解法がないかけっこう考えたけど思い浮かばず普通にループ。ちょうどなので3個買いの回数を全探索。3個買いの回数を決めると1個買いの回数も決まる。
解説を見るとやっぱり場合分け。場合分けはする気が起こらなかったけど全部見通せてればこれもありだった。力不足。
B - Explore
持ち時間と待ち時間を間違わないようにかなりのエネルギーを使った。シミュレーション。持ち時間は途中でintに収まらなくなる可能性がある。しゃくとりみたくしてボーナス部屋を判定したが、今思うと各部屋でもらえるボーナス量を持っておくだけでよかった(アホ)(Xが昇順になってることに惑わされたなあ)。
提出してWA。長いコードなので見直すにも時間がかかる。持ち時間が0になったらアウトだった(0はセーフだと思ってた)。読んではいたと思うけど、意味を取り違えていた。ここまでで12分と1ペナ。気分は最悪になり、かなり引きずった。
C - Belt Conveyor
シミュレーション。4方向の場合分けが重いけど、まとめて書くべきだったか。ここまで虚無問だけで21分。100分しかないratedコンテストの中の21分。やってられん。
D - Iroha and Haiku (New ABC Edition)
3個なのでとりあえず真ん中を決めてみることにすると、真ん中はしゃくとりで列挙がO(N)、左右も累積和の二分探索でいける。二分探索でどんな数を探すかがややこしくて時間を使う。
解説を見て、決めるのは真ん中でなくてもいいと知る。なるほどなあ。単に累積和に4つ点を打つだけか。このすっきりした構造が見えてないし、真ん中でやったせいでややこしい部分の思考が2倍になった。setを使うのは全く思いつかない。
E - Warp
難しい。FGも読むが、どれも難しい。ここで順位表を見ると、Eがめちゃくちゃ解かれている。意味不明すぎる。そもそも、M=1で答えが3^Nかどうかを判定する問題すら解けない。
3種類のワープをそれぞれ何回使ったかわかれば結果を同一視できることに気づいた(当たり前すぎて何に気づいたのかをうまく表現できないな)。だからこんなに解かれてたのかーと思うがここからも長かった。よくわからないが、とりあえず合計N回以下の全部についてどの障害物の上にいるか(あるいは障害物の上にいないか)を調べる。定数倍が1/6くらい付くO(N^3)とunordered_mapでまあ3秒なら大丈夫。DPだ。ここまで来てなおDPが必要になるのか。合計回数の少ない順に回す。貰うDPで、障害物の上だったらスキップする(どの障害物かは知る必要がなかったけど書き直す時間がもったいない)。それぞれのワープが0回でないときだけ遷移して、合計N個のときは答えの変数に足して、そうでないときはDPテーブルに保存する。178msで意外と速かった。
これ水diffはびっくりだけど、水上位だしDPならこんなもんかなとも思う。それよりも、FGが全くわからないのがつらい。全方位苦手セットだったし、実力が低いことの表れでもある。
F - Manhattan Cafe
(追記)こういう幾何的に(異常難易度で)解けそうなやつをDPで解くの、全く自分の感覚と乖離していて、思いつかないし拒否反応がある。解説を見ればまあDP自体は書けるし、累積和で高速化できそうなこともわかる。しかし、その累積和の実装が異常に難しい。斜め2方向の累積和がきついし、区間を3つに分けて処理する必要があり、それによって累積和の境界がわからなくなる。もう嫌だ。
G - 012 Inversion
(追記)解説を見ると思ったより簡単そう。遅延セグ木。実装しながら詰めていく。転倒数の処理が対称性なくてループで書きづらい。一番の問題は、数を置き換える作用で1,0の個数などがどうなるか。1になるものそれぞれと0になるものそれぞれの関係が何個あったかを足していけばいいが、実装が相当めんどい。なんとかACしたが、解説の実装例を見ると貰うんじゃなくて配ってて、なるほどそうすれば楽だった。