[WIP]ABCの高度典型を解いてうはうはしたい

謝罪

常体と敬体がごっちゃです。ごめんなさい。エンタメとしてお楽しみください。

解法を書くのに、公式解説、公式解説放送を主に参考にしています。それだけで理解できなかったものは、他の方のブログを参考にしています。その際は、参考にしたブログのリンクを貼っています。

ABC212-G Power Pair

問題概要

素数$P$が与えられ、$x^n \equiv y \pmod{P}$を満たす$n$が存在する$(x,y)$の組$(0\leq x,y\leq P-1)$の個数を求める問題。

素数$P$に対する原始根$r$が必ず存在するため、$x=r^a,y=r^b$とか表現すると、 $$ x^n \equiv y \pmod{P} \Leftrightarrow r^{an} \equiv r^b \pmod{P} \Leftrightarrow an \equiv b \pmod{P-1} $$ となるので(最後の変換はフェルマーの小定理より)、$an \equiv b \pmod{P-1}$を満たす$(a,b)$の組$(1\leq a,b\leq P-1)$を数えれば良い。

さて、ここからどう数えるかだが、

$P-1$と$a$の最大公約数が$1$であるような$a$を見つけてきたとき、$n=1,2,\cdots P-1$のとき$b$は$P-1$通りの値を取る。
$P-1$と$a$の最大公約数が$2$であるような$a$を見つけてきたとき、$n=1,2,\cdots P-1$のとき$b$は$(P-1)/2$通りの値を取る。

というように、$P-1$と$a$の最大公約数が$g$であるような$a$を見つけてきたとき、$n=1,2,\cdots P-1$のとき$b$は$(P-1)/g$通りの値を取ることがわかる。

$a=1,2,\cdots P-1$のそれぞれに対して$P-1$との最大公約数を取るのは$O(P\log P)$かかってしまうので、$GCD(P-1,a)$の値が$g$になるような$a$の個数を数えることにする。これは$g$が大きい順に数えるとうまくいく(説明がめんどいのでコードを貼ってごまかす)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
mint ans = 1;
map<long,long> mp;
for(auto&i:f){ //fはP-1の約数(降順)
    // GCD(P-1, x) = iとなるxの個数を求める
    long n = P/i;
    for(auto&j:f){
        if(j<=i)continue;
        if(j%i==0){
            n -= mp[j];
        }
    }
    mint a = P/i;
    mint b = n;
    ans += a*b;
    mp[i] = n;
}

提出コード

感想

原始根って便利なんですね

ABC212-H Nim Counting

問題概要

長さ$K$の数列$(A_1,A_2,\cdots,A_K)$が与えられ($1\leq A_i\leq 2^{16}$)、ここから$1$個以上$N$個以下の数を選び(重複可能)、それらの選んだ数のXORをとったとき、$0$にならないような選び方の個数を求める問題。

この問題ではxorの畳み込みという技術を使います。xorの演算子を$\oplus$、xor畳み込みの演算子を$*$とすると、xor畳み込みというのは、

$$ A = (a_1, a_2, \cdots, a_n) \\ B = (b_1, b_2, \cdots, b_n) \\ c_i = \sum_{x\oplus y = i} a_x b_y $$ となるようなベクトル$C = A * B = (c_1, c_2, \cdots, c_n)$を求めることで、$O(n\log n)$で行えます。すなわち、これでxor畳み込み後に添え字が0$以外の要素の総和を求めることでこの問題は解けそうです。

Hadamard変換

