2022-03-02

ABC239F Construct Highway

ABC 木の構成マージテク

解説AC

問題へのリンク
 解説1へのリンク
 解説2へのリンク

web解説を見てよくわからなかったので、自分なりに証明してみました。
素人なので、間違っていたらすみません。

森と、森の各連結成分 $C_i$ について、他の連結成分と連結しなければならない次数の不足数 $D_i$ が与えられる(以下、不足数と表現します。)。これを満たすように連結させ、森を1つの木とすることを考えます。

$C=1$ のときは既に木が構成されているので、 $C\geq 2$ を仮定します。

これを達成するための必要十分条件は、連結成分数を $C$ 、与えられた不足数の合計を $D$ として、

$D=2C-2$ かつ $D_i\gt 0$

が成り立つことである。また、これを満たす時、その構成方法は、

$C\geq 3$ なら、少なくとも一方が不足数2以上である連結成分を選び、連結する
$C=2$ なら、不足数が1である2つの連結成分を連結にする

ことである。

まず、木を構成する上で、なぜ
$C=2C-2$ かつ $D_i\gt0$
という条件が出てくるのかメモしておきます。

木の構成可能条件が出てくる理由

木 $T$ の辺を1本ずつ切断していくことを考える。

任意の辺を1本切断した時、連結成分数は $C_1,C_2$ の2個になり、不足数は $D_1 = D_2 = 1$ で合計は2となる。これは、 $D=2C-2$ かつ $D_i\gt 0$ を満たす。

次に、 $k$ 本目の切断時に $D=2C-2$ かつ $D_i\gt 0$ が成り立っていると仮定し、 $k+1$ 本目の辺を切断した時を考える。
辺が1本以上存在する任意の連結成分 $C_x$ の辺を切断し、 $C_y,C_z$ に分割されたとする。

$C_y,C_z$ には次数の不足が+1ずつされることから $D_y,D_z\geq 1 \gt 0$ が成り立つ。

$k+1$ 本目の辺を切断した後の連結成分数を $C'$ 、不足数の合計を $D'$ とすると、連結成分数は1つ増え、次数の不足は2つ増える。

$k$ 本目切断時の $C,D$ から、 $C' = C + 1$ 、 $D' = D + 2$ となるので、 $D=2C-2$ に代入すると、
$D'-2=2(C'-1)-2\rightarrow D'=2C'-2$
となる。
従って、 $D=2C-2$ が成り立つ。

以上から、木から任意の辺を1本以上取り除くと、 $D=2C-2$ かつ $D_i\gt 0$ が常に成り立つことが示された。

このようにして条件が出てきます。

次に、 $D=2C-2$ かつ $D_i\gt 0$ ならば、木が構成できることを構成方法の正当性とともに示します。

$D=2C-2$ かつ $D_i\gt 0$ $\Rightarrow$ 木を構成できる

$C\geq 3$ である間、先程示した帰納法の逆を考えると、任意の連結成分を連結しても常に、 $D=2C-2$ が成り立つ。

連結する2つの連結成分の内、少なくとも一方について、連結前の不足数が2以上であれば、不足数が各々1減っても新たにできる連結成分の不足数は0とならないので、 $D_i \gt 0$ も保たれる。

よって、 $C=2$ となるまで、この操作を繰り返す。

$C=2$ となったとき、 $D=2C-2$ かつ $D\gt 0$ が成り立っていることから、2つの連結成分のそれぞれの不足数が1である。これを連結させることで1つの木とできる。

以上で証明は終了ですが、以下を示しておきます。

補足

$C\geq 3$ であり、 $D=2C-2$ かつ $D\gt 0$ ならば、

$D_i = 1$ しか存在しない
$D_i\geq 2$ しか存在しない

ことがあり得ないことを示す。
これが示されると、各段階で常に不足数が2以上の連結成分と1の連結成分が1個以上存在することになる。また、これが成り立たないと、構成の途中で木にできない状態を作り出してしまうことになる。

