ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 138 D - Ki

お題箱より。

D - Ki

様々な木の問題を解く上で基本となるような実装なので、実装も含めて解説します。

解法

1回の操作のイメージを図にすると以下のようになります。

f:id:betrue12:20200224171708p:plain

実際には大量の操作があるので、これを1つ1つ処理していくことはできません。ではどうするかと言うと、以下の図のように考えます。

f:id:betrue12:20200224172627p:plain

まず与えられた  Q 回の操作について、頂点  p_{i} 「だけ」に値  x_{i} を足していきます。それが終わったら、根から順番に足された値を「押し流していく」ように伝えていきます。

図中の  p_{1}, p_{2} のように、伝えていった先に既に別の値がある場合、そのまま足し算をすれば良いです。このようにすると、 x_{1}, x_{2}, x_{3} がちゃんと  p_{1}, p_{2}, p_{3} を根とする部分木に伝わっていることが図から分かります。

実装

これを実装しましょう。木において「根から順番に葉まで」あるいは「葉から順番に根まで」値を伝えながら処理をしていきたい場合は、DFSをすることが多いです。

まずは実装の全体像を示します。

#include <bits/stdc++.h>
using namespace std;

int N, Q;
vector<int> edges[200000];
int64_t num[200000];

void dfs(int i, int p){
    for(int j : edges[i]) if(j != p){
        num[j] += num[i];
        dfs(j, i);
    }
}

int main(){
    cin >> N >> Q;
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
    }
    for(int i=0; i<Q; i++){
        int p, x;
        cin >> p >> x;
        num[p-1] += x;
    }
    dfs(0, -1);
    for(int i=0; i<N; i++) cout << num[i] << " \n"[i==N-1];
    return 0;
}

まずは入力を受け取ってグラフを構成します。edges[i] には頂点 i と辺で接続されている頂点の番号が入っています。このようにグラフを記憶する方法を「隣接リスト」と呼びます。

また変数 num に、各操作の「頂点  p_{i} だけに値  x_{i} を足す」という処理を行います。

そしてDFSをします。DFS部分のコードを再度抜き出します。

void dfs(int i, int p){
    for(int j : edges[i]) if(j != p){
        num[j] += num[i];
        dfs(j, i);
    }
}

引数 i は今見ている頂点、p はその親です。今回グラフを無向グラフとして扱っていて、edges[i] の中には親 p も含まれているので、下に下に見ていく際には親のほうに戻らないようにしないといけません。そのため p を引数として渡し、if(j != p) の条件で弾いています。

i の隣接頂点 j を見ていって、もし j が親でない(つまり子である)ならば、まずは値を伝えます(num[j] += num[i];)。そして再帰的に、頂点  j について dfs 関数を呼び出します。

こうすることで、先ほどの説明で書いた「根から順番に足された値を押し流していく」という処理が実現できることになります。

あとは、細かい補足をしておきます。

  • dfs関数を最初に呼び出すときは根を引数にしますが、根に親はないので、他の頂点番号のどれとも異なる値をセットしておけば良いです。私はよく -1 を使っています。
  • dfs関数内部の for(int j : edges[i]) は範囲for文と呼ばれるもので、vector などの各要素を順番に見ていくようなループを回します。便利。
  • 今回の問題の場合は「根をスタートにして、頂点を飛び越さないような順番で見ていく」限りはどのような順番で見ても良いので、DFSじゃなくてBFSでも正しい答えを求めることができます。ただDFSのほうが再帰で書きやすいことが多く、根付き木の頂点を順番に処理していく問題はほとんどの場合DFSがオススメです。

ACコード

上に貼ったものと同じですが、一応リンクを…

Submission #6988047 - AtCoder Beginner Contest 138

Codeforces Round #599 (Div. 1) B. 0-1 MST

お題箱より。

Problem - B - Codeforces

問題概要

 n 頂点の無向完全グラフがある。このグラフの辺のうち、指定される  m 本の辺の重みは  1 であり、それ以外の辺の重みは全て  0 である。

このグラフの最小全域木の重み合計を求めよ。

制約

  •  1 \le n \le 10^{5}
  •  0 \le m \le \min(\frac{n(n-1)}{2}, 10^{5})

解法

