Learning Algorithms

アルゴリズムの勉強メモ

CS Academy 060 E. Flip the Edges

CS Academy 060 E. Flip the Edges

CS Academy

感想

DPの書き方がよくわからなかったので、pekempeyさんより解説をいただきました。

解法

まず二度以上選ぶ辺は存在しないことが言えます。なぜなら、もし仮にそのような部分があるとき、そのような部分は反転しなかったことにすれば、パスの個数は同じまま辺の数を減らせるからです。

まずパスの数を最小化し、それが同じなら辺の数を最小化する、ということなので、(パスの数, 辺の数)というペアで状態を持ってDPができればよいとわかります。これをどのように持ってどのように遷移するかが問題です。

$dp_0$ を根からの辺がもう余っていない部分木、$dp_1$ を根からの辺が一本余っていて、これからどこかに繋ぐことができる状態の部分木(その辺はまだ使ったものとはカウントしない)、と定義すると、次の遷移を考えることができます。ただし辺が二本以上余るような状態は無駄なので、考慮しなくて良いです。

f:id:KokiYamaguchi:20171209111446j:plain

これは、一本のパスというのは両端で完結している(それはそうなのですが)という性質を陽に持つことで、無駄なく使っているパスの個数を漏れなく数えるということをきれいにやっています。

この遷移をそのまま書けば、答えは $dp_0 $です。

実装
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

#define mp make_pair

static const int INF = 0x3f3f3f3f;

struct edge {
        int to;
        int type; //0 -> choose, 1 -> not choose, 2 -> whichever
};

int main() {
        int n;
        scanf("%d", &n);
        vector<vector<edge>> g(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b, c, d;
                scanf("%d%d%d%d", &a, &b, &c, &d);
                a --, b --;
                if (d != 2) d = c != d;
                g[a].push_back({b, d});
                g[b].push_back({a, d});
        }
        vector<pair<int, int>> dp0(n), dp1(n);
        function<void (int, int)> dfs = [&](int u, int prev) {
                dp0[u] = mp(0, 0);
                dp1[u] = mp(1, 0);
                for (auto e : g[u]) { 
                        int v = e.to, type = e.type;
                        if (v == prev) continue;
                        dfs(v, u);
                        pair<int, int> x0(dp0[u].first + dp0[v].first, dp0[u].second + dp0[v].second);
                        pair<int, int> y0(dp1[u].first + dp0[v].first, dp1[u].second + dp0[v].second);
                        pair<int, int> x1(dp1[u].first + dp1[v].first - 1, dp1[u].second + dp1[v].second + 1);
                        pair<int, int> y1(dp0[u].first + dp1[v].first, dp0[u].second + dp1[v].second + 1);
                        if (type == 0) {
                                dp0[u] = x0;
                                dp1[u] = y0;
                        } else if (type == 1) {
                                dp0[u] = x1;
                                dp1[u] = y1;
                        } else {
                                dp0[u] = min(x0, x1);
                                dp1[u] = min(y0, y1);
                        }
                }
        };
        dfs(0, -1);
        printf("%d %d\n", dp0[0].first, dp0[0].second);
        return 0;
}

競プロにおけるオイラー路とその応用について

この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。

競プロにおけるオイラー路とその応用について

はじめに

この記事では、オイラー路の基礎、そして主に競技プログラミングで使えるその応用についてできるだけ詳しく書きます。

最初の方は基礎的な定義や解説を書いているので、オイラー路とは何かをすでにご存知の方は、無向オイラー路の構築あたりからどうぞ。

説明で出てくるグラフは特に断らない限り連結で、多重辺や自己辺は基本的にあってもよいものとします。

また、もし必要があればこの記事に載せたコードはすべて自由に使って頂いて構いません。

例題で扱った問題は、はまやんはまやんさんによる記事からいくつか適切に選びました。情報ありがとうございます。

なにか問題等ありましたらTwitter @Ymgch_Kまで連絡いただけるとありがたく思います。


オイラー路とは?

一般にオイラーとは、あるグラフにおいて、すべての辺をちょうど一度だけ通るような路のことです。この路が閉路になっている場合は特にオイラー閉路と呼びます。


無向グラフのオイラー

まずは無向グラフにおけるオイラー路(無向オイラー)を考えます。以下の無向グラフにおいてオイラー路の一例を示すことができるでしょうか?

f:id:KokiYamaguchi:20171206140310p:plain

このグラフの場合、頂点7からスタートして、例えば以下のような順ですべての辺をちょうど一回使って、オイラー路を構成することができます。

f:id:KokiYamaguchi:20171206140347p:plain

このような、オイラー路が存在するグラフをオイラーグラフと呼びます。あるグラフが準オイラーグラフになるための必要条件について考えます。

あるオイラー路をとったとき、その路上の始点と終点を除く頂点に注目すると、必ず入ってくる辺と出て行く辺のペアを作れることがわかります。よって、始点と終点を除くどの頂点についても必ず次数が偶数である必要があります。一方、始点については出て行く辺が入ってくる辺に比べて一つ多く、終点については入ってくる辺が出て行く辺に比べて一つ多いため、いずれも次数が奇数であることがわかります。

よって次のことが言えます。

★あるグラフが準オイラーグラフであるための必要条件は、そのグラフの頂点のうち次数が奇数であるものがちょうど2個であることである。

また、始点と終点が一致する場合は、オイラー閉路が存在することになりますが、そのようなグラフを特にオイラーグラフと呼びます。オイラーグラフについても同様の考察をすることで、以下の必要条件が言えます。

★あるグラフがオイラーグラフであるための必要条件は、そのグラフのすべての頂点の次数が偶数であることである。


有向グラフのオイラー

次に有向グラフにおけるオイラー路(有向オイラー)について説明します(ほとんど同じ)。次の有向グラフは有向オイラーグラフです。

f:id:KokiYamaguchi:20171206153510p:plain

なぜなら、例えば次のような、始点、終点をともに頂点4とするオイラー閉路が存在するからです。

f:id:KokiYamaguchi:20171206153540p:plain