$D_i = 1$ しか存在しない状態にならない

この状態になったと仮定すると、 $D=C$ となり、 $D=2C-2$ が成立していることから、 $C=2C-2\rightarrow C=2$ が成り立つはずである。しかし、 $C\geq 3$ という仮定からこれは成り立たない。

$D_i \geq 2$ しか存在しない状態にならない

$D\geq 2C$ となるが、 $D=2C-2$ と矛盾する。

最後に、十分性を示しておきます。

木を構成できる $\Rightarrow$ $D=2C-2$ かつ $D_i\gt 0$

対偶

$D\neq 2C-2$ であるか、または、不足数0となる連結成分が1つでも存在するなら木を構成できない

を示す。

不足数0である連結成分が1つでも存在すると、その連結成分を連結できないため、1つの木とならない。よって、木を構成できない。

$i$ 回目の連結操作の終了時点で、 $D\neq 2C-2$ が成立し、 $i+1$ 回目の連結操作で $D=2C-2$ にできると仮定する。
しかし、先程示した帰納法と同様の議論で、 $i+1$ 回目に $D=2C-2$ が成立する場合、 $i$ 回目の操作終了時点に $D=2C-2$ が成り立つことが証明できる。
よって、仮定と矛盾するため、 $D\neq 2C-2$ から $D=2C-2$ が成立する状態にできない。
従って、 $D\neq 2C-2$ の状態から1つの木を構成することはできない。

以上で対偶が示された。

解法

これでweb解説の2つの構成方法

不足数2以上と不足数1を連結する
不足数が多い2つを連結する

がそれぞれ正しいことがわかりました。

ところで、次の構成方法も問題ないはずです。

初期状態( $M$ 個の辺を繋げた状態)において、不足数が最大のものを $C_x$ とおく。まず、不足数が2以上の連結成分を全て $C_x$ に連結させる。その後、不足数が1の連結成分を $C_x$ に連結させる。

この解法でACできました。
( $C_x$ として不足数最大を取らなくても不足数2以上であれば何でも良さそうです)

なお、構成前の前提として、以下の場合も解なしです。

頂点数と不足数の和が $D=2N-2$ を満たさない
$M$ 個の辺を繋いだ時に不足数が負となる連結成分が存在する

余談ですが、解説にあるような、個数の小さい方から大きい方にマージすることをマージテクと呼ぶのを初めて知りました。

提出コード

2022-02-24

ABC240 参加記録

ABC DFS 上界・下界を見積もる

コンテスト中AC:A〜E

E - Ranges on Tree

コンテスト中は確信が持てないまま通してしまいました。
解法に至った経緯をメモしておきます。

まず、問題文の意味がパッと見で理解できませんでした。そこで、入出力例を確認して、ざっくりと以下のような制約であると理解しました。

親の区間を、子に分配する。この時、子の区間は親の区間をはみ出してはならず、かつ、子同士の区間が重なってはならない。

ここまでで解法は思いつかなかったので、問題の例を全て確認してみました。すると、以下がわかりました。

根の区間は、葉の個数を $k$ として、 $[1,k]$
葉の区間は、ある正整数 $m=1,...,k$ をとって、 $[m,m]$ であり、 $m$ は葉同士で相異なる

ことがわかりました。
そこで、葉にそれぞれ $m=1,...,k$ まで割り振って、その葉の区間を $[m,m]$ とし、その後、親に向かうにつれて区間を併合していく解法を思いつきACできました。

公式解説によれば、この解法の正当性として、

葉には必ず異なる番号(区間)を振らなければならないので、k個の異なる整数が必要であり、答えはk以上になる。一方、先に示した方法なら、答えをkにできる。よって、この方法で得られる解は最小であり、解法の正当性が示された。

という感じでした。

提出コード

2022-02-20

ABC239 参加記録

ABC エラトステネスの篩ウェーブレット行列オイラーツアー床関数マージテク

コンテスト中AC:A〜E

B - Intenger Division

