5完。無限にGの実装してて死亡。こんなのばっか。
A - Not Overflow
制約がギリギリを攻めてくるので怖い。特に、C++でabs(-1LL << 63)が負の数を返すのがやばいと思った。しかし結果的にはそういうの関係ない問題で、区間内に入ってるかを普通に試すだけ。
B - Matrix Transposition
正方行列の転置は慣れているが、これはやや混乱する。1列目をH個出力して2列目をH個出力してとやっていく。
C - kasaka
パッと見なんもわからん。少しして末尾の'a'を消すことを思いつき天才かと思うが、abという入力に対応できない。まず元の文字列が回文かを判定する。そうすると全ての文字がaの文字列はそこで処理される。そうでないとき、先頭と末尾にいくつaがあるか数える(aでない文字があるので最後までは行かずに止まる)。回文であるためには先頭と末尾のaの個数は等しい必要があるので、先頭のほうが少なければ足りないぶんを足す。push_backでやりたいのでreverseしてから処理する(反転しても回文性は変わらない)。難しかった。
D - LR insertion
難しいが、時間をおいてサンプルをよく見ると、逆からできそう。逆からというのは思いついてはいたが、そのときはできると思わなかった。結果的にはサンプルエスパーで未証明AC。
E - Skiing
高さが同じ広場をつなぐものも坂なのか?とか余計な心配をしてしまった。上るときはペナルティかかって2倍になる、けっこう厄介そう。しかし、同じ場所に行くなら上りが少ないほうがいいって考えると、位置エネルギー引いてダイクストラ法が使えることに気づく。上りのコスト(2倍してないやつ)だけを考えると、上りが最も少ないルートがわかり、各広場に行ったときの最大楽しさもわかる。典型と少しの天才で解ける、古き良きABCだ。
F - |LIS| = 3
Gと交互に考えていたが、解ける見た目をしていないので、早々に見切りをつけた。
ABC237のFをAC。「解ける見た目をしていない」から飛ばしたけど、俺がそう思った時点で解法がDPであることがほぼ確定しているのになぜ気づかない。
— merom686 (@merom686) February 1, 2022
G - Range Sort Query
8秒もあれば愚直が通ったりしないかな。こないだから平方分割の威力を見ていたのでそっちへ思考が行った。Xの位置だけわかればいいが、どこをさぼれるかすぐにはわからない。Xより大きいか小さいかしか意味がないと気づいて打開。平方分割でできそうだ。しかし、実装に時間がかかる。昇順と降順の2種類書くのがヤバ。残り10分になったときは書き上がらないと思ったが、雑に書き上がるところまでは行った。WAで終了。
(追記)最初に個数を数えるところで添字ミス、引き算はclampの外でやる必要があった(ここは雑にやってたしかなり難しいので順当)、降順ソートのときの添字ミス、半端を処理するとき個数を更新してなかった。ズタボロだったけどミスを直したら通ったのでよかった。