週記(23/04/16)：Euler Tour

今週のまとめ

久しぶりのトレラン。明神山へ
ABC294バチャ。久々の青パフォ相当
Euler Tourをライブラリ化

です。

(本文中にABC 082 D, 294 E-Gの解法を含む話題が出てくるのでご注意ください。)

4/16(Sun)

水Diffの練習でABC089「D – Practical Skill Test」を解きました。

今だとC問題で出て茶Diffから緑Diffくらいかなーという印象。

昼から運動をすべくトレランへ。近くの明神山(藤井ルート)へ行ってきました。

JR大和路線三郷(さんごう) 駅から出発してしばらく行くと登山口へ。

ここから一気に430mで130mほど登ります。運動不足の体にはきつい…。
登りきると多少のアップダウンはありますが、きついところはなく1時間ほどで山頂へ。

奈良県を一望できます。天気も良くトレラン日和でした。

そのまま西に進み道明寺駅で終了。19kmほど動き回って良い運動になりました。

4/17(Mon)

ABC294のバーチャル参加

69分6完、パフォーマンス1620相当で久々の青パフォを出せました。ザ・典型と言える問題セットで取り組みやすかったです。

「E – 2xN Grid」はdequeでランレングス圧縮した要素をもって片方をpop_frontしながらもう片方を追い越さないように取り出してみていけばOK。

Eにしては簡単だと思いましたが茶Diffなんですね。それもすごい話。

「F – Sugar Water 2」は大きい方からK番目の要素を「[math]X[/math]以上が[math]K[/math]個以上になる最大の[math]X[/math]」を求める問題と読み替えてXを二分探索。個数のカウントで少し悩みつつもARC037「C – 億マス計算」を思い出しながら

[math]\dfrac{A_i +C_j}{A_i+B_i+C_j+D_j}\geq X[/math]

は

[math](1-X) C_j + X D_j \geq -(1-X) A_i + X B_i[/math]

と[math]i, j[/math]を分離した形に変形できるので

[math]X[/math]を決める
[math](1-X) C_j + X D_j[/math]をソート
[math]i=1,\dots,N[/math]ごとに[math]-(1-X) A_i + X B_i[/math]以上になる[math]j[/math]をカウント

とすればOKです。

「G – Distance Queries on a Tree」もEuler Tourを使えば解けそう！というところまでは気づいたものの書いたことがなくググっている間に終了。

4/19(Wed)

水Diffの練習でABC082「D – FT Robot」。

計算量の見積もりが甘いままTLEを2回出してしまったのは反省…。[math]T[/math]の出現回数の偶奇で左右か上下の移動に分かれるのでx, y独立に考えることができますね。

4/20(Thr)

Euler Tourをちゃんとライブラリ化しようと思いmaspyさんの「Euler Tour のお勉強」を見ながらお勉強。たしかに辺を移動するごとに情報を書き込んでいると思うと理解しやすいです。

Euler Tourで情報を持つと部分木が配列上の連続した範囲になるので区間クエリに帰着できると。なるほど。

部分木のサイズ
あるノードが部分木に含まれるかの判定
部分木の辺、頂点の重みの合計

が出せて、さらに辺や頂点の重みの変更もセグメント木で対応できます。

さらに賢いのはLCAも根からの深さを持ったEuler Tourを見ると

頂点[math]u[/math]から[math]v[/math]へのDFSパス上で最も根に近くなるノード

がLCAになるので区間最小クエリに帰着できるんですね。LCAが分かれば任意の2ノード間のクエリも処理できるようになります。

Euler Tourの賢さに感動しながら実装して「G – Distance Queries on a Tree」もサンプルを合わせてSubmitするとRE/WAの嵐。なぜ…。

4/22(Sat)

Euler Tourの続き。書き込む時刻や範囲の始点、終点や開/閉区間、入力の辺が「親⇒子」だけなのか「子⇒親」も混在するかなど色々とバグりポイントがありました。

Library checkerやAOJの

がなかったら実装しきれなかったと思います。ようやく「G – Distance Queries on a Tree」も通って一区切り。

夜に下の子の顔が急に腫れてしまってドタバタ。21時には間に合わなかったの後からUnratedでABC299に出ようかと思ったらDDoS攻撃で今回もUnratedだったんですね…。

AHC020も延期になって影響が大きくなってきてますね。ユーザとしてはAtCoder社を応援しながら見守ります。

前週の週記: 「幻の水青反復」
翌週の週記: 「ABC300!」