今回は ABCDEF の 6 完(72:21 + 10:00)(2WA). 難易度の低い問題を解くときの精神状態がかなり悪くなっている気がする。 なんでなんだろう。少しは埋めたほうが良いのかもしれない。
今回は私の気にしい性格によりとんでもないことになった。
スマホの充電器のモスキート音が気になる。開始 20 秒前で何故か不安になってしまう。 充電器を抜こうとしたが手が滑って全く抜けない。 A 問題をとりあえずといた。
どうやっても抜けない。 こんなことに 5 分ぐらい費やしてしまった。あほすぎ。 この問題は ARC の A 問題とかにあるやつなので、条件が難しく解きにくい。 実は、 $R-A$ と $(L-1)-A$ について $M$ でどの程度割れるかを見るだけ。 しかし負の値だとバグるので、$L, R, A$ に $2 \times 10^{18}$ を足して $A$ の値を $A \bmod M$ に調整し AC. どのくらい足せば良いのかがわからなくなっていたので、2WA を出す。もう死にそう。 シャーペンで無理やり充電器を抜こうとしたのでシャーペンが壊れる。
考察を書こうとしてシャーペンが壊れていることに気づきこれでまた 5 分くらい悪戦苦闘。 結局代替があったのでそれで書くことに。悪いことは連鎖する。
近いやつを貪欲にやるだけだと思ったら奇数のときにある一つを使わない場合の考慮を 考えるとめっちゃ重実装になる予感しかしなかった。 でも書いた。この時点で 33 分かかってて死んでいる。 解説見るとなんかすごい簡潔に書かれてるんだけど。
C を解いた後だったので、あれってなったが、これは簡単。 小さい順に並べ替えて累積和をとって二分探索するだけで解ける。
E の方は、連結したときのことを考えればいいだけなのでそこまで難しくない。 '.' の近傍の '#' について代表元を求めて、代表元のパターンの数 $-1$ だけ連結成分が消える。 代表元が存在しないときは $1$ 増えることになる。 これをしっかり Union-Find 等で実装できれば良い。
まず、 $d[i]$ ... $i-1$ から $i$ に行くときの距離と、 $h[i]$ ... $i$ の地点からスタートに戻る距離という定義をしておく。 このようにすると、まず $K$ を関係なしに、一回普通にたどってみる距離のことを考えて、 ある地点 $i$ について、そこに行くために $1$ 回帰ることを想定すると、 $d[i]$ が使われなくなり、$h[i] + h[i-1]$ が使われることがわかる。
こういう形をしているのでもっと簡略化する。 $e[i] = h[i] + h[i-1]$ とすると、家に戻って $i$ に行くとき $e[i]$ を使い、普通にたどるときに $d[i]$ を使うという 選択をする問題になる。$e[i]$ を使う間が $K$ 以上離れないようにするような問題である。
更に簡略化すると、$e[i]$ を使うことにしたときに起こる変化 $e[i]-d[i]$ だけを考える問題にできる。 つまり、$\sum{d[i]}$ は先に足しておいて、$e[i]-d[i]$ をどのように使うかを最小化するという問題になる。 すると、これには DP が使え、$\mathrm{dp}[i]$ ... $i$ までについてを考え、現在 $i$ を使ったときの コストの最小値という定義にすると、 $\mathrm{dp}[i] = \min{(\mathrm{dp}[j], \max{(1, i-K)} \leq j < i)} + e[i]-d[i]$ という式になるので、 これは DP 配列を RMQ のセグメントツリーで持っておけば遷移が高速に求まる。 最終的に答えが、 $\min{(\mathrm{dp}[i], N-K+1 \leq i \leq N)}$ に出てくる。
時間がない。残り 10 分くらいで LowLink を使って関節点について考えると良いことがわかった。 しかし、関節点を消したときにどの程度の連結成分が分解されるのかということがわからず、 無理やり書こうとしたが結局解けなかった。
Perf=1993 で別に悪くはなかったのだが、最近のコンテストをやっているときの精神状態悪すぎやしませんかね・・・ もう気になることがあると、気になることがどんどん増えてきて、誰も気にならないことが気になっていくという・・・ 問題を解くのは好きなのに、難しい問題を解く前にテンパって時間をすり減らすのは辛いっすよ。
(2023/12/24 02:03)B, F を再び解き、 G を解いた。 B だが、負の値でもずれないで計算できる割り算の関数を作っておくと良い。 自分は $\mathrm{bdiv}$ という関数をテンプレートに追加した。 これによって、 $\mathrm{bdiv}(R-A, M) - \mathrm{bdiv}(L-1-A, M)$ だけで 解くことができるようになる。 ついでに $\mathrm{bmod}$ も追加しておいた。これは modulo 演算そのものの mod を取る。
F は実はスライド最小値で解けて、 $O(N)$ で通るようだ。 これも実装してみた。実行時間は少し速くなるくらいだったが、やはり速くはなるので 覚えておくと良いのかもしれない。
G だが、この最初の感想を書く前に LowLink を改造して関節点の分解される連結成分数を出すように 工夫していたのだが、実はそれ自体のアルゴリズムは正しかったようだった。 間違っていたのは LowLink そのもののアルゴリズムであり、$\mathrm{used}[v] = \mathrm{true}$ のときに、 $\mathrm{low}[u] = \min{(\mathrm{low}[u], \mathrm{low}[v])}$ と何故かしていて、 本当は、 $\mathrm{low}[u] = \min{(\mathrm{low}[u], \mathrm{ord}[v])}$ であった ( $u$ が現在のノードで $v$ が接続先のノード )。
なんかこのように間違ってても通るような条件が多かったみたいだった。 二重辺連結成分分解とかはこれで通っちゃうのかな。橋を求めるのには問題ない条件だったみたいなのか？ 関節点の方はきちんと間違っていたので直せてよかった。
そんなこんなで書いていたコードをそこだけ修正したら AC した。 連結成分数を求めるやり方は想定解と同じだった。 黄色 Diff なのだが、やっぱり G 問題でも Diff が低いとやっぱり明確な答えが浮かんでくるものなんだなぁ。
あとは、G を解くついでに二重頂点連結成分分解も実装してみた。これはかなり実装に苦労したが、 いろいろなサイトのおかげで実装することができた。これがあれば各ノードがどれだけのグループに属しているかを 見るだけで分解される連結成分数がわかる。 Block Cut Tree は実装していないが、暇があったら実装してみようと思う。ここまで作っていれば そこまで苦労しないはず(本当?)・・・
(2023/12/29 17:35)