天下り的ですが、 $$ \begin{aligned} H_0 &= 1 \\ H_k &= \begin{pmatrix} E_{k-1} & E_{k-1} \\ E_{k-1} & -E_{k-1} \end{pmatrix} \begin{pmatrix} H_k & 0 \\\ 0 & H_k \end{pmatrix} \end{aligned} $$ と行列$H_i$を定義します($E_k$は$k$次の単位行列)。このとき、$H_k$は$2^k$次の行列です。 $$ H_k H_k = 2^k E_{2^k} $$ が成り立ちますので、$H_k^{-1} = 2^{-k} H_k$となります。また、長さ$2^k$のベクトル$A$と$B$に対して次が成り立ちます。 $$ (H_k A) (H_k B) = H_k (A * B) $$ 左辺はベクトルの各要素ごとの積を表しています。これを変形すると、 $$ A * B = 2^{-k} H_k ((H_k A) (H_k B)) $$ が成り立ちます。しかし、これは長さ$2^k$のベクトルと$2^k$次の正方行列の積の計算をする必要がありますので、$n=2^k$として、結局$O(n^2)$かかってしまいます。しかし、この行列$H_k$とベクトルの積はうまいことに高速化ができます。

高速Walsh-Hadamard変換

$H_k$を変形します。 $$ \begin{aligned} H_k &= \begin{pmatrix} E_{k-1} & E_{k-1} \\ E_{k-1} & -E_{k-1} \end{pmatrix} \begin{pmatrix} H_k & 0 \\\ 0 & H_k \end{pmatrix} \\ &= \begin{pmatrix} E_{k-1} & E_{k-1} \\ E_{k-1} & -E_{k-1} \end{pmatrix} \begin{pmatrix} E_{k-2} & E_{k-2} & 0 & 0 \\ E_{k-2} & -E_{k-2} & 0 & 0 \\ 0 & 0 & E_{k-2} & E_{k-2} \\ 0 & 0 & E_{k-2} & -E_{k-2} \end{pmatrix} \begin{pmatrix} H_{k-2} & 0 & 0 & 0 \\ 0 & H_{k-2} & 0 & 0 \\ 0 & 0 & H_{k-2} & 0 \\ 0 & 0 & 0 & H_{k-2} \end{pmatrix} \\ &= \cdots \end{aligned} $$ この行列の積への分解は高々$O(\log n)$回で終わります(上記の変形をし続けると最後に$H_0$が対角上に並んだ行列、すなわち単位行列が現れます)。そして、各分解された行列をよく見ると、各行で$0$ではない要素は必ず$2$つです。すなわち、この分解された行列単体とベクトルの積は、$O(n)$で行うことができ、行列は$O(\log n)$個しかありませんので、結局$O(n\log n)$で行うことができます。

ピンと来ないという私のために、$n=8$のときの$H_3$を分解してみます。 $$ \begin{aligned} H_3 &= \begin{pmatrix} E_2 & E_2 \\ E_2 & -E_2 \end{pmatrix} \begin{pmatrix} E_1 & E_1 & 0 & 0 \\ E_1 & -E_1 & 0 & 0 \\ 0 & 0 & E_1 & E_1 \\ 0 & 0 & E_1 & -E_1 \end{pmatrix} \\& \begin{pmatrix} E_0 & E_0 & 0 & 0 & 0 & 0 & 0 & 0 \\ E_0 & -E_0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & E_0 & E_0 & 0 & 0 & 0 & 0 \\ 0 & 0 & E_0 & -E_0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & E_0 & E_0 & 0 & 0 \\ 0 & 0 & 0 & 0 & E_0 & -E_0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & E_0 & E_0 \\ 0 & 0 & 0 & 0 & 0 & 0 & E_0 & -E_0 \end{pmatrix} \begin{pmatrix} H_0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & H_0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & H_0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & H_0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & H_0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & H_0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & H_0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & H_0 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \end{pmatrix} \\& \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \end{pmatrix} \end{aligned} $$ これを実装するのにも結構頭を使います。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template<class T> vector<T> Hadamard(const vector<T>&A,const int k){
    // 2^k次行列
    if((int)A.size()!=(1<<k)){
        cout<<"A size should be 2^k"<<endl;
        return vector<T>();
    }
    vector<T> res = A;
    int h = 1;
    for(int i=0;i<k;i++){
        vector<T> tmp(1<<k,0);
        for(int j=0;j<(1<<k);j+=h*2){
            for(int l=j;l<j+h;l++){
                tmp[l] = res[l] + res[l+h];
                tmp[l+h] = res[l] - res[l+h];
            }            
        }
        h <<= 1;
        res = tmp;
    }
    return res;
}

