120. AtCoder参加記録（AtCoder Regular Contest 142）

25回参加でレート 1292 です。

今回はパフォーマンス 1633 です。

ABCを通して、DEFは未解答です。Aで2ペナ。

各問題の思考過程など。

A

初回提出8分18秒、そこからACまで14分43秒。

コーナーケースに自力で気付きましょう問題。

$K$ の末尾が 0 の場合は不適なので答えは 0。それ以外で、 $K$ を「そのまま」「ひっくり返した」数列それぞれの末尾に 0 を 0 個以上追加した数が $x$ の候補。高々12桁なのでこれを全探索すればよさそう。
$K$ について、「ひっくり返した」方が小さくなる場合は答えは 0 になることに気付いていなかった（1WA）
$K$ が回文的な数列になっている場合、重複してカウントしていた（1WA）

合計 2WA でした。もう少し注意深く行きたかったです。

B

23分59秒。

色々考えるものの、筋の良い解き方が見えない。でも、NG条件が厳しいのでそんなに難しくはないはず？とりあえず、「作った盤面が条件を満たすか？」を判定するデバッグ用の出力を追加。
こういう問題は最終的に簡単な答えになりがちなので、思いついた法則で適当に盤面を作ってみる。すると、「順番に並べたものから、奇数列目とその右の数を入れ替える」で、なんか通りそうな雰囲気。
$N = 500$ でも問題ないことを確かめたので、デバッグ出力を消して提出、無事AC。

これでいいのか…？という感じですが、まぁそういう問題だったのかもしれないです。

C

49分9秒。

細かいところを詰めるのが大変な問題。

①と直接つながっている頂点を見つける（クエリ）
1. 直接つながっている頂点が無ければ、②が単独で直接つながっているので $1$ が答え
①と直接つながっている頂点たちと②の距離を尋ねて、その最小値（とする）と個数を見る（最大クエリ）
1. $d \ne 2$ なら、その頂点を経由するのが最短ルートなので $1 + d$ が答え
2. $d = 2$ かつ、そのような頂点が 2 個以上あるなら、①と②は直接つながっている（①経由で距離 2 になるパターンしかない）ので $1$ が答え
以降、 $d = 2$ かつ、そのような頂点が 1 個だったとする（ $V$ と表現します）。ここまで、 $(N - 2) + 1 = N - 1$ クエリであることに注意。
今から考えるのは、「②は①と直接つながっているのか、そうでないのか？」です。
②と直接つながっている頂点を見つける。と直接つながっていることはない（そうであればになる）ので、それ以外の個について尋ねる。ここまでクエリ。
1. ここで、そのような頂点が無ければ、①と②は直接つながっている（かつ、②に子がいない）ことが分かるので $1$ が答え
先ほど求めた頂点から 1 つを適当に取る。その頂点と①、その頂点ととの距離を尋ねて、①からの方が近いなら、そうでないならが答え（2 クエリ、合計クエリで終了）
1. これは、②が①の子になっているのか、 $V$ の子孫になっているのか調べています