以前、このような自作関数を作っていました。

template<typename T> 
T Floor(T a, T b) {
    if ((a<0 && b<0) || (a>0 && b>0)) return a/b;
    else return (Abs(a)+Abs(b)-1)/Abs(b)*-1LL;
}

これを使うことで、Floor(X,10LL)で求められました。
提出コード

E - Subtree K-th Max

Kが小さいことから、公式解説の想定解を思いつきつつも、計算量の見積もりがよくわからなかったので、異なる解法で解きました。
オイラーツアーの部分木クエリと同じ考え方となります。

まず、一回のDFSで以下を記録しておきます。

頂点 $u_i$ のpre-order順。これを $Id_u$ とします。
$X_i$ を頂点のpre-order順に並べたもの。これを配列 $A$ とします。
部分木に属する頂点数。これを $dp_u$ とします。

このようにすると、 $i$ 番目のクエリは、

$Id_{V_i} \leq j \lt Id_{V_i}+dp_{V_i}$ を満たす $A_j$ のうち $K_i$ 番目に大きい数を求めよ

という問題となります。入力例1を例にします。以下はDFS実行後の一例です。

$A = \{1,4,2,5,3\}$
$Id = \{1,3,5,2,4\}$
$dp = \{5,3,1,1,1\}$

ここで、2個目のクエリ、頂点2を根とした時の1番目に大きい数を求めてみます。
対象となる $A_j$ の区間は、 $3\leq j \lt 3+3 \rightarrow 3\leq j \lt 6$ となるので、 $A_3,A_4,A_5$ から1番目に大きい値を計算します。
$2,3,5$ なので、答えは $5$ です。

ここで、 $K$ 番目に大きい値を高速に得る必要があります。
これはウェーブレット行列により可能となります。

$A$ のウェーブレット行列を求めておます。ウェーブレット行列には以下の関数があります。

$quantile(s,e,r)$ : 半開区間 $[s,e)$ のうち、 $r+1$ 番目に小さい値を返す。計算量は $O(logX_{max})$ 。(但し、 $X_{max}$ は $X_i$ の最大値)

これを用いると、区間のサイズが $dp_{V_i}$ であることから、 $quantile(Id_{V_i},\ Id_{V_i}+dp_{V_i},\ dp_{V_i} - K)$ として解を得られます。

計算量は、木なのでDFSに $O(N)$ かかります。また、ウェーブレット行列の構築に $O(NlogX_{max})$ 、
ウェーブレット行列で各クエリに答えるのに $O(QlogX_{max})$ かかります（多分）。

提出コード

2022-02-16

ARC135 参加記録

ARC XOR メモ化再帰

コンテスト中AC:A,C
Bはコンテスト後自力AC。もう少しで解けそうでした。

A - Floor, Ceil - Decomposition

実際に10まで、xとfloor(x/2)×ceil(x/2)のどちらが大きいか手計算しました。

すると、

x≦4なら、x≧floor(x/2)×ceil(x/2)
x≧5なら、x<floor(x/2)×ceil(x/2)

となりました。大きめの数で試してもx<floor(x/2)×ceil(x/2)となり、その差は大きくなっていくので、厳密でないものの一般のxでもこれが成り立つと考えました。
よって、

x≦4ならそのまま、そうでなければfloor(x/2)とceil(x/2)に置き換える。

という解法が成り立つと考えました。

実装ですが、この手の問題ではメモ化再帰を使える場合が多いです。
メモ化することで、xが偶数なら状態は1/2になりますし、厳密ではないものの、全状態数は十分に少ないと見積もりました。
実際に提出してみると、ACできました。
(最大の10¹⁸くらいは試しておけばよかったです。)

厳密でなかった部分は、前者は公式解説に証明がありました。後者も証明できるそうです。(具体的な証明はありませんでした。) 提出コード

B - Sum of Three Terms