template<class T> vector<T> xor_convolution(const vector<T>&A,const vector<T>&B,const int k){
    // xor convolution
    // A,Bのサイズは2^k
    vector<T> a = Hadamard(A,k);
    vector<T> b = Hadamard(B,k);
    vector<T> res(1<<k);
    for(int i=0;i<(1<<k);i++){
        res[i] = a[i] * b[i];
    }
    res = Hadamard(res,k);
    return res; //これを2^kで割る必要がある
}

このコードは最後に得た値の各要素を$2^k$で割り算してやる必要があるので注意です。

問題に戻る

問題で求めたいのは、$C=(c_1,c_2,\cdots,c_{2^{16}})$($c_i$は$i$個の石がある山の個数)があって、 $$ H(H(C)) + H((H(C))^2) + H((H(C))^3) + \cdots + H((H(C))^N) $$ です($C^i$は各要素の$i$乗を取ることを意味します)。Hadamard変換は線形変換なので、次のように変形できます。$D=H(C)$とすると、 $$ H( D + D^2 + D^3 + \cdots + D^N) $$ かなりスッキリしました。あとは、等比数列の和の公式を使って、括弧の中身を計算することができます。

等比数列の和の公式は $$ \frac{d_i(d_i^N-1)}{d_i-1} $$ です。$d_i=0,1$の場合はこのまま計算すると値がおかしくなるのでそこだけ別処理することに注意します。

提出コード

参考サイト

感想

これのAND版やOR版もあるらしい。考えた人天才。

ABC213-G Connectivity 2

問題概要

$N$頂点$M$辺の単純無向グラフ$G$で、$0$本以上の辺を取り除いて新しいグラフ$H$を作る。各$k=2,3,\cdots,N$に対して、頂点$1$と$k$が$H$で連結になるような辺の取り除き方の個数を求める問題。

言い換え