無向グラフのときと同様の考察をすると、各頂点についてやはり、入ってくる辺の数と出て行く辺の数が等しくなっていなければならないので、次の2つの必要条件が言えます。

★ある有向グラフが有向準オイラーグラフであるための必要条件は、ある1頂点について入次数 + 1 = 出次数が成り立ち(始点)、また別のある1頂点について入次数 = 出次数 + 1 が成り立ち(終点)、他のすべての頂点について入次数 = 出次数が成り立つことである。

★ある有向グラフが有向オイラーグラフであるための必要条件は、すべての頂点について入次数 = 出次数が成り立つことである。


無向オイラー路の構築

さて、今までの議論では、オイラー路が構築されたときの、そのグラフの必要条件だけを見てきました。以下では逆にそのようなグラフに対して、実際にオイラー路が構築可能であることを示します。

まず次の条件を満たす無向グラフにおいて、オイラーを一つ構築します。

★次数が奇数である頂点がちょうど2個である。

ここでは、ハイヤーホルザーのアルゴリズム(Hierholzer's Algorithm)によってオイラー路を構築します(Fleury's algorithmというものもありますが、こちらは実装量的にも計算量的にも非効率です)。

まず次数が奇数である頂点をそれぞれ始点 $S$ 、終点 $T$ とおきます。点 $S$ から任意の順番に辺を選んで破壊しながら進み、進める辺がなくなるまで進むことを考えます。このとき、行きつく先は必ず $T$ になることが言えます。なぜなら、 $S$ を出発した瞬間に、 $T$ 以外のすべての頂点( $S$ も含む)の次数は偶数であると考えることができ、従って $T$ 以外の頂点に進んだ場合は必ずその頂点から出ていける辺も存在するため、それ以上進めなくなる点としてありうるのは $T$ だけであるからです。

この時点ですべての辺を使っているなら、その路がオイラー路になるため、これで構築が終了します。そうでない場合は、すでに構築した路(これを路 $P$ とする)を基準にオイラー路を構築することができます。

具体的には、すべての辺を使うまで、次の操作を繰り返すことでオイラー路を構築できます。

(操作)路 $P$ を $T$ の方から順に戻っていくと、まだ使っていない辺をもつ頂点に達するはずである。この点を $Q$ とすると、$Q$ から任意の残っている辺を使って、それ以上進めなくなるまで任意の進み方で進む。その結果、必ず点 $Q$ 自身に戻るのでその路を $R$ とします。路 $P$ において、その途中の点 $Q$ から路 $R$ をそのタイミングで通ったかのように $P$ にマージする。すなわち $S → Q - R - Q → T$ とする。

点 $Q$ から任意の経路を進むとき、必ず $Q$ 自身に戻る(路 $R$ が閉路になる)ことは、上記と同じように示せます。すなわち、$Q$ を出発した瞬間以降、点 $Q$ 以外の全ての点の次数は偶数になっているため、それ以上進めなくなるまで進んだ場合、必ず $Q$ に戻るはずです。


以上の構築は文章だとわかりにくいので、以下の簡単な例で見てみます(特殊な例を挙げているだけなんじゃないかと思う人がもしいれば、いろんなグラフで自分で実験してみることをオススメします!)。

f:id:KokiYamaguchi:20171206183621p:plain

まず点 $S$ から $T$ に達するまで任意の進み方をした($S$ から辺を破壊しながら進み続けると、どうやっても $T$ にしかたどり着けないことに気付くはずです)ところ、以下のような順番で辺を通ったとします。

f:id:KokiYamaguchi:20171206184115p:plain

これが路 $P$ に対応しています。一方、残る辺は次のようになります。

f:id:KokiYamaguchi:20171206184349p:plain

辺が残っているので、上の操作をします。つまり、路 $P$ を $T$ の方から順にみていき、まだ使っていない辺に出会うまで戻ります。すると頂点5(これが上の点 $Q$ に対応します)に達した時に、他の辺が使えることがわかるので、そこから任意の方向に進みます。すると、頂点5から頂点5自身に戻るように以下のように進むことができます。

f:id:KokiYamaguchi:20171206184429p:plain

これが路 $R$ に対応しています。よって、順番に気をつけながら、元の路にこれをマージすることで、次のオイラー路を得ることができます。

f:id:KokiYamaguchi:20171206184516p:plain

同様に考えると次の条件を満たす無向グラフにおいて、オイラー閉路を構築することができます。

★すべての頂点の次数が偶数である。

これは任意の頂点を上の $S, T$ に対応させることで、全く同様に構築可能です。


有向オイラー路の構築

こちらも無向オイラー路の場合と全く同じように構築可能ですね。


実装

さて、ここから実装について書いていきます。

まず、あるグラフについて、オイラー(閉)路が存在するかどうかというのは、各頂点の次数の偶奇をチェックするだけでよいため、オイラー路が構築可能であると確認しているものと仮定します。

すると無向オイラー路の構築は以下のシンプルなコードによって実現できます。

void dfs(int u, vector<int> &trail) {
        for (int v = 0; v < g.size(); v ++) if (g[u][v] > 0) {
                g[u][v] --, g[v][u] --;
                dfs(v, trail);
        }
        trail.push_back(u);
}

より正確には、このアルゴリズムオイラー路の逆順の一例が得られます。ただしgは隣接行列のvectorであるとします。空っぽのtrailとスタートの頂点sを用いてdfs(s, trail)で呼び出して、その結果をreverseすればよいです。理由は上に述べた通りですが、辺を壊しながらひたすら進めるだけ進んで、進めなくなったらその頂点を確定させることで、最後に到達する頂点から順番に決めていくことができます。

これを隣接リストで書くと次のようになります。

void dfs(int u, vector<int> &trail) {
        while (!g[u].empty()) {
                int v = g[u].back();
                g[u].pop_back();
                for (int i = 0; i < g[v].size(); i ++) {
                        if (g[v][i] == u) {
                                g[v].erase(g[v].begin() + i);
                                break;
                        }
                }
                dfs(v, trail);
        }
        trail.push_back(u);
}


有向オイラー路の構築は辺の破壊が容易なので、もっとあっさりと書けます。

