ARC121

ABCの実装で時間が全て消え、D以降は開くこともなかった。面白い問題に挑戦もできないのはクソだと思う。苦手セットで体調もいまいちだったのでこの結果も仕方ないというところ。むしろここ半年くらいARC/AGCが得意セットばかりだったのが異常だった。もちろん黄色から落ちるのはとても嫌だが、自分の名前が青で表示されてるのびっくりするくらい落ち着く。なんか競プロに疲れてたからちょうどよかったなという感じ。

A - 2nd Greatest Distance

順位表を見てヤバそうだったのでABCを全部読んだ。最初は、ソートして1番目を求め、それが複数あるかを確認して1個しかないなら端と反対側の2番目を候補として2番目の値を求めるという方針だった。しかし複数あるかを確認する処理のコーナーケースが面倒すぎる(xでの差の最大値とyでの差の最大値が同じとき、それを同じペアが出している可能性がある)。

実装途中で楽な方法を思いつく(考察が楽なだけで実装はそれなりに重い)。xでソートして両端から2つずつ、yでソートして両端から2つずつ、その8つを候補として全部の点とのペアをN*8個作り、重複を除いて2番目を出力。i(インデックス)でソートし直すのを忘れてサンプルがなかなか合わなかった。

B - RGB Matching

入力をN個しか受け取ってなくて少し時間をロス。並列に考えてるとこういう抜けが生じる。さて、カウントして全部偶数なら0。そうでないとき、和が偶数だから奇数は3個中2個。色と可愛さを同列に扱えたりしないかとか思ったけど、そうでもなかった。奇数の2つのaが一番近いものをペアにするのがおおよそ答えになりそうだというのはわかる。例外を考える。赤と緑のペアが2つ以上あったら、そのうちの2つを選んで赤赤と緑緑にできるので、高々1つとしてよい。赤緑・緑青・青赤の3つともあったとすると全体が奇数になってしまうのでそういうこともない。よって、(赤が偶数個だったとして)赤緑と赤青があるケースだけ追加で考えればいい。赤の同じものを取り合うケースが気になる。ソートして、2番目に近いときの差の絶対値および1番目の相手が誰かを記録して返すようにする。

解説を見ると、同じものを取り合うケースは考えなくてよかった。確かに、図を描いてみると、もろ三角不等式みたいになる。こういうの、実力差が出るから結果に文句はないけど、落とされた側は単純につまらないだけなのが嫌だね。

C - Odd Even Sort

タイミングさえ合えば上からポンポン持ってくることができそう。ただし実装上は後ろから合わせていったほうが楽かと思いそうした。1 3 2 というケースがヤバく、唯一の合法手を続けていくと全順列を生成して最後にソートが終わる。この長さ3の塊を使って楽にできないかと考えるが、N^2より少し多くなってしまう。やはりタイミングを合わせてポンポン運ぶ方針か。注目している要素が本来の位置にない場合、その次(右)の位置は自由に使える。よってそれが左端でない場合は、今の位置をiとして i-1, i, i-1 と3回操作すればレールに乗る。左端のときは、2 1 3 4 というヤバいケースがある。これは 2 3 1 4 と1回ほぐすと3に対して「左端でない」が適用できてその後タイミングが合う(ていうかこれさっきの 1 3 2 と同じケースか気づかなかったー)。ここで回数を消費してもN=3やN=4でN^2に間に合うので、Nが大きければなお間に合うだろう。ギリギリで提出するが、WA。ほぐすときにforを1個戻すのだが1しかずらしてなかった(カウンタ回るから2ずらさないと打ち消されるだけ)。

解説を見て、明快ではあるけど、N=3とN=4の両方を特別扱いする必要があるんだな。想定より複雑な問題だった。この辺の見極めは難しい。

D以降が見れないクソ展開は置いといて、Cまでの3問コンテストとして見たときの時間の使い方はどうだろ。まあ必要な時間ではあるんだよな。Cを(実装ではなく考察面で)しっかり詰める時間がなかったのが不満だが、これだけ簡単な問題でも3問2時間では足りないというだけの話っぽい。