BCの2完。やべーセットだった。めずらしくWA投げ大会になった。
A - ST and TS Palindrome
KがN以下のケースをまず解いたが、これが広い意味ではハズレ方針だったのかなあ。そうじゃないケースがやばすぎる。文字列Sを矢印で表して考えていたが、矢印が複雑に重なり合う。これは、こういうノリで考えていたら解けない。それに気づくまで25分を使ってしまった。改めてB問題から楽しもう。
BCを解いて戻ってきた。残り10分ちょっと。N周期、GCD(N, K)、N*2周期を思いついて何も考えていないコードを投げてみたが、まあWAだよね。ARCの最初に考えるのと最後にやるのではだいぶ思考が別物になって面白い（最初だと丁寧になるが最後はテキトー）。
（追記）実際にこれしかないというものを構成してみる発想が全然なかった。「矢印が重なってるからここは回文じゃないといけなくて」じゃないんだよな。重なってる時点で（回文にできるなら）構成できてる。それでACするのもあれだと思ったので、自分がやってた延長のgcd使うやつで通しておいた。gcd単位で見てNとKの差が奇数なら単位の矢印自体も回文でないといけない。
B - Abs Abs Function
関数fの定義がやばすぎてスルーしたくなるけど、丁寧に解釈していく。aとxの距離がbのとき0。そこから離れるに従って大きくなっていく。つまり、a-bとa+bの近いほうまでの距離ということにおそらくなる。クエリの内容を読むと、std::setでできそうだ。組を追加するたびにa-bとa+bをsetに入れていって（重複したら入れなくていい）、区間の中で一番近いのを見つけるだけ。非負整数というのは入力の制約だけと思うことができるので、忘れてよい。たぶんintで大丈夫だと思ったけどA問題で脳が疲れているので思考停止でllを使った。区間との位置関係で3つに場合分け。もうちょっと、同じことを2回書かない意識を持ったほうがよかった。分けすぎて、提出直前に漏れに気づいて直した。
ここ数日調子が悪くて、今日もずっと寒かった。しかし、Bの実装辺りで体がいい感じにあったまってきた。よかった。
C - Even Sum Triplet
簡単そうに見えるが、実際に簡単だと思える。概要を把握したところで順位表を見た。Aのペナ率が高いのは予想通りだが、Cもだいぶやばい。順位はいいがAを通していないのでほっとくとどんどん下がるやつだ。
まず、操作する長さ3の区間に含まれる奇数の個数は0か2。偶数だけなら自由に動かせる。奇数についても、操作できるものがあれば散らばった奇数を集めることができるし、偶数1個を転がすことで奇数同士のswapも自由にできる。偶数と奇数の配置も自由にできる。あとは丁寧に場合分けするだけ。まず最初から一致していたらYes、そうでないときソートして一致しなければNo、そうでないとき全て偶数ならYes（自由にswapできる）、そうでないとき全て奇数ならNo（操作できない）、そうでないとき操作できる奇数があればYes（自由にソートできる）、そうでないとき（奇数は操作できないので）各奇数の位置が一致していて、奇数で分けた区間毎に偶数をソートして（偶数は自由にソートできるので）一致しないものがあればNo、そうでないときYes。提出してWA。WAが12個もある。
操作できる奇数があれば自由にできるは嘘だ。奇数をバラバラにすることはできない。あとから気づいたけど、操作が可逆であることを早く意識しておけばよかった。ACできれば可逆かを考える必要はないというような思考だった。Bを操作してAに一致させる問題と等価だった。Bもチェックするようにして提出、WA。WAは8個に減った。まだ多い。
もう少し考えると、奇数で分けた区間内の偶数が2個だったら操作できない。直して提出してWAが4個。4個ずつ減っている。なんとなくそんな流れな気はしてたけど、BCの2完ならペナは響きにくいしこのCは通せる見た目なのでもしWAなら早くわかったほうがいいと思ってどんどん提出していた。
ここからがしんどい。たくさん残っていた時間もだんだん終わりが迫ってくる。反例が見つからない時間が続く。Nが2のケースとか思ったけどそうだよなNが3以上なことは認識していた。「偶数と奇数が交じっているとき本当に偶数をソートできるか？」と考えて、奇数を含む操作では偶数同士の位置関係は変化しないと気づいた。つまり、偶数が3個未満しかなかったら偶数をソートできない。偶数が2個のときだけでいいんだけど、いい実装が思い浮かばず、別のvectorに偶数だけそれぞれ入れて比較した。提出してAC。
どうやって作問するんだと思いながら反例を探していた。証明すればいいというのはそうだけど。
結果的にHighestを更新できたから気分がいいけど（いやまあどちらかといえば「ホッとした」だけど）、コンテスト中は「ARCとは何か」を考えさせられた。A問題は内容は面白いかもしれないけどARCの序盤で使っていい時間では解けない。C問題も時間かけてACするだけなら700点のわりには難しくないし、いや難しくないのはいいことだけど、何を得ればいいのかみたいな。実力は測れるけど、コンテストに参加して面白いと思えないなら何のためのARCだよと。
