チーム練(2018 nakhon pathom)
8完。悪くはないけど後一問通したかった
D(Md, 00:19)
G(番兵, 00:58)
C(Md, 01:29)
H(のん, 01:43)
E(Md, 02:26)
K(のん, 03:05)
J(Md, 03:31)
F(のん, 04:26)
全体的にTLが厳しかった
Jを通した後は、Aを詰めたら解けるけど実装クソ重いしキューが詰まってるからやることがないなあとなってデバッグを手伝ったりしてた
ノーペナで通せた問題がCしかない...
軽く解説
A
柱が高い順に見ると木が生やせて、木のパス長をLCA使ってlogで答える問題に落ちる。
同じ高さの柱をどう扱うべきかあんまりわかってない
B
わからん
C
遷移出来るところに辺を生やすとDAGができる
最大長のパスをDP
D
貪欲
E
ソートしておいて
dp[i][j][k]: i番目までみてj回変更して、i番目の要素に+(k-1)したときの最大長
F
ゆきのんが実験したらフラクタルが生えた すごい
G
SCC
H
CRT
I
わからん
J
各項を10^-15で割るとx^(1/3)の微分になるので、微分を足してから10^-15を掛ける
出力だるすぎる
K
endlforces
詳しくは知らないけどセグ木にのせてセグ木上のにぶたんを使いつついい感じに管理するっぽい
L
TLが鬼
線形でdp出来るけど実は普通に1辺の長さをにぶたんしたほうが早い?
二次元累積和を作っておいてにぶたんで解ける
(追記: 入力が遅かったらしい ただそれでもTLはカツカツ。どうして.....)