クラスカル法のアルゴリズムより、まずはコスト  0 の辺で連結にできる頂点を全て連結にしてしまい、それから残ったものをコスト  1 の辺で連結にすれば良いです。ただコスト  0 の辺は非常に多いので1つ1つ処理することはできません。

頂点数も辺数も非常に多いケース、例えば  n = m = 10^{5} である場合を考えましょう。このときコスト  1 の辺は「スカスカ」です。より具体的には、コスト  1 の辺だけで考えた次数の合計が  2m なので、1頂点あたり平均で  \frac{2m}{n} 本しかコスト  1 の辺が繋がっていないことになります。これは  n=m=10^{5} である場合たったの  2 本です。

つまりコスト  1 の辺が最も少ない頂点を1つ選んで  v とすると、 v に繋がっているコスト  1 の辺は  \frac{2m}{n} 本以下です。ということは頂点  v とコスト  1 の辺で繋がっていない(つまり、コスト  0 の辺で繋がっている)ような頂点が大量にあって、それらはノーコストで連結にすることができます。こうすると連結成分の個数が一気に減って、具体的には  \frac{2m}{n}+1 個以下になります。

f:id:betrue12:20200224164852p:plain

こうなると、既に連結になった頂点同士の辺はもう見る必要がありません。あとは頂点  v と連結にできなかった  \frac{2m}{n} 個以下の頂点それぞれについて、「相手の  n-1 個の頂点を全て試してコスト  0 の辺があれば連結にする」という処理をすれば、コスト  0 の辺だけでできる連結成分が得られます。あとは全頂点を連結にするのに足りない分、つまり連結成分の個数から  1 を引いたものが答えになります。

上記の手順は結局、前半は頂点  v に、後半は  \frac{2m}{n} 個以下の頂点について「相手の  n-1 個の頂点を全て試してコスト  0 の辺があれば連結にする」という処理をしていることになります。そのため全体計算量は  O( (n+m)\alpha(n) ) と評価できます。ここで  \alpha(n)アッカーマン関数逆関数(Union-Findの操作計算量)です。

ACコード

Submission #64559878 - Codeforces

Codeforces Round #623 (Div. 1) D. Tourism

Problem - D - Codeforces

計算量がキツキツなので想定解じゃないような気もするのですが、通せたので私の解法を書きます。

問題概要

 n 頂点の有向完全グラフが与えられ、各辺にコストが設定されている。

頂点1からスタートしてちょうど  k 辺を通って頂点1に戻る経路であって、奇閉路を含まないものの最小コストを求めよ。頂点、辺は同じものを何度でも通って良い。

制約

  •  2 \le n \le 80
  •  2 \le k \le 10 であって  k は偶数

解法

 k が最も大きい  k=10 のケースにおいて、経路は以下のようになっています。(実際には頂点や辺が重複していることがあります)

f:id:betrue12:20200224145146p:plain

この図で青く塗っている、始点/終点以外の偶数ステップ目で訪れる頂点は高々4個です。これを  n^{4} のループで全探索しましょう。 80^{4} = 40960000 なのでこの時点で危険な香りがしますね。

そうすると奇閉路を含まないようにコストを最小化するには、奇数ステップ目で踏む頂点を「偶数ステップ目で踏む頂点以外から」なるべくコストが小さくなるようにそれぞれ選べば良い、ということになります。

これはそれぞれ  n 個の頂点を全部調べれば求められますが、ちょっと時間が厳しいので前計算します。全ての頂点ペア  (i, j) について、全ての  k に対する  i \to k \to j の移動コストを求めて短い順にソートしたものを持っておきます(実装上は、さらに最後にINFを入れておくと楽です)。そうすれば頂点  (i, j) の間にある奇数ステップ目の頂点を探すときには、このリストを前から見ていけば最長でも  6 位で使えるものが見つかります。

外側のループが  n^{4} で、 \frac{k}{2}-1 個の奇数ステップ頂点として使えるものをそれぞれ最悪  \frac{k}{2}+1 位まで探すので、一応計算量評価をすると  O(n^{4}k^{2}) になります。ここまで  k が小さいと定数倍を無視する表記法を使うのもどうなんだろうという気もしますが、実際にランダムな最大ケースで試すと一番内側のループが2億回くらい回っていました。通って良かったですね。