問題で求められている「頂点$1$と$k$が連結(ry」の個数を$C(k)$とします。また、次のように$f(S),g(S)$を定義します。

$f(S) := $ $S$を頂点集合とする$G$の連結部分グラフの個数
$g(S) := $ $S$を頂点集合とする$H$の部分グラフの個数

すると、次のように$C(k)$を表現できます。ちなみに$V$は$G$の頂点集合です。 $$ C(k) = \sum_{\lbrace 1,k \rbrace \subset S \subset V} f(S) g(V\setminus S) $$ 全ての$f(S),g(S)$が既知ならば、これは$O(N2^N)$で計算できます。

g(S)の計算

これは簡単です。辺の両端が頂点集合$S$に含まれるような辺の個数を$E(S)$とすれば、$2^{E(S)}$が$g(S)$になります。各頂点集合について$M$個の辺がそれぞれ含まれているかどうかを判定するので$O(M2^N)$で計算できます。

f(S)の計算

問題はこちらです。$f(S)=g(S)-$(頂点集合が$S$であるような非連結なグラフの個数)です。$g(S)$は既知なので、後者を計算する必要があります。連結でないグラフというのは、連結成分が$2$個以上あるグラフのことです。「この$2$個以上の連結成分」というのを、「$1$つの連結成分があって、残りの使ってない頂点たちを好きなようにしてもらう」という数え方をします。

$S$に含まれる頂点を$1$つ取ってきて、これを$v$とすると$f(S)$は次のようになります(この$v$がないとカウントが重複してしまいます)。 $$ f(S) = g(S) - \sum_{ v \in T \subsetneq S} f(T) g(S\setminus T) $$

これを$S$についていい感じの順番で計算していくことで、$O(3^N)$で計算できます。

部分集合の部分集合の列挙

部分集合の$i$の部分集合$j$の列挙は$O(3^N)$でできます。

1
2
3
4
5
6
for (int i = 0; i < (1 << N); i++) {
    for (int j = i; j >= 0; j--) {
        j &= i;
        // (i, j) は条件を満たす
    }
}

提出コード

感想

$f(S),g(S)$に分けて$g(S)$の計算方法考えるのむずくね？？

ABC213-H Stroll

問題概要

問題

DPで解けそうな問題設定だが、時間が間に合わない。

DP解

$d_{s,t}$を$t$キロメートル歩いて地点$s$にいる通り数とすると次のように計算できる。 $$ d_{s,t} = \sum _{(s^\prime,i,x)} d_{s^\prime,t-x} \times p_{i,t-x} $$

ただし、シグマ記号は「$s^\prime$から$s$に向かう$i$番目の長さ$x$の道」を全てのペアについて足し合わせることを意味する。これを$t$の小さい方から計算すれば$O(MT^2)$で計算できるがこれだと時間がかかりすぎる。

シンプルに$N=2$のときを考えると、 $$ d_{1,t} = \sum_u d_{2,u} \times p_{t-u} $$ という式になって、畳み込みっぽい見た目をしている。実際には$d_{2,u}$が定数ならば畳み込みで計算できる。

分割統治FFT

定数ならば畳み込みができるということで、半分を事前に計算して定数にし、いい感じに再帰的に計算するとなんと$O(T\log^2T)$で計算できてしまうのだ。言葉での説明が難しいので図を用意した。図は単純に$1$次元のDPを分割統治FFTで解いたものである。

ただ、計算に使用する数値は全て確定していなければならないので、以下のような順番で計算する必要がある。

今回は、頂点ごとにDPの値を持つが、全ての辺について上記の図のような遷移があるので、各遷移を全ての辺ごとに行う。計算量は$O(MT\log^2T)$となる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void DCFFT(int l,int r,vector<edge>&E,vector<vector<mint>>&p, vector<vector<mint>>&dp){
    int m = (l+r)/2;
    if(l+1==r)return ;
    DCFFT(l,m,E,p,dp);
    for(int i=0;i<(int)E.size();i++){
        auto [u,v] = E[i];
        // [m,r)を更新
        /*
        本来だったら
        for(int i=m;i<r;i++){
            dp[v][i] += sum_x (dp[u][i-x]*p[v][x]);
        }
        をやるが、FFTを使う
        */
        auto dp2u = vector<mint>( dp[u].begin()+l, dp[u].begin()+m );
        auto p2 = vector<mint>( p[i].begin(), p[i].begin()+r-l );
        auto dp3u = convolution(dp2u,p2);
        for(int j=m;j<r;j++){
            dp[v][j] += dp3u[j-l];
        }
    }
    DCFFT(m,r,E,p,dp);
}

提出コード

感想

添字をミスりまくってめっちゃ時間かかった。地味に赤diff初AC。

ABC214-G Three Permutations

問題リンク

包除原理

条件が扱いづらいので、包除原理を使います。

$f(x)$を、$x$個の相異なる添字を選んだときに、その添字で$p_i=r_i$または$q_i=r_i$となるような$r_i$の割り当て方の個数とする。

すると、包除原理により、求める答えは $$ N! + \sum_{x=1}^N (-1)^x f(x) (N-x)! $$ となります。$(N-x)!$は残りの$N-x$個の添字に対する割り当て方の個数です。

この数え方にすぐに納得しない私は具体例を考えてみました。

$N=3, p=(1,2,3), q=(2,3,1)$のとき
- $r=(3,1,2)$の$1$通りだけであるが、これを上記の計算式で求める。
$f(1)$について
- $i=1$を被らせるとき、$r_1=1,2$のどちらかで$2$通り
  - $(1,3,2),(1,2,3),(2,1,3),(2,3,1)$の$4$通りがある
- $i=2$を被らせるとき、$r_2=2,3$のどちらかで$2$通り
  - $(2,1,3),(2,3,1),(3,1,2),(3,2,1)$の$4$通りがある
- $i=3$を被らせるとき、$r_3=3,1$のどちらかで$2$通り
  - $(3,1,2),(3,2,1),(1,2,3),(1,3,2)$の$4$通りがある
- $f(1) = 2+2+2$
- ここで注目したいのが、例えば$(1,2,3)$という順列は$i=1$と$i=2$のパターンの両方に含まれているということである。ここで$2$回取り除かれている順列は、$f(2)$以降で調整されていくのが包除原理である。
$f(2)$について
- $i=1,2$を被らせるとき$(1,2,3),(1,3,2),(2,3,1)$の$3$通りがある
- $i=2,3$を被らせるとき$(1,2,3),(3,2,1),(2,3,1)$の$3$通りがある
- $i=3,1$を被らせるとき$(1,2,3),(2,1,3),(2,3,1)$の$3$通りがある
- $f(2) = 9$
- ここで、$(1,2,3),(2,3,1)$のパターンは逆に足しすぎていので、$f(3)$で調整する。
$f(3)$について
- $i=1,2,3$を被らせるとき$(1,2,3),(2,3,1)$の$2$通りがある
- $f(3) = 2$
よって、$3! - 6\times 2! + 9\times 1! - 2\times 0! = 6 - 12 + 9 - 2 = 1$となり、正しく計算できていることがわかる。

グラフに変換

グラフを使います。頂点を$N$個用意して、頂点$p_i$と$q_i$を繋ぐ辺を張ります。

ここで注意するべきは、連結成分は必ずサイクルになります。なぜなら、$p,q$はどちらも順列であるので、同じ数がちょうど$2$回出現する$\Leftrightarrow$頂点の次数が$2$であるからです。

「各辺は、その両端の頂点番号を使ってはいけない」ことを示します。次の画像は被らせる添字とグラフの対応を表したものです(画像には「サイクル」とありますが、「連結成分」と書くべきでした)。

元のグラフの連結成分ごとに、$k$個の辺を選ぶ(=$k$個の数を被らせる)方法の場合の数をそれぞれ計算すれば、DPによって$f(x)$を計算できます。次の節ではそれぞれの連結成分で、$k$個の辺を選ぶ方法の場合の数を計算する方法を説明します。

DPで計算

サイクル状の頂点と辺を、$v_1,e_1,v_2,e_2,\cdots,v_y,e_y,v_1$と割り振ります。

DP[$i$][$j$] $:=$ $i$番目までの辺を使って、$j$個の辺を選んだときの場合の数

しかし、これだと情報が不十分です。辺$e_1$を選ぶと$v_1,v_2$のどちらかを選べます。$e_1$が$v_2$を選んだ場合、$e_2$は$v_3$を選ぶしかありません。逆に、$e_1$が$v_1$を選んだか、$e_1$を選んでいない場合は、$e_2$は$v_2,v_3$の$2$つの選択肢から選ぶことができます。よって、この情報を追加します。

さらに、円環なので、一番初めの頂点$v_1$が使われたという情報によって、$e_y$が$v_1$が選べるかどうかが決まります。よって、この情報も追加します。

DP[$i$][$j$][$k$][$l$] $:=$ $i$番目までの辺を使って、$j$個の辺を選んだとき、$i$番目の辺が$v_{i+1}$を選んだ/選んでいない($k=0/1$)、$v_1$を使った/使っていない($l=0/1$)の場合の数

こちらのDPですが、遷移が多いので注意深く実装します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
mint dp[3001][3001][2][2];

vector<mint> f(int n){
    if(n==1){
        return vector<mint>{mint(1), mint(1)};
    }
    rep(i,3001)rep(j,3001)rep(k,2)rep(l,2)dp[i][j][k][l] = mint(0);
    // nはサイクルの長さ
    // dp[i][j][k][l] :=
    // i番目までの辺を見て、j個使ったとき、
    // k=0: 直前を使っていない k=1: 直前を使った
    // l=0: 0を使っていない l=1: 0を使った
    dp[0][0][0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(i==1){
                // 使わない
                dp[i][j][0][0] += dp[i-1][j][0][0];
                if(j>0){
                    // 前を使う
                    dp[i][j][0][1] += dp[i-1][j-1][0][0];
                    // 後ろを使う
                    dp[i][j][1][0] += dp[i-1][j-1][0][0];
                }
            }else if(i==n){
                // 使わない
                dp[i][j][0][0] += dp[i-1][j][0][0];
                dp[i][j][0][0] += dp[i-1][j][1][0];
                dp[i][j][0][1] += dp[i-1][j][0][1];
                dp[i][j][0][1] += dp[i-1][j][1][1];
                if(j>0){
                    // 前を使う
                    dp[i][j][0][0] += dp[i-1][j-1][0][0];
                    dp[i][j][0][1] += dp[i-1][j-1][0][1];
                    // 後ろを使う
                    dp[i][j][1][0] += dp[i-1][j-1][0][0];
                    dp[i][j][1][0] += dp[i-1][j-1][1][0];
                }
            }else{
                rep(l,2){
                    // 使わない
                    dp[i][j][0][l] += dp[i-1][j][0][l];
                    dp[i][j][0][l] += dp[i-1][j][1][l];
                    if(j>0){
                        // 前を使う
                        dp[i][j][0][l] += dp[i-1][j-1][0][l];
                        // 後ろを使う
                        dp[i][j][1][l] += dp[i-1][j-1][0][l];
                        dp[i][j][1][l] += dp[i-1][j-1][1][l];
                    }
                }
            }
        }
    }
    vector<mint> res(n+1, mint(0));
    rep(j,n+1){
        rep(k,2){
            rep(l,2){
                res[j] += dp[n][j][k][l];
            }
        }
    }
    return res;
}

