dwangoプログラミングコンテスト D - タクシー

• 問題
• AC

最小費用流なので、とりあえずグラフを二周くらいしながら需要と供給を解消していって、循環流になおす。あとは負閉路を解消すれば最適になるが、このグラフ上の負閉路は環状線を一周するものしかありえないので、ここにできるだけ流せばよい。具体的には、残余グラフ上の負辺を集めて$(上限流量、辺の重み)$を上限流量の昇順でソートして、先頭から順に（一周のコストが負である限り）上限流量いっぱいに流すことを繰り返した。

ARC 093 E - Bichrome Spanning Tree

• 問題
• AC

$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)$。

---

厳密な証明がよくわからなかった。

---

1. path optimality condition ↩︎

ABC 180 F - Unbranched

• 問題
• AC

「最大サイズがちょうど$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$は許されないことに注意。

CodeChef October Challenge 2020 - Compress all Subsegments

• 問題
• AC

区間$I$に関する$f$の値は、$(A_i)_{i \in I}$中のhighest set bitの位置を$k$として、$k$が立っている数が$(A_i)_{i \in I}$に何個含まれるかでだいたい決まる:

1. $k$が立っている数が1個でそれ以外が0個の場合、その数自身になる
2. $k$が立っている数が奇数個の場合、上の場合を除いて$2^k$になる
3. $k$が立っている数が2個でそれ以外が0個の場合、不定
4. $k$が立っている数が2個でそれ以外が1個の場合、不定
5. $k$が立っている数が2個でそれ以外が2個以上の場合、0にできる
6. $k$が立っている数が4個でそれ以外が$0$個の場合、不定
7. $k$が立っている数が4個でそれ以外が$1$個以上の場合、0にできる
8. $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)$。