titiaのノート: yukicoder contest 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~

2025年6月10日火曜日

　AHCを頑張ろうと思っていたのでAだけAC。

No.3166 [Cherry 7th Tune *] 桜の守人

　解説AC。

　二分探索は分かったが、その後分からなくなり解説を見た。

　分からなくなってしまったのは、全ての整数座標、もしくは整数/2の座標の頂点が守られているか？　と考えてしまったせいだった。座標圧縮が必要なはずだけど……などと考えて混乱。

　守る範囲は区間なのだから、[x-p,x+p]に全ての区間が含まれているか？　と考えるのは自然。これは、イベントソートを使って解くことができる。

　自力AC。そこそこ苦労したが解けて良かった。

　クエリ先読みを使い、クエリ2の削除しないものとして、最終的なAの配列を求める。

　クエリ1で、何の直前に何が付け加わるか？　というのが与えられている。これをなぞるのは、木構造でDFSして求めていく感じになる。

　あとは、Bit_indexed_tree上の二分探索を駆使したら解けた。

　自力AC。

　図を描いて相似を見つけたら解けた。空間図形には苦手意識があるため、図を描いた後しばらく分からなくて焦った。