ACコード

Submission #71722559 - Codeforces

Codeforces Round #579 (Div. 3) F1. Complete the Projects (easy version)

お題箱より。

Problem - F1 - Codeforces

問題概要

Polycarpは初期評価  rフリーランスである。

依頼が  n 個ある。 i 番目の依頼は受諾時点で  a_{i} 以上の評価が必要であり、完了後にレートが  b_{i} 変化する(これは負であることもあり得る)。依頼の順序は好きに選んで良いが、依頼を複数同時に持つことはできない。

全ての依頼を完了し、かつ完了時点での評価が非負であるような依頼の処理順序が存在するかどうか判定せよ。

制約

  •  1 \le n \le 300
  •  1 \le r \le 30000
  •  1 \le a_{i} \le 30000
  •  -300 \le b_{i} \le 300

解法

まずは  b_{i} \ge 0 であるような依頼を処理します。このときの順序は気にする必要がなく、できるようになったものから処理して良いです。ここで  b_{i} \ge 0 の依頼を全て処理できなかった場合、答えは NO です。

この後は  b_{i} \lt 0 の依頼を処理します。ここでの順序には気を配る必要があります。どのように依頼をこなしていくのが最適でしょうか?

簡単のため、まずは  a_{i} または  b_{i} のいずれかが同じようなケースを考えてみます。もし  a_{i} が同じならば、依頼を完了して評価が下がるほど次の依頼が受けにくくなるので、完了後の評価減少が少ない( b_{i} が数として大きい)ほうからこなしていくべきです。逆に  b_{i} が同じならば、受諾条件が厳しい、つまり  a_{i} が大きいものからこなしていくべきです。

ここからなんとなく、  a_{i} が大きいものや  b_{i} が大きいものを先にこなしたほうが良さそうな気がしてきます。では  a_{i} b_{i} のどちらも異なる場合どのようにするべきかと言うと、なんと  a_{i} + b_{i} が大きいほうを先に処理するのが常に最適になります。

これは考え方のテクニックとして、証明手順と一緒に覚えてしまったほうが良いです。証明していきましょう。

証明

まずは依頼が  (a_{i}, b_{i}), (a_{j}, b_{j}) の2つだけだとして、どっちを先に処理したほうが得なのかを具体的に計算します。今回の問題における「得」とは何なのか…という点ですが、両方の依頼をこなせるかどうかが重要なので、「得」とは両方の依頼を完了できるための条件が緩いことです。この条件は、具体的には依頼を受ける前の評価値が○○以上である、というものになります。

 b_{i} が負であるせいで数式の大小が若干分かりにくくなるので、 |b_{i}| を使うことにしましょう。依頼を受ける前の評価値を  r とします。依頼を  i \to j とこなしたときの評価値の推移と受諾できる条件は、

  1. 依頼  i を受ける。その受諾条件は  r \ge a_{i} であり、完了後に評価は  r-|b_{i}| となる。
  2. 依頼  j を受ける。その受諾条件は  r-|b_{i}| \ge a_{j} であり、完了後に評価は  r - |b_{i}| - |b_{j}| となる。

という流れになるため、この依頼をともに完了できる条件は  r \ge \max(a_{i}, a_{j} + |b_{i}|) となります。

もし依頼を  j \to i とこなした場合、同様に考えて条件は  r \ge \max(a_{j}, a_{i} + |b_{j}|) となります。

 R_{1} = \max(a_{i}, a_{j} + |b_{i}|), R_{2} = \max(a_{j}, a_{i} + |b_{j}|) として、この値が小さいほど「緩い」条件になります。それぞれの  \max の中身のうちどっちが大きいかで場合分けします。

 a_{i} \gt a_{j} + |b_{i}| のとき

 R_{1} \max の中身について見ています。このときは  R_{1} = a_{i} となり、さらに  R_{2} = a_{i} + |b_{j}| となります。このことから  R_{1} \lt R_{2} であり、依頼  i を先にやるべきです。

 a_{j} \gt a_{i} + |b_{j}| のとき

次は  R_{2} \max の中身について。この場合は逆に  R_{1} \gt R_{2} になり、依頼  j を先にやるべきです。

