第八回 アルゴリズム実技検定

満点だった。

L - K番目の絶対値

総和の絶対値が$D$以下であるような連続部分列を数える問題が解ければよさそう。累積和$S_i = A_1 + ... + A_i$上で言い換えると各$i$について$|S_i-S_j| \le D$であるような$j < i$を数えればよく、これは$S_0, S_1, ..., S_{i-1}$の中で$[S_i-D, S_i+D]$に含まれるようなものを数えることに等しい。数え上げを${O}(N \log N)$で解くと、全体で${O}(N \log N \log \sum_i |A_i|)$。

順序対を数えることにすれば尺取りでできる。確かに。

M - バランス

SoundHound Inc. Programming Contest 2018 Masters Tournament E - + Graph

O - 色分けトーナメント

• トーナメントは$2 \cdot 2^N-1$頂点の完全二分木とすると、制約$(W_i, L_i)$は$W_i$と$L_i$のLCAまで$W_i$と$L_i$が勝ち上がって$W_i$が勝つこととみなせる。
• ある選手を青に塗ると決めても赤に塗ると決めても有効な塗り方は同数ある。（どの有効な塗り方についても、すべての色を反転したものが有効な塗り方であるため。）

$\operatorname{dp}_v[x] =$頂点$v$を根とする部分木に属する左から$x$番目の選手の色を決め打った時に、部分木$v$に属する選手の塗り方で（部分木$v$に含まれる制約を満たし、かつ）$v$が勝ち上がるようなものの総数、とする。$\operatorname{dp}_v$は$v$の子を$c_1, c_2$として$\operatorname{dp}_{c_1}, \operatorname{dp}_{c_2}$から線形で作れるので、下から処理していけばよい。根に関する$\operatorname{dp}$の総和を2倍したものが答えになる。

各深さの$\operatorname{dp}$の長さの総和はちょうど$2^N$になるので、全体の計算量は${O}(N 2^N + M)$。