提出コード

ABC214-H Collecting

問題概要

問題リンク

$K$人で分担して有向グラフ上の落とし物をできるだけ多く拾う問題。

最小費用流問題

強連結成分にある落とし物はすべて取るのが最適なので、強連結成分一つをまとめて1つの頂点として考えた新しいグラフを作ります。そのグラフはDAGになります。(このとき、頂点$1$から辿ることができない頂点とその頂点から出てる辺は無視します)。

サンプル$1$の場合、次のようなグラフを作り$S$から$T$へ$K=2$だけ流せば最小コストの符号を取ったものが答えとなる。

しかし、負辺があるので、(私が知っている)アルゴリズムが適用できない。

負辺を取り除いたものがこちらです。

SからTまでグラフにそって適当なルートを通ったときに、通った辺のコストが「全体の落とし物のうち拾えなかった個数」を示しています。

このようなグラフは、強連結成分分解後に$M$頂点にしてトポロジカル順に頂点番号をつけたグラフについて、次のような操作によって機械的に構築できます。

各頂点$u$ごとに$i_u$と$o_u$を用意して、$i_u$から$o_u$に$(1,0)$と$(\infty,X_u)$の辺を張る。$X_u$
辺$(u,v)$に対して、$o_u$から$i_v$に$(\infty, X_{u+1}+X_{u+2}+\cdots+X_{v-1})$の辺を張る。
$S$から$i_1$に$(K,0)$の辺を張る。
各頂点$u$ごとに、$o_u$から$T$に$(\infty,X_{u+1}+X_{u+2}+\cdots +X_M)$の辺を張る。