//隣接行列
void dfs(int u, vector<int> &trail) {
        for (int v = 0; v < n; v ++) if (g[u][v] > 0) {
                g[u][v] --;
                dfs(v, trail);
        }
        trail.push_back(u);
}

//隣接リスト
void dfs(int u, vector<int> &trail) {
        while (!g[u].empty()) {
                int v = g[u].back();
                g[u].pop_back();
                visit(v, trail);
        }
        trail.push_back(u);
}

以上の実装をまとめると、以下のようなライブラリとして使うことができます。あとで示す例題5のような、本当にオイラー路を求めるだけというようなときに瞬時に使えます。

//gが隣接リスト
//gを破壊する
vector<int> EulerianTrail(const int s, vector<vector<int>> &g, const bool directed) {
        function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) {
                while (!g[u].empty()) {
                        int v = g[u].back();
                        g[u].pop_back();
                        if (!directed) {
                                for (int i = 0; i < g[v].size(); i ++) {
                                        if (g[v][i] == u) {
                                                g[v].erase(g[v].begin() + i);
                                                break;
                                        }
                                }
                        }
                        dfs(v, trail);
                }
                trail.push_back(u);
        };
        vector<int> trail;
        dfs(s, trail);
        reverse(trail.begin(), trail.end());
        return trail;
}

//gが隣接行列
//gを破壊する
vector<int> EulerianTrail(const int s, vector<vector<int>> &g, const bool directed) {
        function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) {
                for (int v = 0; v < g.size(); v ++) if (g[u][v] > 0) {
                        g[u][v] --;
                        if (!directed) g[v][u] --;
                        dfs(v, trail);
                }
                trail.push_back(u);
        };
        vector<int> trail;
        dfs(s, trail);
        reverse(trail.begin(), trail.end());
        return trail;
}


実装から明らかですが、連結なグラフにおけるオイラー路構築の時間計算量は $O(m)$ です。オイラー路の解説と実装は以上になります。

ここから先は、5つの例題とその解法を、難易度順(?)に載せています。ここまでに述べたことを理解していればそこまで難しくはないので、ぜひすべて解いてオイラー路のプロになりましょう!

例題1(★)

パトロール | Aizu Online Judge

問題概要:省略です。

与えられるグラフが無向準オイラーグラフかどうかを判定するだけですね。

実装
#include <cstdio>
#include <vector>
using namespace std;

int main() {
        int a, b;
        vector<pair<int, int>> es;
        while (~scanf(&quot;%d%d&quot;, &a, &b)) es.emplace_back(a, b);
        int k  = 0;
        while (k < es.size()) {
                vector<int> deg(105);
                while (es[k].first != 0) {
                        deg[es[k].first] ++;
                        deg[es[k].second] ++;
                        k ++;
                }
                k ++;
                bool ok = true;
                for (int i = 3; i <= 105; i ++) if (deg[i] & 1) ok = false;
                if (deg[1] % 2 == 0 || deg[2] % 2 == 0) ok = false;
                puts(ok ? &quot;OK&quot; : &quot;NG&quot;);
        }
        return 0;
}

例題2(★★)

Kobutanukitsuneko | Aizu Online Judge

問題概要:文字列がいくつか与えられるので、そのすべてを使ってしりとりができるるかどうかを判定せよ。ただし、最後の文字列の語尾と最初の文字列の先頭も一致していなければいけない。

しりとりで重要なのは先頭と語尾の文字だけなので、そこに注目します。そこで、「"euler"という文字列を使う」という条件を「頂点"e"から頂点"r"に張られた辺を使う」という風に読み替えることができます。

この方法でグラフを構築すると、ある頂点からスタートして、すべての辺を重複なく使って元の頂点に戻るような路が存在するかを判定する問題に変わりますね。

したがって、このグラフが有向オイラーグラフであるかどうかを判定すればよいです。これをそのまま書くと次のようになります。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
        int n;
        while (scanf(&quot;%d&quot;, &n), n) {
                vector<int> in_deg(26), out_deg(26);
                for (int i = 0; i < n; i ++) {
                        string s;
                        cin >> s;
                        int a = s[0] - 'a';
                        int b = s.back() - 'a';
                        in_deg[a] ++, out_deg[b] ++;
                }
                bool ok = true;
                for (int i = 0; i < 26; i ++) ok &= in_deg[i] == out_deg[i];
                puts(ok ? &quot;OK&quot; : &quot;NG&quot;);

        }
        return 0;
}

しかしこれでは不十分で、連結でないオイラーグラフが2個以上あったりする場合などに対応できていません。つまりグラフの連結性を確認しておかなければいけません(ここでいう連結とは、グラフを無向グラフとみたときに連結であるということです)。よってUnionFindなどを使って連結性もみると、以下のようなコードになります。

実装
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
        int n;
        while (scanf(&quot;%d&quot;, &n), n) {
                UnionFind uf(26);
                vector<int> in_deg(26), out_deg(26);
                for (int i = 0; i < n; i ++) {
                        string s;
                        cin >> s;
                        int a = s[0] - 'a';
                        int b = s.back() - 'a';
                        in_deg[a] ++, out_deg[b] ++;
                        uf.unite(a, b);
                }
                bool ok = true;
                int cnt = 0;
                for (int i = 0; i < 26; i ++) if (in_deg[i] > 0 || out_deg[i] > 0) cnt ++;
                for (int i = 0; i < 26; i ++) {
                        if (in_deg[i] > 0 || out_deg[i] > 0) {
                                if (uf.get(i) != cnt) {
                                        ok = false;
                                        break;
                                }
                        }
                }
                for (int i = 0; i < 26; i ++) ok &= in_deg[i] == out_deg[i];
                puts(ok ? &quot;OK&quot; : &quot;NG&quot;);

        }
        return 0;
}

例題3 (★★★)

Problem - D - Codeforces

問題概要:長さ3の文字列が $n$ 個与えられます。これらがある一つの文字列のTrigramになっているかを判定し、そうであるならばその文字列を出力せよ。