上2つでない場合

このときは  R_{1} = a_{j} + |b_{i}|, R_{2} = a_{i} + |b_{j}| となります。このとき  R_{1} \le R_{2} となる条件は、移行して

(★)  a_{i} - |b_{i}| \ge a_{j} - |b_{j}|

という条件になります。これが依頼  i を先にやるべき条件であり、冒頭に書いた「 a_{i} + b_{i} が大きいほうを先に」という条件がここで出てきます。

このように3つの場合分けをしてきましたが、実際には  a_{i} - |b_{i}| \ge a_{j} - |b_{j}| の式だけで判定をすることができます。なぜなら、

  •  a_{i} \gt a_{j} + |b_{i}| のときは、★の不等式は必ず真となり、結果として「依頼  i を先にやるべき」と判定される。
  •  a_{j} \gt a_{i} + |b_{j}| のときは、★の不等式は必ず偽となり、結果として「依頼  j を先にやるべき」と判定される。

と、★の不等式を使って判定すると全てのケースについて正しい結果になるからです。

証明の続き

これで依頼が2つだけの時は証明できたので、一般のケースについて考えます。これは「先ほどのソート順を破っているような並べ方は、隣り合ってソート順に違反している2要素を交換することで必ず良く(条件を緩く)できるので、最適解になり得ない」というロジックを使います。バブルソートのように違反箇所を交換していって、結果としてソートされた状態が一番いい状態だ…というロジックです。

厳密には以下の点を全てチェックして証明完了となります。

  • 隣り合う2要素の交換は、「それらの2依頼を受ける直前の評価」以外の条件に影響を与えないこと。
  • 違反箇所の交換する操作が有限回で終わること。
  •  a_{i} + b_{i} が同じ要素はどのように並んでいても条件に影響しないこと。

最後に

これを思いつくポイントですが…要素を順番に処理していく際に何らかのソート条件でソートすると最適な順序になるという問題では、

  1.  a_{i} が同じだとすると、 b_{i} をどうなっている順に取っていくのが良いか」あるいはその逆を考えてみる
  2. 隣り合う2要素を並び替えたときに得する/損する条件を考える

というのが糸口になり得ます。ただ今回の問題では場合分けが入ってストレートに不等式が出てこないので少し難しいですね。

2の考察をした時に直接不等式が出てきて、それがソート条件としてそのまま使えるような問題もあります。例えばこの回のC問題などはそうですね。

ACコード

Submission #58737114 - Codeforces

合成数modでの二項係数を用いた数え上げ

先日やっていたバチャで出てきたので、まとめておきます。

この記事では二項係数を  _{n}C_{k} と表記します。また法を  M とします。

はじめに

 _{n}C_{k} が必要となる  n, k の最大値をそれぞれ  N, K として、 O(N^{2}) O(NK) が許される制約であれば、パスカルの三角形で全部計算できます。こちらのほうが圧倒的に楽なので間に合う場合はこちらを使いましょう。

vector<vector<int64_t>> comb(N+1, vector<int64_t>(N+1));
for(int i=0; i<=N; i++){
    comb[i][0] = comb[i][i] = 1;
    for(int j=1; j<i; j++) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % M;
}

やり方

アウトライン

中国剰余定理を使います。

中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

まず  M素因数分解して、素数 P_{i} = p_{i}^{c_{i}} の積に分解します。

求めたい答え(の  \bmod を取る前の値)を  A とします。 A \bmod M を求める代わりに、  A \bmod P_{i} を求めて、中国剰余定理で復元します。

例えば  M = 180 であれば、これは  2^{2}\times 3^{2}\times 5素数冪の積に分解できるので、 A \bmod 4 A \bmod 9 A \bmod 5 をそれぞれ別々に求めて復元します。

この  A が二項係数の足し・引き・掛け算で計算できるようなときに、 A \bmod P_{i} を求める方法を書いていきます。

二項係数

 M が十分大きい素数である場合は、階乗とその逆元を前計算しておいて  O(1) _{n}C_{k} を求める方法が広く使われています。ただし  M素数でない場合や、  M が小さくて  n M 以上になってしまう場合は、一般には逆元が取れると限らないためこの方法は使えません。ですが、これを応用することにします。

