2019-12-15
■ 第2回全国統一プログラミング王決定戦 参加記 (冬休み2日目)
正式名称をちゃんと書いてみました。
C
N^2 log N、4secとは言え流石にやばくない？と言い続けて線形解を探してしまった (AtCoderのジャッジサーバーは速い！(素振り))
E
やることは実家 (長方形sum + setで区間管理) なんですが、実装の仕方がヤバすぎてバグった... (大反省)
G
解法は簡単で実装も簡単 (完)
ちゃんと書くと、dp[u][v] = 木に辺u-vがあり、頂点uをsubtreeに加えることが決まっているとき、辺u-vを切断したときにできる頂点vを含む方の木から最適に頂点を0個以上選んだ時に辺の重みはいくつ増えるか を全方位木DPで計算 (これは簡単) し、sum[v] = dp[v][*]のsumとします。
すると、クエリ(a,b)に対する答えは、a-bパスをa-v1-v2-...-vk-bと書くと、sum[a]+sum[v1]+...+sum[vk]+sum[b]-dp[a][v1]-dp[v1][a]-dp[v1][v2]-dp[v2][v1]-...-dp[vk][b]-dp[b][vk]+(a-bパスの重み)になって、これはどれも根からの累積和 + lcaだけで計算可能です。
何も知らないけどtoptreeとかいうの強すぎる
D,F,Hはどれも教育的なので後でちゃんと解く
結果は4位でした。頭じゃなくて精進量で負けたと思えるコンテスト、最高なのでこれからも続けていきたい
今回の懇親は渾身ではなかったです (<-これはなんですか？)
2018-2019 ACM-ICPC, Asia Xuzhou D
何も考えないとdp[i][j][k]みたいな配列に対してN通りの遷移を考える必要があって4乗になりTLEする。
dp[I][J][K] <- dp[i][j][k] (a[I]=a[J]=a[K] & a[i]=a[j]=a[k] & A_{a[i],a[I]} = 1) の遷移を睨むと、
dp[i][*][*]の更新はdp[(i未満)][*][*]のsumだけ分かっていればできるので、(新たに追加されるのはa[i]なので、A_{*,a[i]}=1なる*だけ取り出して2次元累積和する) これで3乗になる。
(例えばdp[i][x][x]とdp[i][y][y] (a[i]=a[x]=a[y]) を計算する上で大きな差がない (同じグリッドの違う領域のsumを取っているだけ) ということに注目すると解けたような気もする...?)