例題2とほとんど同じ発想をします。つまりまず「文字列"abc"を使う」という条件を「頂点"ab"から頂点"bc"に張られた辺を使う」という風に読み換えてしまうことができます。

よってそのグラフが有向(準)オイラーグラフであるかどうかを判定すればよいです。ただし、こちらもやはりグラフが連結でない場合は明らかにダメなことに気をつけます。

例題2と違ってこちらは構築までしなければいけないので、上の構築のアルゴリズムを書きます。UnionFindなどによる連結性の判定は必要なく、オイラー路を構築したあとにまだ使っていないノードがあるかどうかをみればよいです。

実装
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <functional>
using namespace std;

//隣接リスト
//gを破壊する
vector<int> EulerianTrail(const int s, vector<vector<int>> &g, bool directed, vector<bool> &used) {
        function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) {
                used[u] = true;
                while (!g[u].empty()) {
                        int v = g[u].back();
                        g[u].pop_back();
                        if (!directed) {
                                for (int i = 0; i < g[v].size(); i ++) {
                                        if (g[v][i] == u) {
                                                g[v].erase(g[v].begin() + i);
                                                break;
                                        }
                                }
                        }
                        dfs(v, trail);
                }
                trail.push_back(u);
        };
        vector<int> trail;
        dfs(s, trail);
        reverse(trail.begin(), trail.end());
        return trail;
}

int main() {
        int n;
        scanf("%d", &n);
        
        //文字列を頂点に変換
        map<string, int> stov; //2文字 -> 頂点
        map<int, string> vtos; //頂点 -> 2文字
        int k = 0;
        vector<pair<int, int>> es;
        for (int i = 0; i < n; i ++) {
                string s;
                cin >> s;
                string a = s.substr(0, 2);
                string b = s.substr(1, 2);
                if (!stov.count(a)) stov[a] = k ++;
                if (!stov.count(b)) stov[b] = k ++;
                es.emplace_back(stov[a], stov[b]);
                if (!vtos.count(stov[a])) vtos[stov[a]] = a;
                if (!vtos.count(stov[b])) vtos[stov[b]] = b;
        }

        //グラフを構築する
        int m = n;
        n = stov.size();
        vector<vector<int>> g(n);
        vector<int> in_deg(n); //入次数を数える。出次数はg[i].size()でよい
        for (int i = 0; i < m; i ++) {
                int a = es[i].first, b = es[i].second;
                g[a].push_back(b);
                in_deg[b] ++;
        }

        //オイラー路を構築可能かを判定する
        int s = -1, t = -1;
        for (int i = 0; i < n; i ++) {
                if ((int) g[i].size() == in_deg[i] + 1 && !~s) s = i;
                else if ((int) g[i].size() + 1 == in_deg[i] && !~t) t = i; 
                else if (g[i].size() == in_deg[i]) continue;
                else return !printf("NO\n");
        }
        if (s == -1) s = 0; //オイラー閉路の場合

        //オイラー路を構築する
        vector<bool> used(n, false);
        auto trail = EulerianTrail(s, g, true, used);

        //連結性を判定する
        for (int i = 0; i < n; i ++) if (!used[i]) return !printf("NO\n");

        cout << "YES" << endl; //オイラー路の順番に辿って文字列を出力する
        for (int i = 0; i < trail.size(); i ++) {
                cout << vtos[trail[i]][0];
                if (i == trail.size() - 1) cout << vtos[trail[i]][1] << endl;
        }
        return 0;
}

例題4(★★★★)

Problem - E - Codeforces

問題概要:無向グラフが与えられるので、すべての辺に適切に向きをつけて、入次数と出次数が等しい頂点数を最大化せよ。

少しずつオイラー路っぽさが見えにくい問題になってきました。まず、すべての頂点の次数が偶数の場合を考えてみることにします。

するとそのグラフは無向オイラーグラフであることがわかります。ここで任意のオイラー閉路を作って、それを有向グラフのように見てやると、これは有向オイラーグラフであることになります。

よってすべての頂点について入次数と出次数が等しくなるように向きづけることができました。

ところで、もとのグラフには次数が奇数である頂点が存在します。このような頂点は、どのように向きづけても条件を満たすようにはできません。

そこで、次数が奇数であるような頂点のペアに対して勝手に1本辺を加えてやることを考えます。このようなペアは必ず余すことなく作ることができます(すべての辺は、ある2頂点の次数をそれぞれ1増加させているため、次数が奇数であるような頂点は必ず偶数個あるからです)。これですべての頂点の次数が偶数になったので、このグラフの上でオイラー路を構築すると考えればよいです。

これを連結成分ごとにやれば、すべての辺に向きをつけることができます。ただし勝手に付け加えた辺の向きづけは出力しないように注意します。

実装
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
#include <functional>
using namespace std;

int main() {
        int t;
        scanf(&quot;%d&quot;, &t);
        while (t --) {
                int n, m;
                scanf(&quot;%d%d&quot;, &n, &m);

                //グラフ構築
                vector<vector<int>> g(n, vector<int> (n, 0)); //nが小さいので隣接行列でやる方がよい
                for (int i = 0; i < m; i ++) {
                        int a, b;
                        scanf(&quot;%d%d&quot;, &a, &b);
                        a --, b --;
                        g[a][b] ++;
                        g[b][a] ++;
                }

                //次数が奇数である頂点を列挙する。
                vector<int> odd;
                int ans = n;
                for (int i = 0; i < n; i ++) {
                        int deg = 0;
                        for (int j = 0; j < n; j ++) deg += g[i][j];
                        if (deg & 1) {
                                odd.push_back(i);
                                ans --;
                        }
                }
                assert(odd.size() % 2 == 0); //そのような頂点の個数は必ず偶数個ある

                //次数が奇数である頂点を適当につないでいく。追加した辺であることがわかるようにしておく。これでつないだ結果多重辺になる場合もある。
                vector<vector<int>> added(n, vector<int> (n, 0));
                for (int i = 0; i < odd.size(); i += 2) {
                        int a = odd[i], b = odd[i + 1];
                        g[a][b] ++, g[b][a] ++;
                        added[a][b] ++, added[b][a] ++;
                }

                //任意の順番で各連結成分のオイラー路を構築し、-1で連結成分ごとに区切っている
                vector<int> used(n, false);
                function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) {
                        used[u] = true;
                        for (int v = 0; v < n; v ++) if (g[u][v] > 0) {
                                g[u][v] --, g[v][u] --;
                                dfs(v, trail);
                        }
                        trail.push_back(u);
                };
                vector<int> trail;
                for (int i = 0; i < n; i ++) {
                        if (!used[i]) {
                                dfs(i, trail);
                                trail.push_back(-1);
                        }
                }
                reverse(trail.begin(), trail.end());

                //付け加えた辺以外の向きを出力する
                printf(&quot;%d\n&quot;, ans);
                for (int i = 0; i < trail.size() - 1; i ++) {
                        if (trail[i] == -1 || trail[i + 1] == -1) continue;
                        int a = trail[i], b = trail[i + 1];
                        if (added[a][b]) {
                                added[a][b] --;
                                added[b][a] --;
                                continue;
                        }
                        printf(&quot;%d %d\n&quot;, a + 1, b + 1);
                }
        }
        return 0;
}