素数 p、法とする素数冪を  P = p^{c} と書くことにします。このとき  n! は、

  •  n! の中の素因数  p を全て取り除いたものを、 \bmod P で計算したもの
  •  n! の中に素因数  p がいくつ含まれるか

の2つで特徴付けられます。これらの値を順に  x, y として、 n! \leftrightarrow (x, y) と表記することにします。

例えば  P=2^{2}=4 を法として  6! を計算する場合は、 1\times 2\times 3\times 4\times 5\times 6 の中に素因数  2 4 つ含まれ、それらを除くと  45 \equiv 1 \bmod 4 なので、 6! \leftrightarrow (1, 4) となります。

ここで  x の値が  p の倍数になることはありません。例えば  p=2 として、素因数に  2 を含まない奇数だけを掛け算した値が、 \bmod 4 0, 2 になることはありません。

 n! に対応する値  (x, y) は、 0!, 1!, 2!, ..., n! と順次計算していくことができます。 (n-1)! から  n! を計算する際には、 n に素因数  p がいくつ含まれるかを計算して、 x, y をそれぞれ処理すれば良いです。

そして二項係数

 \displaystyle _{n}C_{k} = \frac{n!}{k!(n-k)!}

 \bmod P で計算する際も、これらの値から計算することができます。

 x については、分母にあるものに対しては  \bmod P での逆元を計算して掛ければ良いです。 P素数とは限らないので、フェルマーの小定理ではなく拡張ユークリッドの互除法を使いましょう。 n! \leftrightarrow (x, y) において  x p の倍数になることはない、つまり  P と互いに素であることは保証されるので、拡張ユークリッドの互除法は適用可能です。

「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita

 y については、分母にあるものをマイナスとして扱って足し算すれば良いです。二項係数は整数になるので、この値が非負であることは保証されます。

こうして得られた二項係数が  _{n}C_{k}  \leftrightarrow (X, Y) と計算できたとして、ここから  _{n}C_{k} \bmod P の値を求めます。これは  Y \ge c であれば  0 であり、そうでなければ  X p^{Y} \bmod P を実際に計算してあげれば良いです。

これで  _{n}C_{k} \bmod P が計算できたので、これらの足し・引き・掛け算で構成される値は  \bmod P で計算できます。 (x, y) の形式から実際の  \bmod P での値に直してしまった後は、逆元は一般には取れないので注意です。

長いですが実装例です。

// サブルーチン群
void add(int64_t& a, int64_t b, int64_t mod){
    a = (a+b) % mod;
}
void mul(int64_t& a, int64_t b, int64_t mod){
    a = a*b % mod;
}

vector<pair<int64_t, int>> prime_division(int64_t n){
    vector<pair<int64_t, int>> ret;
    for(int64_t i=2; i*i<=n; i++){
        int cnt = 0;
        while(n % i == 0){
            n /= i;
            cnt++;
        }
        if(cnt) ret.emplace_back(i, cnt);
    }
    if(n > 1) ret.emplace_back(n, 1);
    return ret;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a, int64_t mod){
    int64_t x, y;
    extgcd(a, mod, x, y);
    return (MOD + x%mod) % mod;
}

// 素数冪を (p, c) で表現したもの
vector<pair<int64_t, int>> primes;
// 素数冪 p^c の実際の値
vector<int64_t> ppow;
// 階乗を (x, y) 形式で表現したもの
vector<vector<pair<int64_t, int>>> fact;


// 素因数分解をして素数冪ごとにfactを前計算
void create_composite_mod_table(int N, int64_t M){
    primes = prime_division(M);
    int sz = primes.size();
    ppow.resize(sz, 1);
    fact.resize(sz);
    for(int pi=0; pi<sz; pi++){
        int64_t p = primes[pi].first, cnt = primes[pi].second;
        while(cnt--) ppow[pi] *= p;

        auto& f = fact[pi];
        f.resize(N+1);
        f[0] = {1, 0};
        for(int i=1; i<=N; i++){
            f[i] = f[i-1];
            int n = i;
            while(n%p == 0){
                n /= p;
                f[i].second++;
            }
            mul(f[i].first, n, ppow[pi]);
        }
    }
}

