ooooooo-
1872->1920
■A - Median?
ソートします
■B - Distance Between Tokens
abs(x1-x2)+abs(y1-y2)
■C - Max - Min Query
mapでやった
■D - FizzBuzz Sum Hard
Σall-Σax-Σbx+Σabx
■E - Distance Sequence
単純なdpだけど単純にやると間に合わないので累積和で高速化
k=0がコーナーケース
■F - Operations on a Matrix
クエリ先読み
操作３に影響する操作２を先に調べておく。
少し前にcfで覚えたテク。
■G - Swap Many Times
愚直+工夫+愚直
■Ex - We Love Forest
割と簡単。行列木定理は第二回日本最強プログラマー学生選手権で既出なので知識としては持っている。
f[i]:=集合iを木にする通り数
g[i][j]:=集合iが森で、森を構成する辺の数がj
としてdpを行う。
fが行列木定理そのものなので、gをどうやって求めるかを考える。
これは典型でまず集合iから代表(v)を選ぶ。
g[i][j] = Σg[i^k][j-(popcount(k)-1)] * f[k](v∈k)
とすれば良い(配列外参照に気をつける。)
