CF #499

開始前:
辛いカレーをお腹いっぱい食べてしまった
6問か

C:
まずCから開く
読めない
読めた
無
(8)

D:
読めた
マージテクで終わりだな
UnionFindのほうが楽かな
0になるやつの親と1になるやつの親と普通にやるとどっちになるか持てばいいな
ここで実装で何故か混乱する
今頭が働いてないのでやめたほうがいいなとなってAに行く
(35)

A:
読めない
読めた
無
たしかクソしょうもないバグで時間とかした、こんなのバグるか?
(46)

B:
読めない
読めた
無
WA on 1 (は?)
よく見るとT回しか回してない
書き直して再提出
WA on 1 (は?)
よく問題文を読むと、-1を出力してはいけなかった(下の方に書いてある intじゃないとhogehogeみたいなのを見て勘違いしていた)
AC
(65)

D:
頭が働いてなさすぎてうつ病
普通にマージテクのほうが楽なので書く
普通にかけた
(83)

E:
順位表見たらメチャクチャな場所にいたので嫌な気持ちになる
F解かれてないしEだな
データ構造じゃん
まずoのやつを含む最小の直方体を考える
それにクエリが入ったらo
xにできるかは?
そいつをoだとおもって追加したときに内部にxがいるか?
3次元点存在クエリになった
z軸をtime sweepすると、2次元で点add,長方形countになる
あらかじめ点がわかってるやつなので、マージソートのやつでいいな
ライブラリにあるので貼る
(113)

順位表見たらhack横行しまくっててこわい
見直して終了

反省:
Dまでで信じられないパフォーマンス出したのはカレー食べ過ぎたせいなのでコンテスト直前に食いすぎない(事前に食べておく)
言い訳がましくて嫌だけど明らかにパフォーマンス落ちるから気をつけないと

F:
どうせいい感じに多項式持ってFFTだろうって感じだけど、まずcutされた頂点数を固定すると割り振り方がクッソ自明になることに気がつく必要がある
これは fv(x) = fa(x)*fb(x)*fc(x)*x + 1 って感じになるんですが
とりあえずline graph ですらこれが解けないとどうしようもないのでそれを考えます
(((1*x+1)*x+1)*x+1 .. みたいな感じになってこれは自明
line graph にちょっと増やしたようなグラフだと各xの部分がなんか一般の多項式になる
(((1*a+1)*b+1)*c+1 ..
abcd + bcd + cd + d + 1
これはcd (ab+b+1) + (d+1) とかなので半分(多項式の次数の和で分けないとだめかも)ずつに分ければできる
で、一般の木の場合にどうするかというとだいたい一緒で、とりあえずHLDします
で、heavy path の部分は (((1*a+1)*b+1)*c+1 .. みたいなformで持っていく
その時light から入ってくるfu(x) は上のようにexplicitに評価する
計算量は、各heavy path の一番上でexplicit に計算するので、
vでexplicitに計算するとき、s = sz[v] とすると O(s log^2 s) でできるので
lightを降りた段数でまとめて数えると全体で O(n log^3 n)
重すぎィ!

これってこの形以外で出るのか?(出ないなら今後出たらこっからコピーしてこよう)
HLDでマージをなんとかするのは普通だけどそもそもline graph で D&C っていうのがちょっと面白かった