$A_1,\ A_2$ 及び $S_i$ が決定すると、 $i\geq 3$ の $A_i$ を決定できます。
また、 $A_i \geq 0$ という制約があるので、 $A_1,\ A_2$ に関する何らかの制約が得られそうです。
$A_7$ まで、列挙してみます。
$A_1 = A_1$
$A_2 = A_2$
$A_3 = S_1 - A_1 - A_2$
$A_4 = S_2 - S_1 + A_1$
$A_5 = S_3 - S_2 + A_2$
$A_6 = S_4 - S_3 + S_1 - A_1 - A_2$
$A_7 = S_5 - S_4 + S_2 - S_1 + A_1$

$S_i$ のみからなる定数部分を $B_i$ としておきます。 $B_i$ は、

$i \leq 2$ のとき、 $B_i = 0$
$i \geq 3$ のとき、 $B_i \leftarrow S_{i-1} - B_{i-1} - B_{i-2}$

として、計算できます。

次に、 $A_1,\ A_2$ に関する制約式を得たいので、それぞれの $A_i$ での係数を $A_1 [i],\ A_2 [i]$ とします。
これも以下のように計算できます。

$i=1$ のとき、 $A_1 [1] = 1,\ A_2 [1] = 0$
$i=2$ のとき、 $A_1 [2] = 0,\ A_2 [1] = 1$
$i\geq 3$ のとき、
$A_1 [i] = -A_1 [i-1]- A_1 [i-2]$
$A_2 [i] = -A_2 [i-1]- A_2 [i-2]$

これを基に実際に実装して計算してみたところ、以下の事実に辿り着きました。

$i\ mod\ 3 = 0$ のとき、 $A_1 [i] = -1,\ A_2 [i] = -1$
$i\ mod\ 3 = 1$ のとき、 $A_1 [i] = 1,\ A_2 [i] = 0$
$i\ mod\ 3 = 2$ のとき、 $A_1 [i] = 0,\ A_2 [i] = 1$

そのため、 $A_i \geq 0$ という制約から、以下の3種類の制約式が得られます。

$i\ mod\ 3 = 0$ のとき、 $A_1 + A_2 \leq B_i$
$i\ mod\ 3 = 1$ のとき、 $A_1 \geq -B_i$
$i\ mod\ 3 = 2$ のとき、 $A_2\geq -B_i$

そこで、
$A_1+A_2$ の上限を $X$
$A_1$ の下限を $Y$
$A_2$ の下限を $Z$

とします。初め、 $X=S_1,\ Y=Z=0$ です。
これを $i=3,4,...,N+2$ について、以下のように更新していきます。

$i\ mod\ 3 = 0$ のとき、 $X\leftarrow min(X,\ B_i)$
$i\ mod\ 3 = 1$ のとき、 $Y \leftarrow max(Y,\ -B_i)$
$i\ mod\ 3 = 2$ のとき、 $Z \leftarrow max(Z,\ -B_i)$

これが終了したとき、
$0\leq A_1 + A_2 \leq X$
$Y\leq A_1 \leq S_1$
$Z\leq A_2 \leq S_1$
という制約式が得られ、これを満たすような $A_1,\ A_2$ を設定します。

まず、
$X\lt 0$
$Y\gt S_1$
$Z\gt S_1$
のいずれかを満たす時、解なしです。

そうでないとき、
$0\leq A_1 + A_2 \leq X$
を満たすようにするには、 $A_1,\ A_2$ は、それぞれの下限である $A_1=Y$ 、 $A_2 =Z$ にしておくのが最善です。
そのため、 $Y+Z\gt X$ であれば解なしです。

そうでなければ、 $A_1=Y$ 、 $A_2 =Z$ として $A$ を構築できます。
(下記実装はiが0-indexedなので、i mod 3の値が異なっています) 提出コード

C - XOR to All

$A=\{A_1,\ A_2,\ A_3,\ A_4,\ A_5\}$ として以下に一例を示します。