各頂点について容量が$1$の辺があるのは、一人だけ「$X_u$を拾えなかった」ことを回避できるからです。よって、求まったコストを$K\sum_u X_u$から引けば答えになります。

提出コード

参考サイト

kmjp’s blog 2021-08-16 AtCoder ABC #214 : H - Collecting

感想

フローのこういうテクニックは覚えていきたい。

ABC215-G Colorful Candies 2

$N$個のキャンディがあり、$i$番目のキャンディの色は$C_i$である。 $K=1,2,\cdots,N$について、$N$個のうち$K$個のキャンディを選ぶ(同様に確からしい)とき、キャンディの種類数の期待値を求める問題。

式を作る

とりあえず$K$を固定して考える。確率変数$X_i$を種類$i$のキャンディを$1$以上選ぶとき$1$、選ばないとき$0$とすると、答えは次の式で求められる。 $$ E\left[\sum_i X_i\right] = \sum_i E\left[X_i\right] $$ 線形性で右辺に変形できる。その種類のキャンディが$m$個あった場合に$1$つ以上選ぶ組み合わせは$_N \text{C} _K - _{N-m} \text{C} _K$通りと二項係数で計算できる。

この計算方法だと、各$K$について最大$N$種類の計算をすることになるので、$O(N^2)$かかりそうだが、ちょうど$x$個ある種類のキャンディをまとめて数え上げれば$O(N\sqrt(N))$になる(詳しくはコード、計算量の節を参照)。

