CodeChef - Killing Monsters

• 問題
• AC

それぞれのモンスターについて、どの時点まで生きているかが高速に求まればよい。

クエリ$(x, y)$が与えられたとき、$x$に（bit集合の意味で）包含されるようなすべての番号のモンスターから$y$を引くことになる。

• $f[t] :=x =t$であるようなクエリの総ダメージ。
• $F[t] :=x \supseteq t$であるようなクエリの総ダメージ。

とするとき、関心があるのは$F$で、$F$は$f$からゼータ変換で得られる。各クエリを処理した時点での$F$が配列として$q$個分すべて求まっているとすると、それらをクエリ番号に関して二分探索することで各モンスターがどの時点まで生きているかがわかる……が、$F$を毎回作ると間に合わない。

そこで、クエリを$B$個ずつに分割して、$q/B$個のクエリ番号に対してのみ$F$を作ることにする。 モンスター$k$がどの分割まで生きているかを線形探索（あるいは二分探索）で調べて、そこからはモンスターが死ぬまでクエリを一つずつ見ていく。

前半の計算量は${O}((q/B) n\log n)$で、後半は${O}((q/B + B)n)$。$B = \sqrt {q \log n}$とすると全体の計算量は${O}(n \sqrt {q \log n})$となる。

CodeChef - Path containing K Nodes

• 問題
• AC

$u$が$v$の先祖かどうか調べる方法を思い出す:

• 各頂点$v$にDFS順序で行きの番号$\operatorname{pre}[v]$と帰りの番号$\operatorname{post}[v]$を振る。$u$が$v$の（広義の）先祖である必要十分条件は$\operatorname{pre}[u] \le \operatorname{pre}[v]$かつ$\operatorname{post}[v] \le \operatorname{post}[u]$が成り立つことである。

$K$個の頂点のうち、$\operatorname{pre}[u]$が最大であるような$u$と$\operatorname{post}[v]$が最小であるような$v$を選ぶ。この二つが同一のとき、上の性質を考えると$K$個の頂点はすべて$u=v$の先祖なので、一つのパス上にある。

$u \neq v$の場合を考える。パスが存在するならこの2点が（極小のパスの）端点になっているので、$K$個の頂点が$u$または$v$の先祖であり、かつ$u, v$のLCAの（狭義の）先祖ではないことが必要十分条件である。

CodeChef - ForbiddenSum

• 問題
• AC (fractional cascading)
• AC (永続セグメント木)

まずは与えられた列$A_1, ..., A_N$のForbiddenSumを求めるうまい方法を考える必要があるが、この時点でわからなかった。Editorialより。

• 列$(S_i)$を$S_0 = 0, S_{i+1} = \sum_{A_i \le S_i+1}A_i$で構成する。$S_{i+1} = S_i$が成り立ったら$S_i + 1$がForbiddenSumである。

理由を考える。簡単のために$A_1 \le ... \le A_N$としておくと、$S_i$は$(A_i)$のprefix sumとして表せるので、右端を$r_i$で表して$S_i = A_1 + ... + A_{r_i}$としておく。次のことを示せればよい:

• $A_1, ..., A_{r_i}$のsubset sumによって常に$S_i$以下のすべての非負整数が作れる。$S_i + 1$は作れない。

帰納法で示す。$i=0$の場合は明らか。$i-1$について成り立つとする。このとき、$\{A_{r_{i-1} + 1}, ..., A_{r_i}\}$のすべてのsubset sumを昇順に並べると、隣り合う要素の差は$S_i$の定義より$S_{i-1}+1$以下である。また、帰納法の仮定より$\{A_1, ..., A_{r_{i-1}}\}$のsubset sumによって$S_{i-1}$以下のすべての非負整数が作れて$S_{i-1}+1$は作れない。したがって、前半と後半の集合を合わせると、$(A_{r_{i-1} + 1}+ ...+ A_{r_i}) + S_{i-1} = (A_{r_{i-1} + 1}+ ...+ A_{r_i}) + (A_1 + ... + A_{r_{i-1}}) = S_i$以下のすべての非負整数が作れて$S_i +1$は作れないことがわかる。

また、$S_{i-1}$から$S_i$を求めるとき、増えるなら常に$S_{i-2}$以上増える（$S_{i-2}$より小さい数は$S_{i-1}$の時点で加算されているため）ので、フィボナッチ数以上のオーダーで増加する。したがって、$(S_i)$は${O}(\log \sum A_i)$で停止することになる。

与えられた区間に対して列$(S_i)$を構成することは、区間$[L_i, R_i]$について$A_{L_i}, ..., A_{R_i}$のうちの閾値以下の数の総和を求める計算を繰り返すことに相当し、これらは二次元のrange sum queryとみなせる。例えばfractional cascading付きの領域木なら${O}(\log N)$で処理できるので、クエリあたり${O}(\log N \log \sum A_i)$となる。永続セグメント木でも同じことができる。