2021年1月26日火曜日

CodeChef - Killing Monsters

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

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

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

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

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

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

2021年1月22日金曜日

CodeChef - Path containing K Nodes

uuvvの先祖かどうか調べる方法を思い出す:

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

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

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

2021年1月10日日曜日

CodeChef - ForbiddenSum

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

  • (Si)(S_i)S0=0,Si+1=AiSi+1AiS_0 = 0, S_{i+1} = \sum_{A_i \le S_i+1}A_iで構成する。Si+1=SiS_{i+1} = S_iが成り立ったらSi+1S_i + 1がForbiddenSumである。

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

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

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

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

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