脳log[20251206]

2025年12月06日 (土) [AtCoder] 今日は AtCoder Beginner Contest 435 があった。終了１分前にバグの原因に気がついて修正して提出してコンテスト終了後にまだジャッジが進んでいるのをドキドキで見つめていた。それが E 問題。今日は F 問題までそれなりの早さで解かないといけないセットだったらしいです。■A 問題「Triangular Number」。三角数？ N*(N+1)/2 ■B 問題 No-Divisible Range。愚直に、やります。■C 問題 Domino。どこまで倒せるかをメモしながら左から倒していく。違った。どこから倒せないかをメモしながら左から倒していく。■D 問題 Reachability Query 2。黒いマスを始点にして逆向きに辺をたどって通り道の頂点も黒く塗っておく。どの頂点も高々１度しか塗られないし、塗られたときにしか遷移しないので、全体で N+M に比例した処理。クエリ１で与えられる頂点がすでに黒いかどうかを確かめずに無条件に探索を開始したら TLE×2 を食らった。テストケースがいい仕事をしている。多くの辺を集めている頂点が何度も始点になったら、たとえその次の頂点が黒で探索がストップするとしても、最初の１ステップが O(M) で死ぬ。■E 問題 Cover query。区間の併合。BIT で区間の始点を管理した。座圧が必要。とてもやっかい。時間をかけて丁寧に書き何度も読み返し２歩進んで１歩戻る慎重さ……というか自分が今何をしているかを思い出す時間を確保しながら書いていた。とてもやっかい。最後まで見つからなかったバグとは何か。BIT で管理している区間の始点の集合が壊れている。単調増加のはずなのに途中で減少したりしていて、それでは BIT 上の二分探索ができない。なぜ壊れたか。ある位置を含みうる区間(始点がある位置以下にある直近の区間)を BIT から検索していたのだけど、ある区間の始点を基準にして、その位置を含みうる直前の区間の始点を検索していた。何が見つかるかは火を見るより明らかなんだけど、座圧をしているとデバッグプリントの解読が難しくて思い違いになかなか気づけない。十分に早い SortedSet があれば座圧は必要ないのになあ。遅延セグメント木を使う解法と、BIT を使っていながらもっとシンプルな解法があるみたいなのと、自分と同じような解法ながらずっと早く提出している人がいた。要するに、考えが足りず、実装も下手だった。これが現在の自分。■F 問題 Cat exercise。実装前にいろいろ考えた。移動を開始すると移動可能な範囲は必ず左右に２分割される。左右のどちらに移動させるかは選べる。移動先の高さを選ぶ意味はあるだろうか。……ない。じゃあ左右の移動先を効率良く見つけるためにセグメント木と値から添字の逆引きインデックスを用意すれば終わり。E 問題より簡単。「……ない」の点々部分について書く。移動先を選ぶということは、(1)優先される移動先を予め取り除いておく、(2)移動範囲を予め制限しておく、のどちらかを実行することになるのだけど、(1)をするくらいなら優先される高いタワーに寄り道をする方が移動距離が増える。(2)を実行するのは今ではなく制限のために取り除くタワーの隣に移動してきたときでいいし(つまりこれが左右の移動先を選ぶというときの実際の操作)、そのときを待つ方が移動距離が伸びる。■■■F 問題。O(N) で解けると読んだので考えてみた。頭の体操。こういうときに使えるデータの持ち方を知っている。AtCoder を始めたごく初期の日記に書いてある(脳log[20190907p01] AtCoder Beginner Contest 140 E問題)。結局、左右にある直近の現在より低いタワーの位置が定数時間でわかればいいのだ。高さ N から降順でやるのに失敗したので逆に、高さ１から昇順でやることにした。左右にあって最も近くの現在より高いタワー(左右１つずつ)に情報を伝えていく。提出 #71557988 (AC / 165 ms)。