メインの実装自体はかなり簡潔。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main(void){
    std::cin.tie(0)->sync_with_stdio(0);
    int N;cin>>N;
    Combination<mint> comb(N+1);
    map<int,int>mp;
    rep(i,N){
        int c;cin>>c;
        mp[c]++;
    }
    map<int,int> mp2;
    for(auto&[k,v]:mp){
        mp2[v]++; //v個あるキャンディの種類数
    }
    for(int k=1;k<=N;k++){
        mint ans = 0;
        for(auto&[m,a]:mp2){
            mint A = a;
            ans += (comb.com(N,k) - comb.com(N-m,k)) / comb.com(N,k) * A; 
        }
        cout << ans << endl;
    }
}

mapを使っているため定数倍が重め。

提出コード

計算量について

$a_i$を種類$i$の個数だとすると、種類数(キャンディが$1$個以上ある)が$M$個、キャンディの総数が$N$個のとき、次の条件たちを満たす。

$a_1+a_2+\cdots+a_M=N$
$1 \leq a_i \leq N$

計算量は、$a_i$の種類数を$D$とすると、$O(DN)$である。$D$は高々$O(\sqrt N)$にしかならないというのがミソである。

なぜなら、$D$をできるだけ大きくしようとすると、$a_i$はできるだけ小さくするべきなので、 $a_1 = 1, a_2 = 2, \cdots$と設定していくべきであり、$1+2+3+\cdots+D = O(D^2) = O(N)$となる。

感想

今回の記事の中ではかなり簡単に見えるが、$X_i$の定義を思いつくところは経験値が必要だと思った。

謝罪

ABC212-G Power Pair

問題概要

感想

ABC212-H Nim Counting

問題概要

Hadamard変換

高速Walsh-Hadamard変換

問題に戻る

参考サイト

感想

ABC213-G Connectivity 2

問題概要

言い換え

g(S)の計算

f(S)の計算

部分集合の部分集合の列挙

感想

ABC213-H Stroll

問題概要

DP解

分割統治FFT

分割統治FFT

分割統治FFT(計算順序)

感想

ABC214-G Three Permutations

包除原理

グラフに変換

辺を張る

被らせる添字を選ぶ

DPで計算

ABC214-H Collecting

問題概要

最小費用流問題

最小費用流

負辺を取り除く

参考サイト

感想

ABC215-G Colorful Candies 2

式を作る

計算量について

感想