CF Round 969 (Div. 1) virtual 振り返り

ABCD 4 solved, 110 th

A – Iris and Game on the Tree

人と話していて設定した時刻から 6 分遅刻。

読む。根の値と葉の値が同じか違うかのみが重要。$S_1$ が ? のときは簡単。そうでない場合いつ $S_1$ を変えるかが重要になる。

もともと葉についている 0, 1 の個数が違う場合は初手で根により良い値を付ける。そうでない場合、葉の ? の個数が奇数である場合うまくやることで相手に根を強制的に選ばせることができて $1$ 得するなどがある。根でも葉でもない ? のことを忘れてサンプルが合わず困った。

トップはだいたい 10 分以内に詰めていて、自分の実時間が 15 分ほどなので厳しい。この 1.5 倍を埋められるような思考の研ぎ澄ませ方をしたい。

B – Iris and the Tree

まず読解が遅かった。

ある辺はたかだか $2$ つのパスにしか出ないので、各パスについてうまく寄与を計算する方針はすぐにたった。その後認識が甘くて、あるパス外の辺の重みの変更でもそのパスについての答えが変わるのを忘れており、割と大きく累積部分を手直しすることになった。

実装は、 index の詰めの速度が遅かったり +- を間違えたりして散々だった。

C – Beautiful Sequence

ある数列 $a$ が Brilliant であるような条件をまず考える。ここまでは ok 。

まず、ある $2$ つの値の差が $2$ のべきであればその間は埋まるな、ということを考えた。そこから少し迷走して、 2 進数で考えるなどいろいろなことをしていた。10 分くらいしたあと、実はどこかに連続した値があればそこに何を追加しても間を全て埋められることに気がついた。

これをもう少しうまく解釈すると、差分配列を取って gcd を載せた Segment Tree で、差分の gcd が素因数に $2$ 以外を含まないかどうかを二分探索するという結論になった。

実装は少し二分探索の index をずらしたがすぐできたので ok 。考察の部分、もう少し約数の感覚があれば速くできたなと思った。ある種の典型ではあると思うので、速くなる余地はある気がする。

D – Iris and Adjacent Products

数列 $a$ に対してどうやって答えを求めようかと思ったが、 $O(n)$ にしかならず少し詰まった。

$k\le {10}^6$ なので $O(\sqrt{k})$ を活用するのかなという発想はあったが、 $[\sqrt{k},k]$ のうち本質的に異なる値が $O(\sqrt{k})$ というのを突然思い出すまで $10$ 分ほどかかった。これはひどい。

たかだか $O(\sqrt{k})$ 個の値ならどうできるかを考えると、同じ値がたくさんあっても種類数に線形な形でできることはわかった。これは実装前にもう少し詰めるべきで、マッチング的なきれいな形になることを認識せず雑に実装を初めてしまった。末尾の処理などももう少し確認してから始めるべきだったと思う。

方針は Mo くらいしか思いつかず制約も小さかったのですぐに書き始めた。久しぶりに書いたから少し遅かったが、まあ許容範囲かな。

まとめ

詰めてから実装するべきだった vs もっと速く書くべきだった、というのが難しいように感じるが、多分他の場所で速度を稼げるようになって、ちゃんと詰めて書くようにしたい。