例題5(★★★★★)

Problem - C - Codeforces

最後です。

問題概要:無向グラフが与えられるので、各頂点について入次数と出次数がともに偶数個になるように辺の向きづけを行い、必要に応じて最小限の個数だけ辺を追加せよ。

まず最初に例題4と同様に、次数が奇数個の頂点が存在する場合、辺を追加しない限り条件を満たすようにできません。よって、これらの頂点同士を無向辺でつなぎます。とりえあず最低でも(次数が奇数の頂点数 / 2)本の辺は必ず追加しなければいけないのは明らかです。

この操作によってすべての頂点の次数が偶数になりました。そうなると、今まで通りオイラー閉路を構築したい気持ちになるので、構築してみることにします。

さて、このオイラー路は当然条件を満たしているわけではありません。そこで次のようなことを考えます。

オイラー路というのは、各頂点を通過するたびに、その頂点の入次数と出次数を1ずつ増やすものでした。これを、入次数または出次数のいずれかを2増やす、という風にできないでしょうか。

それをするために、オイラー路の向きを、交互に逆向きにすることを考えます。すると、頂点を通過するたびに入次数または出次数のいずれかが2増えることになります。よって、この方法ですべての辺を使って各頂点を通過すれば、条件を満たすようにできるはずです!

しかし、このオイラー閉路におけるスタートの頂点はまだ条件を満たしていない可能性があります。具体的には、オイラー閉路ではすべての辺を使っているので、すべての辺の個数が奇数の場合はまだ条件を満たしていません。その場合は、スタートの頂点は入次数も出次数も奇数になっているはずなので、そこに自己辺を追加することで条件を満たすようにできます。

この最後の追加が最小値の条件を満たすかどうかというのは次のようにして示せます。

まずグラフの構築の仕方によらず、上にも述べたように最低限必ず(次数が奇数の頂点数 / 2)本の辺は追加しなければいけません。この結果できるグラフの辺の総数は一意に定まります。辺の総数が奇数の場合は条件を満たすようにはできないことを言えばよいです。

グラフのある2頂点(同一の場合も含む)に有向辺を付け加える操作を行うと、片方は入次数が、もう片方は出次数が1増加します。辺の総数が奇数個であるならば、この操作の回数は奇数回なので、入次数の総和と出次数の総和はどちらも必ず奇数になっているはすです。よってこのとき少なくとも1頂点については条件を満たしていないことがわかります。これで最小性が言えました。

以上を実装すると以下のようになります。

実装
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

//gは隣接リスト
//gを破壊する
vector<int> EulerianTrail(const int s, vector<vector<int>> &g, const bool directed) {
        function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) {
                while (!g[u].empty()) {
                        int v = g[u].back();
                        g[u].pop_back();
                        if (!directed) {
                                for (int i = 0; i < g[v].size(); i ++) {
                                        if (g[v][i] == u) {
                                                g[v].erase(g[v].begin() + i);
                                                break;
                                        }
                                }
                        }
                        dfs(v, trail);
                }
                trail.push_back(u);
        };
        vector<int> trail;
        dfs(s, trail);
        reverse(trail.begin(), trail.end());
        return trail;
}

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }

        //次数が奇数の頂点を列挙し、適当につなぐ
        vector<int> odd;
        for (int i = 0; i < n; i ++) if (g[i].size() & 1) odd.push_back(i);
        int cnt = 0;
        for (int i = 0; i < odd.size(); i += 2) {
                int a = odd[i], b = odd[i + 1];
                g[a].push_back(b);
                g[b].push_back(a);
                cnt ++;
        }

        //オイラー閉路を構築する
        auto trail = EulerianTrail(0, g, false);

        //オイラー路を順に辿り、向きを交互につけていく
        vector<pair<int, int>> ans;
        for (int i = 0; i < trail.size() - 1; i ++) {
                int a = trail[i], b = trail[i + 1];
                if (i & 1) ans.emplace_back(a, b);
                else ans.emplace_back(b, a);
        }

        //すべての辺の数が奇数個のときは、頂点0に自己辺を張る
        if ((m + cnt) & 1) ans.emplace_back(0, 0);

        printf("%d\n", (int) ans.size());
        for (int i = 0; i < ans.size(); i ++) {
                printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
        }
        return 0;
}

最後に

ここまで読んでくださって(る人がもしいるなら)ありがとうございました。オイラー路構築は僕のお気に入りのアルゴリズムの一つでもあります。この記事を読んで、オイラー路に感動したり、オイラー路を好きになってくれる人が増えれば、なにより嬉しく思います。

CODE THANKS FESTIVAL 2017 参加記

CODE THANKS FESTIVAL 2017 参加記

CODE THANKS FESTIVAL 2017 - AtCoder

前日

前日はボードゲームの会に参加しました。会う予定の人は全員初対面だったため、もちろん緊張でヒザがガクガク震えていました。

Tikeさん、TsutaJさん、フェリンさん、らてあさん、竹雄さんらと遊びました。みんな優しくてヒザの震えも一瞬で止まりました。