// 二項係数を計算
int64_t comb_mod(int n, int k, int pi){
    auto &a = fact[pi][n], &b = fact[pi][k], &c = fact[pi][n-k];
    int64_t p = primes[pi].first, cnt = primes[pi].second;
    int64_t pp = ppow[pi];
    int pw = a.second - b.second - c.second;
    if(pw >= cnt) return 0;

    int64_t v = a.first;
    mul(v, inv_mod(b.first, pp), pp);
    mul(v, inv_mod(c.first, pp), pp);
    while(pw--) mul(v, p, pp);
    return v;
}

問題例

Codeforces Div.1の問題です。

問題:Problem - D - Codeforces

ACコード:Submission #71631654 - Codeforces

Educational Codeforces Round 34 G. Yet Another Maxflow Problem

バチャでやってて結構面白かったので。

Problem - G - Codeforces

問題概要

以下のように構成される、頂点数  2n・辺数  2(n-1)+m の有向グラフを考える。

  • 頂点は  n 個ずつの2グループに分類され、それぞれAパート・Bパートと呼ぶ。頂点を  A_{1}, ..., A_{n} B_{1}, ..., B_{n} と表記する。
  •  1 \le i \lt n について、 A_{i} から  A_{i+1} に伸びる容量  x_{i} の辺と  B_{i} から  B_{i+1} に伸びる容量  y_{i} の辺が存在する。
  • それらに加えて、Aパートに属する頂点からBパートに属する頂点に伸びる辺が  m 本与えられる。

このグラフについて  A_{1} を始点、 B_{n} を終点とする最大流量を求めたい。初期状態および以下のようなクエリを順に  q 個処理したそれぞれの時点において、この最大流量を求めよ。

  • 整数  v, w が与えられる。 A_{v} から  A_{v+1} に伸びている辺の容量を  w に変更する。

制約

  •  2 \le n, m \le 2\times 10^{5}
  •  0 \le q \le 2\times 10^{5}
  • 与えられる辺は問題概要に記した条件を満たし、容量は  1 以上  10^{9} 以下

解法

最大流量を求める貪欲アルゴリズム

説明の都合で呼び名がほしいので、Aパートの頂点からBパートの頂点に向かう辺のことを「AB辺」と呼ぶことにします。

クエリ対応は後で考えるとして、まずはあるグラフの状態についての最大流量の求め方を考えます。今回のグラフの構成から、最大流は以下のように求めることができます。

  • まず、 A_{1} から直接伸びるAB辺でBパートに行くようなフローを流せるだけ流す。
  • 次に、  A_{1} \to A_{2} と流れ、 A_{2} から伸びるAB辺でBパートに行くフローを流せるだけ流す。
  • ...
  • 最後に、 A_{1} \to \cdots \to A_{n} と流れ、 A_{n} から伸びるAB辺でBパートに行くようなフローを流せるだけ流す。

つまり  A_{1} になるべく近いところから伸びるAB辺から貪欲に流せるだけ流していくことで、全体の最大流量を求めることができます。

その正当性はFord-Fulkersonのアルゴリズムの動作から証明することができます。Ford-Fulkersonは流量が増加するパスを好きに選んで流せるだけ流すことを繰り返して良い、ただし既にフローを流している辺を逆流して相殺する可能性は考慮すること、というアルゴリズムです。

先ほどの貪欲アルゴリズムの動きを追ってみます。 A_{i} から伸びるAB辺を考える時に既に使われている辺は、 A_{i} 以前を始点とする辺とBパート内部の辺だけです。これらの辺は逆流しても得をしません。Bパート内部だけを逆流することに全く意味はないですし、Aパート側に戻ったとしてもその後に結局  A_{i} に戻ってくることになります(Aパートに戻った後に  A_{i} より手前でBパートに移りゴールするようなパスがあるなら、そのパスはとっくに使われているはずです)。

f:id:betrue12:20200222014137p:plain

つまり既に流したフローを逆流することは考えなくて良いため、先ほどの貪欲が正しく動作することが分かります。

Aパート内部の辺容量を無限大として前計算

