AtCoder Regular Contest 200 (Div. 2)

　ABの二完。若干レートは下がったが、それほど失敗したという感覚はないため厳しい。Aは、最初から紙で立式すべきだったかなぁ。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 200 (Div. 2) AB二完。
A Ai/Biが異なるものがあればその二つで作れる。Ai/BiとAj/Bjの間にある分数はStern–Brocot木を思い出せば作れる。
B 100と11100みたいなので大体作れた。
C Li<Lj<Rj<Liのときjからiに辺を引く。その中で辞書順最小かと思ったが、8caseしかACしない。

— titia (@titia_til) June 15, 2025

C - Movie Theater

　後ろから決めていけばいい、というツイートを見てAC。

　どこでWAになっているかの判断を誤っていたのがダメだった。今回は、人の順番の配列を求めた後、その逆写像が答えになるわけだけど、「人の順番の配列」の辞書順最小を求めても、その逆写像が辞書順最小にはならない。

　ここに気付かず、もっと別の条件の部分で間違っていると思ってしまってダメだった。

　逆写像を辞書順最小にするためには、後ろから決めていけばよい。

　このことは知らなかったけれど、この部分が間違っていると気付けたら試したと思う。

D - |A + A|

　自力AC。

　コンテスト中に書いた実験コードを利用してAC。

　コンテスト中は実験しても偶数のときの構築が分からなかったのだけど、落ち着いて実験結果を見たら、6以上なら、0, 1, 2, 4のように、0から連続する数＋一つ飛ばしでできていた。

　2は、偶数のときは0とM/2で良い。（奇数だとダメ）

　4のときでWAを出してしまったが、2のときと同じように、Mが4の倍数なら0, M/4, M/2で作れる。

　コンテスト中は、Dを20分くらい考えた後、分からなそうと思ってCに行ったのだが、その判断はどうだったんだろう。

　一応、今考えてACするまで30分はかかっていない気がするが、コンテスト後に落ち着いて

実験結果を眺められたからという気もするし、WAの修正に12分もかかっている。

　Dに集中していたら解けた可能性がなかったとは思わないけど、望み薄だったかなぁ。