今までTwitterや順位表でしか見たことがなかった人々と直接お会いできるのはとても素敵なことだなあと思いました。

なんだかんだで(?)あっという間にボードゲームの会は終わり、リクルートが用意してくれていたホテルに泊まって当日に備えました。

フランスやイギリスのベンチで寝たこともある僕にとってはあまりに豪華なホテルだったので胸騒ぎがしました。
(参考)予測不能のサバイバル18日目 - えんぴつ画サバイバル

コンテスト

後ろから解きました。

G問題

とりあえずG問題を見ました。最大なんとか集合を求めるんでしょと思いましたが、求め方がよくわかりませんでした。適当に書いて投げるとWAでした。

次数1以下のものは即座に消すような枝刈り全探索で通せるかなあと一瞬思ったのに、なぜかそのアイディアは余裕で棄却していました。

G問題をひたすら考えていると時間がどんどん過ぎた(110分くらい使っていた(は?))ので、H問題を解くことにしました。

H問題

H問題は、画家の才能で殴りました。まあ典型的なので25分ほどかけてACです(H : 135:26)。

G問題

その後もG問題を解こうとしましたが解けませんでした。かなしいですね。

F問題

残り時間10分になったころにF問題を見てみると、5分くらいで多分いけるなあという気持ちになりました。

E問題

残り時間5分になったころにE問題を見てみると、3分で脳内ACしました(ん?)。

G問題

残り時間2分になったころにもう一度G問題に戻って考えますが、もう頭は真っ白です。

こんな感じで終わりました。

解きたい問題が解けないのは悔しいですね。精進します。

ABCD問題

終了直後に見ましたが、ABCDは実家でした。

直後

らくたるさんにG問題の解法を聞きました。ふんわりと解法を教えてくれました。

解説

あまり聞いていませんでした。

表彰式

らくたるさんが5位をとっていてすごいな〜と見ていました。前で感想を述べていたみたいですが、耳が悪いのか僕にはよく聞こえませんでした。

Connection Hunt

ニューヨークとヨーロッパで鍛えた、知らない人に話しかける力で殴って、無事おしゃれなバッグをゲットしました。
(参考)厳し過ぎたサバイバル1日目 - えんぴつ画サバイバル

懇親会

お寿司を食べながらclimpetさんと色々話せて楽しかったです。Hしか解いていない変なやつがいると認知してくれていました。

ボーリング

解散した後、Tikeさん、vimamiさん、TsutaJさん、なんとかさん、なんとかさん、なんとかさんらとボーリングをしました。

まとめ

TsutaJさんはボーリングのプロでした。あとvinamiさんはイケメンでした。

最後に

リクルートの皆さん、関わってくれた競プロerの皆さん、貴重な体験をありがとうございました。

Inverse of factorialsをO(N)で列挙する

Inverse of factorialsをO(N)で列挙する

はじめに

素数 $p$ を法として、 $n$ 以下の階乗の逆元を $O(n)$ で列挙しちゃおうというアレを知っていますか?(僕は知りませんでした。。。)

(コードが読みにくくなる割には)そんなに高速になるわけではないためか、実際に使っている人はほとんど見たことがないので、書いておこうと思います。

まず典型的な計算量 $O(n \log n)$ での列挙は次のようなものでした。ここでは $10^9 + 7$ (素数)を法として、$5000000$ 以下の階乗とその逆元を列挙しています。

const int MOD = 1e9 + 7;

const int N = 5000001;
long long fact[N];
long long invfact[N];

long long Inv(long long a) {
        long long res = 1;
        long long n = MOD - 2;
        while (n > 0) {
                if (n & 1) res = res * a % MOD;
                a = a * a % MOD;
                n >>= 1;
        }
        return res;
}

void init() {
        fact[0] = fact[1] = 1;
        for (int i = 2; i < N; i ++) fact[i] = fact[i - 1] * i % MOD;
        invfact[0] = invfact[1] = 1;
        for (int i = 2; i < N; i ++) invfact[i] = invfact[i - 1] * Inv(i) % MOD;
}

フェルマーの小定理と繰り返し二乗法を使って各数の逆元をそれぞれ $O(log n) $で求めています。いえい。

本題

ところで、上の計算に無駄があるとすれば、それは毎回Inv(i)を呼び出して逆元を計算していることです。そこで、Inv[i]をあらかじめ $O(n)$ で求めておく方法を考えます。

まず、次の式を眺めることにします。これは $p$ を $i$ で割ったときの計算式そのものになっています。つまり、 $ \frac {p}{i}$ が商、 $p\ \%\ i$ がその余りになっています。

$p = i * \frac {p}{i} + p\ \%\ i$

この式を $p$ を法として考えると、

$0 \equiv i * \frac {p}{i} + p\ \%\ i$

移項して両辺に $(\frac{p}{i})^{-1}$ をかけると

$i \equiv -\ (\frac {p}{i})^{-1} * (p\ \%\ i)$

両辺の逆元をとると

$i^{-1} \equiv -\ (\frac {p}{i})(p\ \%\ i) ^ {-1}$

さて、ここで注目したいのは、$p\ \%\ i < i$ であるため、小さいものから順に逆元を計算していけるということです。

はい、これで $O(n)$ で逆元を前計算しておけることがわかったので、全体でも計算量は $O(n)$ になりました。これをそのまま実装すると次のようになります。ただし負数 $-x$ は 正数 $p-x$ として扱っています。

const int MOD = 1e9 + 7;

const int N = 5000001;
long long fact[N];
long long invfact[N];
long long inv[N];

