木上クエリコン 感想
Tester でした.
問題文とかかなり修正したんですが読みやすかったかな.
A - compαctree
ジャッジが詰まらないよう$ Qを小さくしたので変な制約になっています.
正直$ Q = 1にしたかったんだけどクエリコンなのでね.
B - tri-βutree
ダブリング LCA を python3 で書いてみたらかなり遅くて(python3 7115 ms / PyPy3 2731 ms)厳しさを感じた.
C - γatheree
距離$ 1以下だと$ \Theta(Q)解法があります(多分,厳密な証明が書けてない(お気持ち証明)).
距離$ 2以下だと$ o(QlogN)は流石に不可能かなぁとか思ってる,出来ますか?
D - aδδitivee
親の顔より見た ET.
遅延セグ木を抽象化すると書くのが楽.
ところで遅延セグ木に載せる関数$ gについてなんですが上の$ g1, g2の書き方はよく見るんですが$ g3は全く見たことがなくて,ぼくは最近これに変えました,ちょくちょく楽になります.
code:cpp
auto g1 = [](monoid a, operator_monoid b) { a <- b; };
auto g2 = [](monoid a, operator_monoid b, int len) { a <- (b <- len); };
auto g3 = [](monoid a, operator_monoid b, int l, int r) { a <- (b <- (l, r)); };
2020/09/27 追記:そもそも区間の情報はモノイドのほうが持つべきだと考え直しました。
E - K-ary εxtrεεmε
B のテスティングをしてたら一般化出来たので提案しました.
部分木辺加算クエリを載せるという案も出したんですが流石に冗長かと思ったので流しました(やるだけなので).
テスター解は HLD + 遅延セグ木 で $ \Theta(Nlog^2N)
ライター解は top tree で$ \Theta(NlogN),らしいんですがぼくは top tree を持っていない(理解していない)のであんまりわかってない(たぴ).
木の steiner tree を高速に求める問題で,論文ありそうだなと思って探してみたんですが見つかりませんでした.もしあれば教えてもらえると嬉しいです.
F
9.26 に急遽生えた問題,link/cut 用.
ぼくはダイコネでチェックするくらいしかできていません>< 難易度$ 6がネタバレすぎる.
コンテスト前の感想
普通に一時間くらいで全完されそうだな~(beet さんとかうしさんとか)とか思ってる.
cpp 等以外に異常に厳しいコンテストになってしまってちょっと申し訳ないな.
コンテスト後の感想
最初 clar が$ 4つ来たんだけど問題文の雑な部分の指摘で,本質的な欠陥ではなかったので一安心(ただこういう部分はテスターが指摘しないと行けない部分だったと思うのでかなり反省です,ナイス反省!).
ところで clar の返答案を DM で渡したら語尾についてた "とか" が残っててびっくりしてしまった.
あと問題文の修正を二人同時にしてしまったせいで修正の修正をする羽目になりました,こういうことをするときはちゃんと事前にどちらが修正するのかをしっかり確認するようにしましょう.
C があまり解かれていなかったんですが,これは割と予想通りでした.
E が Writer とは別の方針(?)の HLD 解法で通されていて,さらにすごく簡潔で完全敗北です.
よくみたら本質的に B と同じ解法でまずいですね(まずいですね).
完全敗北
動画作りたかったので E の解説動画作りましたが,普通に微妙な解法なのでかなしい