$A_1$ と全体のXORをとる。 $\{A_1\oplus A_1,\ A_2\oplus A_1,\ A_3\oplus A_1,\ A_4\oplus A_1,\ A_5\oplus A_1\}$
$A_5\oplus A_1$ と全体のXORをとる。
$\{A_1\oplus A_1\oplus A_5\oplus A_1,\ A_2\oplus A_1\oplus A_5\oplus A_1,\ A_3\oplus A_1 \oplus A_5\oplus A_1,\ A_4\oplus A_1\oplus A_5\oplus A_1,\ A_5\oplus A_1\oplus A_5\oplus A_1\}$
XORは交換法則が成り立ち、かつ、 $X\oplus Y\oplus Y = X\oplus 0 = X$ より、
$\{A_1\oplus A_5,\ A_2\oplus A_5,\ A_3\oplus A_5,\ A_4\oplus A_5,\ A_5\oplus A_5\}$

これより、任意に置き換えを行った場合でも最終的には、
$\{A_1\oplus A_i,\ A_2\oplus A_i,\ \cdots,\ A_N\oplus A_i\}$
という形になります。

そこで、 $i=1,2,...,N$ について、
$B_i=(A_1\oplus A_i)+(A_2\oplus A_i)+\cdots +(A_N\oplus A_i)$
とした時、最大の $B_i$ を求める問題と読み替えられます。

愚直にこれを計算すると $O(N^2)$ となって、間に合わないため、工夫する必要があります。

ビットの問題では各ビットに着目するのが典型なので、それを基に考えてみます。すると、

$A_i$ の $j$ ビット目が0の場合、 $A_1,\ A_2,\ \cdots ,\ A_N$ の $j$ ビット目はそのまま。
$A_i$ の $j$ ビット目が1の場合、 $A_1,\ A_2,\ \cdots ,\ A_N$ の $j$ ビット目はすべて反転する。

ということがわかります。
そのため、 $A_1,\ A_2,\ \cdots ,\ A_N$ のうち、 $j$ ビット目が1の個数(または0の個数)さえ分かれば、以下のように $B_i$ を計算できます。

$cnt_j$ を $A_1,\ A_2,\ \cdots ,\ A_N$ の内、 $j$ ビット目が1である要素の個数とし、
$A_i$ の最大値 $A_{max}$ の最上位ビットを $D$ ビット目とする。

$j=0,1,2,...,D$ について、

$A_i$ の $j$ ビット目が0の場合

$B_i$ に $2^j$ を $cnt_j$ 個分足す： $B_i \leftarrow B_i + cnt_j \times 2^j$
$A_i$ の $j$ ビット目が1の場合

$B_i$ に $2^j$ を $N-cnt_j$ 個分足す。： $B_i \leftarrow B_i + (N-cnt_j) \times 2^j$

このようにすると、全ての $B_i$ を $O(DN)$ で計算できます。 $A_i \lt 2^{30}$ という制約上、 $D$ は最大で29なので、 $j$ のループは最大でも30回となり、余裕を持って間に合います。

なお、操作を一度も行っていない場合も考慮する必要があります。

提出コード

2022-02-11

ABC237F |LIS| = 3

最長増加部分列 ABC DP

解説AC

問題
 公式解説

公式解説で解法だけみて、実装は自力でしてみようと思ったのですが、これも上手くいきませんでした。結局、実装も解説のものを確認しました。

LISの長さが3未満の保持方法

未確定の部分はinf、今回ならM+1としておけばよいようです。
例えば、{2,5}というLISを持つ数列はdp[i][2][5][M+1]という感じになります。

dp遷移におけるループ

a1,a2,a3のループ部分は、単調増加にしたくなります。

イメージ
for a1 = 1 to M+1
　for a2 = a1+1 to M+1
　　for a3 = a2+1 to M+1

しかし、このようにするとM+1を複数含む場合の遷移が起こらないため、だめでした。
そのため、ループ部分は、
for a1 = 1 to M+1
　for a2 = 1 to M+1
　　for a3 = 1 to M+1

