2020年10月30日金曜日
2020年10月23日金曜日
ARC 093 E - Bichrome Spanning Tree
$X$がMSTの重みの総和より小さい場合は実現不可能である。
$X$がMSTの重みの総和に等しい場合、MSTを作れるような塗り方を数えればよい……が、そもそも、だいたいの塗り方においてMSTが作れるように見える。というのも、MSTに使える辺が全部白または全部黒になっているような塗り方を除けばMSTができるからだ。つまり、MSTに使われうる辺が$K$本あるとき、$K$本全部を一色で塗る$2\cdot 2^{M-K}$通りの塗り方以外はMSTを作れる。あとは$K$が求まればよい。これは最小全域木$T$を作った後、$M$本の辺$e = (u, v)$について最適性条件を満たせるか判定すれば数えられる。具体的には、$e$の重みが（$T$上の）パス$u - v$上の重みの$\max$以下であれば$e$はMSTに使える[1]。変更がないので、$\max$クエリはダブリング等で処理できる。（制約を$N=10^5$と勘違いしていた。愚直でよい。）
$X$がMSTの重みの総和より大きい場合、MSTに使われうる辺は全部白または全部黒に塗られていなければならないので、とりあえず白に塗られているとする。この時、黒に塗られていてMSTに使えない辺が全域木に少なくとも1本含まれていなければならないが、その1本以外は白い辺も自由に選べる。したがって、MSTに対して辺を挿入してそれによってできたサイクルから別の最大辺を削除して全域木を作った時に、重みの総和が$X$になるものを考えればよい。これにはやはり木上の$\max$クエリで答えられる。「MSTの辺と交換した時の重みの総和」が$X$になる辺を$p$本、$X$より大きくなる辺を$q$本としたとき、$p$本から少なくとも一つを黒い辺にする必要があって、$q$本は好きにぬってよいので、塗り方は$(2^p-1)2^q$通り。白の分と黒の分を足すと$2\cdot(2^p-1)2^q$通りとなる。${O}((M+N)\log N)$。
厳密な証明がよくわからなかった。
path optimality condition ↩︎
2020年10月17日土曜日
ABC 180 F - Unbranched
「最大サイズがちょうど$L$」の代わりに、$f(n, m, l) :=$連結成分のサイズが$l$を超えない$n$頂点$m$辺のグラフの数、を数えることにして、$f(N, M, L)-f(N, M, L-1)$を答えとすればよい。
次数2以下の連結成分はパスかサイクルしかないので、この2つを作りながら数えていくDPができそうだが、頂点の順番をどうするかが問題になる。順番を固定した上で最後に定数を掛けるのはうまくいかなそうだし、固定せずに挿入していくDPもサイズの上限に関する制約を扱うのが困難に見える。
こういう時の典型テクニックの一つとして、「選ぶ頂点の一つは、残っているものの中でもっとも小さい番号とする」というルールを追加してグループ（この場合は連結成分）を作っていくというものがある。この場合はこれがうまくいきそうだ。
$\operatorname{dp}[x][y] :=$頂点を$x$個、辺を$y$個使ってできる（条件を満たす）グラフの総数
とする。残った$N-x$個の頂点からサイズ$s$のパスグラフを作る時、連結成分のうちの1つの頂点は残った頂点の中でもっとも番号の小さいものと決めているので、残りは$N-x-1$個から$s-1$個を選ぶことになる。ラベル付きパスグラフの総数は$s!/2$（ただし$s=1$の場合は例外）なので、
$$ \operatorname{dp}[x+s][x+s-1] \mathrel{{+}{=}} \frac{s!}{2} \binom{N-x-1}{s-1} \operatorname{dp}[x][y] $$と遷移できる。サイクルを作る場合も同様で、ラベル付きサイクルグラフの総数は$(s-1)!/2$（ただし$s\le 2$の場合は例外）なので、
$$ \operatorname{dp}[x+s][x+s-1] \mathrel{{+}{=}} \frac{(s-1)!}{2} \binom{N-x-1}{s-1} \operatorname{dp}[x][y] $$と遷移する。ただし、自己ループである$s=1$は許されないことに注意。
2020年10月12日月曜日
CodeChef October Challenge 2020 - Compress all Subsegments
区間$I$に関する$f$の値は、$(A_i)_{i \in I}$中のhighest set bitの位置を$k$として、$k$が立っている数が$(A_i)_{i \in I}$に何個含まれるかでだいたい決まる:
- $k$が立っている数が1個でそれ以外が0個の場合、その数自身になる
- $k$が立っている数が奇数個の場合、上の場合を除いて$2^k$になる
- $k$が立っている数が2個でそれ以外が0個の場合、不定
- $k$が立っている数が2個でそれ以外が1個の場合、不定
- $k$が立っている数が2個でそれ以外が2個以上の場合、0にできる
- $k$が立っている数が4個でそれ以外が$0$個の場合、不定
- $k$が立っている数が4個でそれ以外が$1$個以上の場合、0にできる
- $k$が立っている数が6個以上の偶数の場合、それ以外が何個でも0にできる
まずは、$k$が立っている数が偶数個の時に常は$f$の値が0になり、$k$が立っている数が奇数個の時は常に$2^k$になるとして、偶奇のみに注目して計算する。そして、後から3, 4, 6のパターンを別に数えて補正する。
前半パートは、$i = 1, 2, ..., N$についてそれぞれ区間$[1, i], [2, i], ..., [i, i]$に関する結果の和を求めるとよい。この際、
- $\operatorname{odd}[x] :=$ highest set bitが$x$で、$x$が立っている数を奇数個含むような区間の数
- $\operatorname{even}[x] :=$ highest set bitが$x$で、$x$が立っている数を偶数個含むような区間の数
を保持しながら走査するとまとめて計算できる。${O}(N\log \max A_i)$。
2020年9月14日月曜日
CodeChef September Challenge 2020 - Chefina and Swap
0-basedで考える。列$(S_i)$を$[0, m), [m, N)$に分けた時に、左右の和を等しくするようなスワップが何個あるか数える。まず、右の和のほうが大きいことが有効なスワップが存在する必要条件である。右の和が左の和より$D(m)$だけ大きいとする。このとき、$D(m)$が偶数なら左の区間の$S_i$と右の区間の$S_{i+D(m)/2}$を交換すると和が等しくなる。添え字$i$が有効である条件は$0\le i < m, m \le i+ D(m)/2 < N$で、これは$\max(0, m-D(m)/2) \le i < \min(m, N-D(m)/2)$とまとまる。この区間の長さが有効なスワップの数に等しいので、すべての$m$について足せばよい。ただし$D(m)=0$の場合は区間をまたいで数を移動する必要がないので特別扱いして、左の区間内と右の区間内のスワップの総数を数える。
さて、$0\le D(m) < 2N$が必要なことを考えると、有効な$m$は多くないはずだ。$m$が増加するとき、$D(m)$が正から負に変わる地点を考えると、この地点は全体の半分よりは右にあるはずだから、その付近では$m$が$1$動くごとにおおむね$2 \cdot N/2 = N$程度は$D(m)$が変化することになる。したがって、高々3つ程度の$m$について数えれば十分という見積もりができる。実装の際は$D(m) \ge 0$であるような最大の$m$を二分探索などで求めておいて、そこから下っていけばよい。
CodeChef September Challenge 2020 - Find XOR
仮に$K=0$を尋ねることが可能だとすると、$K=0$による総和と$K=2^e$による総和の差は$(A_i)$の中で第$e$ビットが$1$であるものの総数-第$e$ビットが$0$であるものの総数に等しい。これを利用すると各桁の立っているビットの数がわかるので、偶数ならXORを0、奇数なら1とすればよい。
実際には$K\ge1$という制約があるが、代わりに全ビットを反転したもの（=$2^{20}-1$とXORを取ったもの）を$K$とすれば同じことができる。
また、素朴にやると$K=0, 2^0, 2^1, ..., 2^{19}$を全部尋ねる必要があってクエリの回数が21回になってしまう。$K=2^0, ..., 2^{18}$を調べて$K=0$の場合の生の総和と比較することで、$K=2^{19}$は省略できて20回になる。
$N \le 10^3 < 2^{10}$だから、11ビットくらいで区切れば2つの質問を1つのクエリでできそうと思ったが、分離がかなり複雑になりそうなので方針を変えた。
CodeChef September Challenge 2020 - Rotate the Polyline
$v_i=P_iP_{i+1}$とした時、原点を通る直線$l$によってできた2つの（境界を含まない）半平面のそれぞれに連続した添え字のベクトルが並んでいれば、$l$に直交するベクトルが答えということになる。ただし、答えとなるベクトルは十分に原点に近い格子点を通る必要がある。
整数性の条件をいったん忘れると、直線$l$を表すベクトルの候補$u$は各$v_i$から偏角を左右に微小にずらした$2N$通りが考えられる。そこで偏角順の尺取り法をして、それぞれの$u$から偏角が$180 \degree$以内におさまるすべての$v_i$の添え字を保持することにする。添え字がすべて連続している瞬間があれば$u$を$90 \degree$回転したものを答えにすればよい。管理と判定はBITでできる。以下、実装のポイント:
- 尺取り法で区間を伸ばす場合の処理: ベクトルの候補$u$と$v_i$のクロス積がマイナスになるまで伸ばしていけばよい。[1]
- 尺取り法で区間を縮める場合の処理: $u$と$v_i$のクロス積がプラスになるまで縮めればよい。
- $u$と同一か180度回転した偏角が$(v_i)$に含まれる場合、$u$（を$90\degree$回転したもの）は答えにできない。
さて、$2N$本の直線を用意する上で、整数性の条件を考慮しなくてはならない。単純化のために正数に限定して考える。ベクトル$(x, y)$から反時計回りに微小に偏角を進めたベクトルを得ることは、$y/x < 1$であればファレイ数列$F_{2\cdot 10^9}$において$y/x$の直後にある分数を得ることと同じである。$y/x \ge 1$の場合も、逆数を取って直前の分数を得ると考えればよい。やり方を知らないのでググったらstackexchangeの質問が見つかった。ファレイ数列の隣接項$p/q, c/d$は$cq-dp=1$を満たすので、$c, d$は互除法で求まるようだ。
クロス積がマイナスになるベクトルが存在しなかった場合はこれだとうまく処理できないように見える。こういうことが起こるのは、偏角ソートされた$(v_i)$の隣接項同士が$180\degree$より開いている場合だが、問題設定より全ベクトルを足すと$0$に戻るのでこの範囲に1つもベクトルがないということはありえない。 ↩︎
登録:
投稿 (Atom)