Aパート内部の辺容量はクエリで変わってしまうので、それに依存しない値を前計算して活用できないでしょうか。具体的には、まずAパート内部の辺容量を全て無限大と仮定してしまいましょう。この状態で先ほどの貪欲法を考え、どれだけフローを流せるかを計算します。求めたいフローは、こうして求めたフローのうちの一部がAパート内部で「詰まった」ような形になります。

 A_{1}, ..., A_{n} と順番に、これらから伸びるAB辺を用いたフローを考えます。 A_{i} から  B_{j} に伸びるAB辺を用いて流せる最大流量は、このAB辺の容量と  B_{j} から  B_{n} までに通る辺全ての残容量の最小値になります。これはBパート内部の辺容量をセグメント木で管理しておけば、最小値を求める処理は区間min、実際に容量を使ってフローを流す処理は区間addで計算できます。

これを前から貪欲に行い、 A_{i} から伸びるAB辺で流せた合計流量を  L_{i} と書くことにします。こうするとグラフは結局、以下のようなものと同一視できることになります。

f:id:betrue12:20200222014151p:plain

クエリの処理方法

では実際にAパート内部の辺容量が有限である場合の計算方法を考えます。このとき先ほど求めた流量が、Aパート内部が「詰まる」ことにより流せなくなってきます。つまり先ほど求めた  L_{1}, ..., L_{n} を前からフロー1単位ずつ見たときに、その途中までを流せるということになります。

f:id:betrue12:20200222014556p:plain

では、ある整数  k について  L_{1}, ..., L_{k} が全て流しきれるような条件は何でしょうか。Aパート内部の辺容量と各流量が満たすべき条件を整理しましょう。

f:id:betrue12:20200222021346p:plain

 L_{1}, ..., L_{i} までを全て流した上で、 A_{i} \to A_{i+1} の辺に流せる流量を  X_{i} とします。これは1つ上で余った流量とこの辺の容量の最小値、つまり  \min(x_{i}, X_{i-1} - L_{i}) と計算できます。これが  L_{i+1} 以上であれば  L_{i+1} が全て流せることになります。

この  X_{i} を順次展開していくと、結局  L_{k} が全て流せる条件は

 i = 1, ..., k-1 の全てについて、 x_{i} - L_{i+1} - L_{i+2} - \cdots - L_{k-1} \ge L_{k} が成り立つこと

となり、これはさらに  L_{i} の累積和  S_{i} = L_{1} + \cdots + L_{i} を用いると

 i=1, ..., k-1 の全てについて、  x_{i} + S_{i} \ge S_{k} が成り立つこと

と簡潔に表現することができます。

この条件を満たす最大の  k は、 x_{i} + S_{i} をセグメント木で管理しておくことで二分探索で求めることができます。そのような  k を求めることができれば、あとは  A_{k+1} から流せるフローを  L_{k+1} のうちどれだけ流せるかを計算して足すことで答えを求めることができます。

計算に使う値のうち、 L_{i}, S_{i} はクエリで変化せず、クエリで  x_{i} が変化することはセグメント木で対応できます。これでクエリが処理できました。

ACコード

Submission #71505130 - Codeforces

なんか公式Editorialは初手で最小カットに言い換えていて全然方針が違ったんですが、考察を進めると非常にキレイな構造になって解けたので面白かったです。

Codeforces Round #621 (Div. 1 + Div. 2) E. Cow and Treats

Problem - E - Codeforces

問題概要

 n 本の草が横一列に並んでいて、 i 本目の草の味は整数  s_{i} で表現される。また  m 頭の牛がいて、 i 頭目の牛は味  f_{i} の草を好み、それを  h_{i} 本食べると満足する。

以下の処理を行う。

  1. 互いに素な牛の集合  S_{L}, S_{R} を選ぶ。一方または両方が空であってもよい。
  2.  S_{L} の牛は左端から、 S_{R} の牛は右端から、好きな順番で出発する。
  3. 各牛  i は訪れた草のうち味  f_{i} のものだけを食べながら進み、 h_{i} 本の草を食べると満足してその場所に留まる。草は一度食べられると消滅する。別の牛が留まっている場所は通過できない。

出発順を適切に選んだ時に  S_{L}, S_{R} に含まれる全ての牛が満足する時、この  (S_{L}, S_{R}) を良い集合対と呼ぶことにする。良い集合対における  |S_{L}| + |S_{R}| の最大値を求め、さらにその最大値を達成する良い集合対の総数を  \bmod 10^{9}+7 で求めよ。