void init() {
        fact[0] = fact[1] = 1;
        for (int i = 2; i < N; i ++) fact[i] = fact[i - 1] * i % MOD;
        inv[1] = 1;
        for (int i = 2; i < N; i ++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
        invfact[0] = invfact[1] = 1;
        for (int i = 2; i < N; i ++) invfact[i] = invfact[i - 1] * inv[i] % MOD;
}

簡単なベンチマークをしたところ、およそ3倍程度高速に計算されている感じでした。

この実装の問題点を挙げるとすれば、なぜこれで逆元が計算されるのかがぱっとわからないことくらいでしょうか。プログラム中の他の部分で逆元を多用する場合にはこのように前計算しておくのもありかもしれません。

CS Academy 058 E. Path Inversions

CS Academy 058 E. Path Inversions

CS Academy

解法

ある長さ $k$ のパスを固定して考えると、このパス上の転倒数の個数とこのパスを逆に進むようなパス上の転倒数の個数の和は、書かれている数に関わらず常に、${}_{k + 1} C _2$ となることがわかる。これは実験してみればわかるのだが、全ての数が相異なることから、ある任意の2数をとったときに、それらを端点とするパスの一方では必ず転倒しているものとして数えられ、もう一方では必ず転倒していないものとして数えられるためである。これを踏まえると、結局頂点数 $k + 1$ 個の中からペアを作るときの個数が転倒数の和になるはずである。

よって、向きを無視した長さ $k$ のパスが木の上で何個とれるかを数えれば、答えがわかる。

ここでは、デマテク(データ構造をマージする一般的なテク)によるすっきりとした解法を記す。

頂点 $0$ を根とする根付き木で考え、各頂点に対してmapをもたせ、cnt[u][d]をノード $u$ を親とする部分木の中で、深さが $d$ である頂点の個数と定義する。

この値を葉の方から決めていき、決まったらその値を親ノードにマージする。あるノード $u$ を親とする部分木 $S$ に部分木 $T$ をマージするときに $T$ のある頂点から $u$ を経由して作れる長さ $k$ のパスを計算し、答えに足していく。こうするとうまくすべてを数え上げることができる。

マージするときは当然サイズの小さい方を大きい方にマージする。 $O(n \log n)$ 。

ちなみにこの問題はアリ本に載っている類題とほとんど同じで、重心分解による分割統治法でやはり $O(n \log n)$ で解ける(ほとんど貼るだけだった)。

実装1
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

const long long MOD = 1e9 + 7;

vector<int> g[100000];
int n, k;
map<int, int> cnt[100000];
long long ans;

void merge(int u, int v, int d) {
        if (cnt[u].size() < cnt[v].size()) swap(cnt[u], cnt[v]);
        for (auto &sub : cnt[v]) {
                int dd = d + (k - (sub.first - d));
                if (cnt[u].find(dd) != cnt[u].end()) {
                        ans += (long long) cnt[u][dd] * sub.second;
                        ans %= MOD;
                }
        }
        for (auto &sub : cnt[v]) cnt[u][sub.first] += sub.second;
        cnt[v].clear();
}

void dfs(int u, int prev, int d) {
        cnt[u][d] ++;
        for (auto v : g[u]) if (v != prev) {
                dfs(v, u, d + 1);
                merge(u, v, d);
        }
}

int main() {
        scanf(&quot;%d%d&quot;, &n, &k);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf(&quot;%d%d&quot;, &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        ans = 0;
        dfs(0, -1, 0);
        printf(&quot;%lld\n&quot;, ((long long) k * (k + 1) / 2) % MOD * ans % MOD);
        return 0;
}
実装2
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

const int MOD = 1e9 + 7;

static const int INF = 0x3f3f3f3f;
struct edge { int to, cost; };
const int N = 100000;
int k;
vector<edge> g[N];
bool divided[N];
int subtree_size[N];
long long ans;

int ComputeSubtreeSize(int u, int prev) {
        int cnt = 1;
        for (int i = 0; i < g[u].size(); i ++) {
                int v = g[u][i].to;
                if (v == prev || divided[v]) continue;
                cnt += ComputeSubtreeSize(v, u);
        }
        subtree_size[u] = cnt;
        return cnt;
}
pair<int, int> SearchCentroid(int u, int prev, int all_size) {
        pair<int, int> res = make_pair(INF, -1);
        int sum = 1, ma = 0;
        for (int i = 0; i < g[u].size(); i ++) {
                int v = g[u][i].to;
                if (v == prev || divided[v]) continue;
                res = min(res, SearchCentroid(v, u, all_size));
                ma = max(ma, subtree_size[v]);
                sum += subtree_size[v];
        }
        ma = max(ma, all_size - sum);
        res = min(res, make_pair(ma, u));
        return res;
}
void EnumeratePaths(int u, int prev, int dist, vector<int> &ds) {
        ds.push_back(dist);
        for (int i = 0; i < g[u].size(); i ++) {
                int v = g[u][i].to;
                if (v == prev || divided[v]) continue;
                EnumeratePaths(v, u, dist + g[u][i].cost, ds);
        }
}
int CountPairs(vector<int> &ds) {
        int res1 = 0, res2 = 0;
        sort(ds.begin(), ds.end());
        int j = ds.size();
        for (int i = 0; i < ds.size(); i ++) {
                while (j > 0 && ds[i] + ds[j - 1] > k) j --;
                res1 += j - (j > i);
        }                 
        res1 /= 2;
        j = ds.size();
        for (int i = 0; i < ds.size(); i ++) {
                while (j > 0 && ds[i] + ds[j - 1] >= k) j --;
                res2 += j - (j > i); 
        }                 
        res2 /= 2;
        return res1 - res2;
}
void SolveSubproblem(int u) {
        ComputeSubtreeSize(u, -1);
        int centroid = SearchCentroid(u, -1, subtree_size[u]).second;
        divided[centroid] = true;
        for (int i = 0; i < g[centroid].size(); i ++) {
                int v = g[centroid][i].to;
                if (divided[v]) continue;
                SolveSubproblem(v);
        }
        vector<int> ds;
        ds.push_back(0); 
        for (int i = 0; i < g[centroid].size(); i ++) {
                int v = g[centroid][i].to;
                if (divided[v]) continue;
                vector<int> ds_tmp;
                EnumeratePaths(v, centroid, g[centroid][i].cost, ds_tmp);
                ans -= CountPairs(ds_tmp);
                ds.insert(ds.end(), ds_tmp.begin(), ds_tmp.end());
        }
        ans += CountPairs(ds);
        divided[centroid] = false;
}
void CentroidDecomposition() {
        ans = 0;
        SolveSubproblem(0);
}

int main() {
        int n;
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back({b, 1});
                g[b].push_back({a, 1});
        }
        CentroidDecomposition();
        printf("%lld\n", ((long long) k * (k + 1) / 2) % MOD * ans % MOD);
        return 0;
}

DDCC 2017 D. なめらかな木

DDCC 2017 D. なめらかな木

D: なめらかな木 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 | AtCoder

解法

bitDPをする

実装
#include "bits/stdc++.h"
using namespace std;

const int MOD = 1000000007;

int n;
vector<int> g[55];
map<tuple<long long, int, int>, long long> dp;

long long dfs(long long s, int prev, int pprev) {
        if (__builtin_popcountll(s) == n) return 1;
        for (int x = 0; x < n; x ++) {
                for (auto y : g[x]) {
                        if (x == prev || x == pprev) continue;
                        if (y == prev || y == pprev) continue;
                        bool used1 = (s & (1LL << x)) != 0;
                        bool used2 = (s & (1LL << y)) != 0;
                        if (used1 != used2) return 0;
                }
        }
        auto key = tuple<long long, int, int> (s, prev, pprev);
        if (dp.count(key)) return dp[key];
        long long sum = 0;
        for (int x = 0; x < n; x ++) {
                if (s & (1LL << x)) continue;
                sum += dfs(s | (1LL << x), x, prev);
        }
        return dp[key] = sum % MOD;
}

int main() {
        scanf("%d", &n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        for (int i = 0; i < n; i ++) if (g[i].size() > 4) return !puts("0");
        printf("%lld\n", dfs(0, -1, -1));
        return 0;
}

Atcoder Grand Contest 009 E. Eternal Average

Atcoder Grand Contest 009 E. Eternal Average

E: Eternal Average - AtCoder Grand Contest 009 | AtCoder

感想

実装軽いのに考察が重すぎる...。

解法

最終的に残る数を$\ x\ $とする。$\ x\ $は連分数で書かれるような数になるが、このまま考えるとわかりにくいので、これを完全$\ K\ $分木で考える。各葉には$\ 1, 0\ $が書かれていて、その親ノードにはその平均が書かれている。

この根ノードに書かれた数が$\ x\ $になるが、これはそれぞれの葉の深さを$\ depth_i\ $とし、書かれた数を$\ p_i = \{ 0, 1 \}\ $とすると、$\ x = \sum K^{-depth_i} * p_i\ $となる。

さて、$\ 0\ $と書かれたノードの深さの列を$\ a_1, a_2, ..., a_n\ $、$\ 1\ $と書かれたノードの深さの列を$\ b_1, b_2, ..., b_m\ $とする。このとき次の条件を得る。

$\ K^{-a_1} + K^{-a_2} + ... + K^{-a_n} + K^{-b_1} + K^{-b_2} + ... + K^{b_m} = 1\ $

これは気づきにくいが、木を書いてみればわかる。逆にこの条件が成り立つとき、その$\ x\ $が残るように木が構成できることも言える。さらに上に書いた$\ x\ $を用いて書きなおすと、

$\ K^{-b_1} + K^{-b_2} + ... + K^{-b_m} = x\ $
$\ K^{-a_1} + K^{-a_2} + ... + K^{-a_n} = 1 - x\ $

となる。

次に、$\ K\ $進法によって$\ x = 0.d_1d_2...d_l\ $、$\ 1 - x = 0.e_1e_2...e_l\ $と書く。ただし$\ d_l \neq 0, e_l \neq 0\ $とする。これについて満たすべき条件というのは、以下のようになる。

$\ \sum d_i \equiv m\ (mod\ K - 1)\ ...(A)\ $
$\ \sum e_i \equiv n\ (mod\ K - 1)\ ...(B)\ $

なぜかというと、$\ b_i\ $の各項が増えるごとに、ある桁に$\ 1\ $が足されるはずなので、$\ b_i\ $の項数が$\ m\ $であるならば$\ m\ $回$\ 1\ $が加えられているはずだが、繰り上がりを考慮すると、$\ K - 1 + 1 \equiv 1\ $であるため、$\ mod\ K - 1\ $で考えると$\ \sum d_i \equiv m\ $となっているはずだからである。同様に2番目の式も出てくる。

さらにこれらの和は$\ 1\ $になることから、次が言える。

$\ d_i + e_i = K - 1\ (i = l)\ $
$\ d_i + e_i = K\ (i \neq l)\ $

これを用いると、上の$\ (B)\ $を変形することができて、

$\ \sum_{i = 1}^{l - 1} (K - d_i - 1) + (K - d_l) \equiv n\ (mod\ K - 1)\ $

$\ lK - \sum_{i = 1}^{l} d_i - (l - 1) \equiv n\ (mod\ K - 1)\ $

よって以下を得る。

$\ l = \cfrac{n + \sum_{i = 1}^{l} d_i - 1}{k - 1}\ ...(C)\ $

さて、次の$\ dp\ $を考える。

$\ dp[i][j] := \ $ ($\ i\ $番目までの$\ d\ $を定めて$\ x\ $を構成したときに、その各桁の総和が$\ j\ $であるような場合の数)

この$\ dp\ $を計算し、上の条件$\ (A), (C)\ $を満たすようなものについての総和をとれば答えになる。

実装
#include <cstdio>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

signed main() {
        int n, m, k;
        scanf(&quot;%d%d%d&quot;, &n, &m, &k);
        int c = (n + m - 1) / (k - 1);
        vector<vector<long long>> dp(c + 1, vector<long long> (m + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= c; i ++) {
                for (int j = 0; j <= m; j ++) {
                        for (int l = 0; l < k && j + l <= m; l ++) {
                                (dp[i][j + l] += dp[i - 1][j]) %= MOD;
                        }
                }
        }
        long long ans = 0;
        while (m > 0) {
                int nc = (n + m - 1) / (k - 1);
                (ans += dp[nc][m]) %= MOD;
                m -= k - 1;
        }
        printf(&quot;%lld\n&quot;, ans);
        return 0;
}