N以外。珍しく夜に5時間確保してやった。
A - シンプル石取りゲーム/Simple Game
Sは結果が逆になる。Tは？これも逆になる。てことで、Nの偶奇とこれらを全部xorすればよい。どっちが正しいかはサンプルで確かめる。
B - 小数点第 D 位/Dth decimal place
Python有利な問題かと思ったらそうでもないみたいだな。Bで出すかという気はするが、こういうのは好き。まず、小数点の位置は2通りしかないので、整数部分が1桁なら先頭に0を追加する。揃ったので、小数点部分は飛ばして普通に足し算。入力は100未満だが答えは100以上になることがあるので、最後にキャリーが残っていたら先頭に1を追加。最後に先頭の0を除いて出力。
C - 逆順列/Inverse Permutation
これも好きなやつ。これの解説が2乗なの教育上よくない気がする。
D - シューティング / Shooting
アイテム2を使うなら早いほうがいい（敵の体力が多いときのほうがいい）ので、最初に何回連続でアイテム2を使うかを全探索。毎回半分くらいにはなるので30回程度やればいい。提出してなぜか1725msかかってそのときは理由がわからなかったが、アイテム2を使わないとき引き算でやってたらめちゃくちゃ時間かかるやんけ。割り算使え。これ言語アップデート前にやってたらTLEだったな。
E - 図形のシャッフル/Shuffle the Pattern
個数が合っていればよい。
F - 集合の問題 / A Set Problem
なんか前半に見た目が厳ついの多いな。ちゃんと読めば、unordered_setで被りを数えるだけ。containsを初めて使った。
G - 隣り合うマス / adjacent cells
位置ではなく、書かれている2数をソートしたものを辞書順に答える。メイン処理はDPでよくやるやつ。上と左を見る。
H - 3 枚階段 / Discarding Triplets
取れる3枚組を左から貪欲に取っていけばよさそう（未証明）。それを実現するために、mapで数えるかと思ったけど、普通にソートして数えてもそこまで手間変わらん。これで座圧されたみたいになったので、左から順にその3つが連続していて1個以上あるなら取るというのを繰り返す。入力はllで受け取ってたのにそれをintに入れててWA。ちょっと見慣れない問題だとすぐにこういうミスする。
あーmultisetは思いつかなかった。
I - 簡易オマハポーカー / Easy Omaha
枚数だけが重要。どれで枚数を稼ぐか全探索。自分のから2枚まで、机のから3枚までを取り、枚数に26を掛けて文字の何番目かを引いてスコアとする。番号が小さいプレイヤーから探索して最大値を先に更新したものを残せばそのまま答え。
J - 図形のシフト/Shift the Pattern
ローリングハッシュも思ったけど、最初に見えたFFTで頑張った。さすがに時間かかる。文字の個数が合ってることを別途確認すればよかったな。0と1だとどうやっても内積0なので1と2でやってた。
あーZ-algorithmか。log付かないんだ。
K - 金貨と袋のゲーム/Game with Coins and Bag
わかんなくて困るけど面白い。簡単そうなんだけど、整理に時間がかかる。ラウンドiから開始したときの期待値を後ろから求めていけばいい。
L - 順位表/Ranking
これは既出。「AtCoder トポロジカルソート 辞書順」で検索すれば出てくる。ABC223の問題を読むと上位互換なので、当時の自分の提出をそのまま出してAC。
M - お片付け/Put Away
セグ木で二分探索すればシミュレーションできる。ACLを使った。
N - ゴミ出し / Garbage
常にゴミを捨てるとしたときのゴミの量の最小値が0になるようにしてCより大きければできない。なぜなら、0にしたところをいくつに増やしても最終結果はそれより大きくしかならない。で、Xの最大値と思って書いたら最小値で、それを延々考えてわからなくて、それも誤読で金額の最小値だったし、誤読に気づいても何ら進展はなかった。二分探索はできないんですねーとか言ってた時期がなつかしいね。マジでわからん。
（追記）解説を見る。C[kg]としてよいの言われてみれば。捨てれるときは捨てるみたいな勘違いしていた時間が長かったので、誤認識に気づいたあとも発想が出なくなる。解説の後半は、やり方が示されているだけで正当性がわからない。ていうかやり方もわからない。予想して考えると、後ろからやってゴミの量が負になったらそこより前の場所でゴミを得たことにする、大きいものから貪欲に。自分は意味を捉えてしかコードを書けないので、どういう貪欲かわかるまでかなり時間がかかり、これを書こうとなったら簡単に書けた。ACはしたが、これが正しいかはわからない。誤読した問題が難しすぎてもう無理かもしれない。
