チーム連 7/4 (2017 ACM-ICPC, Asia Daejeon Regional)

BCDEFGIK 8完
ひさびさに顔を合わせてチーム練した　ついでに本番っぽく一台のPCでやった
L, Hは冷静に考えたら解ける問題だった
これのあとでこどふぉに出たら脳が機能を停止していて、反省...

B (Md, 02: 07)
C (Md, 00:32)
D (Md, 00:18)
E (のん, 02:43)
F (番兵, 01:01)
G (のん, 04:48)
I (Md, 03:09)
K (番兵, 03:25)

B
枝狩り全探索

C
次数が小さい順に並べてDP

D
一回操作をしたあとの数が729以下に抑えられるので、一周するか停止するまで操作を繰り返す

E
各辺について、自分より小さいコストの辺だけをつかった部分グラフについて今見ている辺の両端を非連結にしたい
最小カットに落ちる

F
頑張って再帰的にやると通るらしい

G
座圧

I
周期pを固定したときにkをどこまで伸ばせるかはにぶたんできる
にぶたんの各判定はロリハをつかってO(n / (pの長さ))なのでpを全探索すると考えれば調和級数でO(nlogn)の気持ちになる
pを全探索 + kをにぶたんするとn * (調和級数のlogn) * (にぶたんのlogn)に落ちる

K
知らず

7/10追記
H
NTT

L
それぞれのグラフについて
dp[i][j]: j回目に頂点iにいるときのコストの最小値
をj <= 200000くらいまで求めておいて、最後に組み合わせる