制約

  •  1 \le n \le 5000
  •  1 \le m \le 5000
  •  1 \le s_{i}, f_{i}, h_{i} \le n
  • 同一の  (f_{i}, h_{i}) を持つ牛は2頭以上存在しない

解法

境界の全探索と重複の排除

まず、同じ味を好む牛は左右それぞれに高々1頭しかいません。2頭以上いる時には、必ず最初に出た牛に他の牛が通せんぼされるからです。

左側の先頭の牛が進む位置と右側の牛が進む位置の境界を  n+1 通り全探索することを考えます。

f:id:betrue12:20200219233739p:plain

この境界を決めると、境界の左右それぞれに存在する各味の草の本数が決まります。そして各味ごとに、 h_{i} がその本数以下であるような牛を左右それぞれ1頭または0頭採用することになります。逆に全ての味についてこれを満たす選び方をしていれば、止まる場所が遠い順に牛を出発させることで、必ず進路を妨害されることなく全ての牛を満足させることができます。

つまり集合に含める牛は味ごとに独立に決められるので、味ごとに採用する牛の頭数(0~2頭)の最大値を求めて全て足せば、その境界に対応する牛の頭数の最大値が求められます。これを全ての境界について試せば良さそうです。

ただし今回の問題では場合の数も要求されているため、重複を排除する必要があります。例えば上の図のような状況では、赤い境界線が図より1つ右側にあるときでも同じ場合が数えられてしまいます。

これを防ぐために、

  • 境界が左端にある場合を考える時は、左側から出発する牛は存在しない。
  • それ以外、つまり境界の左隣に草がある時は、左側の先頭の牛がちょうどその草を食べて止まるような場合のみを数えることにする。

というルールを追加します。このルールによって、例えば上の図のような牛の選び方は図に示した位置の境界を考えている時だけカウントされることになり、重複を排除できます。

具体的な処理アルゴリズム

具体的な処理の仕方を考えましょう。まず各牛を味ごとに分類し、同じ味の中では  h_{i} が小さい順にソートしておきます。制約より、ここで味も  h_{i} も等しい牛が複数存在することはありません。

左右の境界を全探索します。そして各味ごとに、左右それぞれの領域に何本の草があるかを累積和や差分更新などで求めて、採用する牛の頭数の最大値とその選び方の数を以下のように求めます。

見ている味が、境界の左隣の草の味ではない時

各味について、その味を好む牛はあらかじめ  h_{i} の値でソートしておきました。これを左右それぞれに存在する草の数で二分探索することで、小さい方から何頭目までの牛が候補になるかを計算できます。この頭数を左右それぞれ  n_{L}, n_{R} としましょう。

このとき、左右ともに1頭ずつの牛を採用する場合の数は  n_{L}n_{R} - \min(n_{L}, n_{R}) と計算できます。左右それぞれ独立に牛を選んだペアの個数から、同じ牛を選んでいるものを除くという計算です。この値が正である時は牛を2頭採用できます。

2頭採用できないならば、1頭だけを選ぶ場合の数は  n_{L} + n_{R} で、これが正なら1頭採用になります。これも  0 ならば0頭採用です。

見ている味が、境界の左隣の草の味である時

この時は左側の牛は完全に固定されます。境界の左側に今見ている味の草が  x 本あるとすると、ちょうど  h_{i} = x の牛を採用する必要があります。これがもし存在しないならば、この境界で考えるべき場合の数はそもそも存在しないので、処理を中断します。

その上で右側の牛として採用できる牛の候補を二分探索で求めます。もしこの候補の中に先ほど左側で採用した  h_{i} = x の牛が存在する場合は取り除く必要があります。

右側の牛として採用できる候補の数を  n_{R} として、これが正なら2頭採用で場合の数は  n_{R} 0 なら1頭採用で場合の数は  1 になります。

これで各味についての牛の頭数の最大値と場合の数が求められたので、それぞれ総和/総積を取ることで全体での最大値と場合の数を求められます。あとは全ての境界についての結果をマージすれば答えを求めることができます。

ACコード

Submission #71338331 - Codeforces