と、しておく必要があります。
dp[i][2][5][1] += dp[i-1][1][5][1]ような不正な更新が行われますが、これらは全て0になっているので問題ないということでした。

提出コード

2022-02-09

ABC234F Reordering

ABC 重複並び替え

解説AC

問題へのリンク
 公式解説

単純に部分列を得るだけなら部分列DPなどが考えられますが、今回はすべての並び替えを得る必要があるので適用できません。
重複を含む並び替えの計算方法から考えてみます。

$a,b,c,\cdots ,z$ の選んだ個数をそれぞれ $A,B,C,\cdots , Z$ とします。この時の並び替えの方法は、

$\frac{(A+B+C+\cdots +Z)!}{A!\cdot B! \cdot C! \cdot\ \cdots \ \cdot Z!}$

です。

よって、各文字を何個選んだかという情報があれば、並び替えが何通りあるか得ることができます。
そこで、それぞれ何個選ぶかをDFSで全探索してみましたが、到底間に合いませんでした。

ここからは公式解説の方法に自分の補足を加えながら書いてみます。

実は、どの文字を何個選んだかという情報は不要で、合計で何個選んだかさえ分かれば、その時に選んだ文字数に対する文字列の並び方の総数を計算できるということでした。

具体例として、aが3個、bが3個ある場合に、a,bから合計4個選んだ時の並び替えの総数から、その後cから3個選んだ時の並び替えの総数への遷移を考えます。

aを3個、bを1個選んでいた場合
$\frac{4!}{3!1!}$ が $\frac{7!}{3!1!3!}$ になります。
よって、
$\frac{4!}{3!1!}\times {}_7C_4 = \frac{7!}{3!1!3!}$ です。
aを2個、bを2個選んでいた場合
$\frac{4!}{2!2!}$ が $\frac{7!}{2!2!3!}$ になります。
よって、
$\frac{4!}{2!2!}\times {}_7C_4 = \frac{7!}{2!2!3!}$
aを1個、bを3個選んでいた場合
$\frac{4!}{1!3!}$ が $\frac{7!}{1!3!3!}$ になります。
よって、
$\frac{4!}{1!3!}\times {}_7C_4 = \frac{7!}{1!3!3!}$

以上から、
$(\frac{4!}{3!1!}+\frac{4!}{2!2!}+\frac{4!}{1!3!})\times {}_7C_4 = \frac{7!}{3!1!3!}+\frac{7!}{2!2!3!}+\frac{7!}{1!3!3!}$
となります。

ここで、dpを考えます。a,b,c,...を1番目,2番目,3番目,...とします。
$dp[i][j]:=i$ 番目までの文字を考えたとき、これまで選んだ文字の合計個数が $j$ の時の、並び替えによって得られる文字列の総数
と、定義します。

すると、

$dp[2][4]=\frac{4!}{3!1!}+\frac{4!}{2!2!}+\frac{4!}{1!3!}$
$dp[3][7]= \frac{7!}{3!1!3!}+\frac{7!}{2!2!3!}+\frac{7!}{1!3!3!}$

であることから、

$dp[3][7]=dp[2][4]\times {}_7C_4$

となって、bまでで文字を合計4個選んだ時の文字列の総数から、cまでで文字を合計7個選んだ時の文字列の総数を計算できました。

一般化すると、 $i-1$ 番目までで文字を合計 $k$ 個選んだ時の文字列の並び替えの総数から、 $i$ 番目で $j$ 個選んだときの文字列の並び替えの総数は、

$dp[i][j+k]\leftarrow dp[i-1][k]\times {}_{j+k}C_k$

と計算できます。

計算量についてです。
解説の実装部分は読まずに実装してみました。

    dp[0][0] = 1;
    ll sum = 0;
    rep(i,1,27) {
        rep(j,C[i-1]+1) {
            rep(k,sum+1) {
                dp[i][k+j] += dp[i-1][k]*cn.nCr(k+j,k);
            }
        }
        sum += C[i-1];
    }