自分が書く今後の競プロ問題解説記事について

これまでは、難しいなと思った問題や AOJ で解説がない問題の記事をはてなに直接書いてきた。
しかし最近は解いたときのコードを git で管理するようになったので、今後は github の解答コードへのリンクを貼るようにしようと思う。
解説や考察メモはコードの上にコメントとして書くことにする。
メモがない場合は、僕が自明だと思ったか、あるいは書くのを忘れているだけなので、そこらへんは許してほしい。

例えばこんな感じにする。
https://github.com/Suikaba/procon-solved/blob/master/Codeforces/Round200-249/Round210/Div1-C.cpp

解説に画像をくっつけたいなと思ったときだけはてなに書くかもしれない。
Markdown でいい気もするけど。

Lindström–Gessel–Viennot lemma

概要

格子点上で、n 組の始点と終点 $(a_1, a_2, \ldots, a_n), (b_1, b_2, \ldots, b_n)$ が定まっているとして、それらが交差しないようなパスの選び方をカウントできる定理である。($a_i$ をどの $b_j$ と対応付けるか、まで含めて。)
後にこの定理を用いて解ける問題を挙げる。

主張

$G$ を局所的に有限なDAGとする。
始点集合を $A = \{a_1, \ldots, a_n\}$ とし、終点集合を $B = \{b_1, \ldots, b_n\}$ とする。
辺には重みがついており、パス $P$ に対して $w(P)$ で $P$ 上の辺の重みの積と定義する。
また、$e(a, b) := \sum_{P : a \rightarrow b}w(P)$ と定義する。
もしすべての辺の重みが 1 であるならば、$e(a, b)$ は $a$ から $b$ へ行く方法の総数に対応する。

ここで、
$M = \left(
\begin{array}{cccc}
e(a_1, b_1) & e(a_1, b_2) & \cdots & e(a_1, b_n) \\
e(a_2, b_1) & e(a_2, b_2) & \cdots & e(a_2, b_n) \\
\vdots & \vdots & & \vdots \\
e(a_n, b_1) & e(a_n, b_2) & \cdots & e(a_n, b_n)
\end{array}
\right)$
とおく。
$n$ 組の $A$ から $B$ へのパス $P = (P_1, P_2, \ldots, P_n)$ が交差しないとは、以下の性質を満たすことである。

  • $\{1, \ldots, n\}$ のある順列 $\pi$ があって、パス $P_i$ は $a_i$ から $b_{\pi(i)}$ へのパスと表される
  • $i \neq j$ ならば、$P_i$ と $P_j$ は端点も含め共通な頂点を持たない

すると、$det(M)$ は $A$ から $B$ への $n$ 組非交差パス $P = (P_1, \ldots, P_n)$ についての符号付き総和となる。
つまり、 $\det (M) = \sum_{(P_1, \ldots, P_n) : A \rightarrow B} sgn(\pi(P)) \prod_{i=1}^{n}w(P_i)$ である。

とくに、2つの性質を満たす順列 $\pi$ が identity な順列、つまりすべての $i$ について $\pi(i) = i$ となる順列しか無く、かつ辺の重みがすべて 1 の場合、$\det(M)$ は $A$ から $B$ への $n$ 組非交差パスのとり方の総数と等しくなる。

証明

そのうち(ごめんなさい)

問題概要

n * m のグリッドが与えられる。いくつかのマスは障害物があり通れない。
2人が座標 (0, 0) からスタートして (n - 1, m - 1) に到達する移動方法で、同じマスを通らないようなもの(ただし始点と終点はよい)は何通りあるか。
許される移動方法は、今の座標を (x, y) として (x + 1, y) か (x, y + 1) に移動することだけである。

・2 <= n, m <= 3000

解法

さっきの定理で解ける。
今回であれば、始点として $A = \{(0, 1), (1, 0)\}$ を、終点として $B = \{(n - 2, m - 1), (n - 1, m - 2)\}$ を与えて適用できる。
適用できる理由は、順列 $\pi$ としては identity なものしかありえないからである。
具体的には、$(0, 1)$ と $(n - 1, m - 2)$ を対応付ければ、かならずパスが交差してしまうということである。
よって、求める答えは、行列式
$\left|
\begin{array}{cc}
f(a_1, b_1) & f(a_1, b_2) \\
f(a_2, b_1) & f(a_2, b_2)
\end{array}
\right|$
である。ただし、$f(a_i, b_i)$ は $a_i$ から $b_i$ への移動方法の総数を表し、これは簡単な dp で O(nm) で解ける。

ソースコード

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

using ll = long long;

constexpr int mod = 1e9 + 7;

int add(int a, int b) {
    a += b;
    if(a >= mod) a -= mod;
    return a;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<string> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    vector<vector<int>> dp(n, vector<int>(m));
    auto calc = [&] (int sy, int sx, int gy, int gx) {
        if(v[sy][sx] == '#') return 0;
        for(int i = 0; i < n; ++i) {
            fill(begin(dp[i]), end(dp[i]), 0);
        }
        dp[sy][sx] = 1;
        for(int i = sy; i < n; ++i) {
            for(int j = sx; j < m; ++j) {
                if(v[i][j] == '#' || (i == sy && j == sx)) continue;
                if(i != 0) dp[i][j] = add(dp[i][j], dp[i - 1][j]);
                if(j != 0) dp[i][j] = add(dp[i][j], dp[i][j - 1]);
            }
        }
        return dp[gy][gx];
    };

    int ans = (ll)calc(1, 0, n - 1, m - 2) * calc(0, 1, n - 2 , m - 1) % mod;
    (ans += mod - (ll)calc(1, 0, n - 2, m - 1) * calc(0, 1, n - 1, m - 2) % mod) %= mod;
    cout << ans << endl;
}

参考文献

Lindström–Gessel–Viennot lemma - Wikipedia
主張はほとんどここからのパクリです。

ACM-ICPC 2018 Asia Yokohama Regional 参加記

はじめに

2018年12月8, 9日に横浜で行われた ACM-ICPC 2018 Asia Yokohama Regional の参加記です。
ラクティス~懇親会あたりまでの話を大雑把にまとめようと思います。

チームについて

自分はチーム Zerokan_Sunshine として kazuma, nakano と一緒に出ました。
基本的に担当は

  • suibaka (自分) : 実装担当、自明とか典型とか幾何とか。あと問題読解。
  • kazuma : 実装担当2。データ構造が得意(ICPCではあまり出ないので悲しい)
  • nakano : 考察・問題読解担当、コードは書かない(早く US 配列に慣れろ)

となっています。

ラクティス

ラクティスは基本的に1問ACしてあとはジャッジで遊ぶだけなんですが、今年は問題が普通に過去問だったので真面目にやりました。

A 問題

kazuma が Link-cut tree で解けるとか言い出したので後回しにした(流石にネタ)
n 要素の数列が与えられるから合計値出力するだけ。

B 問題

覚えてないが全探索、kazuma に書かせた

C 問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320
知っているので油断していたらコーナーケースを忘れて 1WA 。
知っていると思考が無になる。

D 問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1605&lang=jp
これも解いたことがあるが今思えば条件判定部分を間違えていた。
間に合わなかった。

ラクティス後

雑にチーム紹介をして終わり。今年はご飯の提供がなかった。
まあ近くに中華街があるのでそっちで食べられた。
ただ寝不足が続いていてコンディションが悪い人が多く、ちょっと食べてさっさと寝た…んだったら良かったんだけどなー。

ABC

なんかABCがあった。後述の Snackdown まで仮眠をとるつもりが何故か眠れず、出ることにした。
さっさと終わらせて寝るつもりだったけど、冷えたので布団で暴れたり呪詛の言葉を吐いたりした。

Snackdown 2019

運の悪いことに今年は Snackdown の最終予選が 23:00 ~ 04:00 とかいうヤバヤバの時間で、しかも完全に予定がかぶっていた。
普通なら出ないって?僕らは頭が悪いので出ました。

詳細は脱線なので書きませんが、難しすぎて絶望した。
10問あって3完、ラスト1問は実装間に合わないとかだった。
多分Tシャツはゲットなのでセーフということにした。

就寝(04:30)

本番

8:30 ぐらいに起きて飯をくい、さっさと会場へ。
以下内容。

A 問題

問題文の解釈に少し手間取ったけどまあやるだけなので書いて終わり (0:12 AC)

C 問題

nakano が読んでいたので教えてもらって、Bのあとに書く予定だった。
B が自明 O(N^2logN) 解は多分 TLE するからめんどい、とのことだったので先に C を書くことにした (0:30 AC)

B 問題

kazuma が O(N^2) で通す。(0:41 AC)
疑問なんですが、5sec で N <= 5000 だったら O(N^2logN) は通ると思いますか?
僕はかなり微妙だと思います(強いて今回のセットで不満があるならここぐらいかな…)

虚無

虚無です。いつもの時間です。虚無虚無プリン。

G 問題

nakano が概要を教えてくれた、明らかに BIT だし kazuma に投げた。
まあいけるね、となったけど方針が想定と違っていて、駄目なケースがあった。
幸いサンプルに存在したので気づけてセーフ。nakano が想定解に修正して kazuma が通す。(1:40 AC)

E 問題

オイラー路が存在するように与えられたグラフに辺を生やせ、という構築。
第一感は解けそう、という感じ。
自分は D, K をやっていたので kazuma がやることに。
実装頑張って投げたが WA、しかし落ちるケースをすぐ発見(やりますねえ!)して AC (3:18 AC)。
G の次に解いたのが E なの完全に異常、僕のせいですごめんなさい。

K 問題

辞書順最大を誤読しており 1WA。Standings みればわかることなんだよね。
前の値から決めていくいつものやつじゃ~んとなる。
けど、普通にやったら O(N^3) なのでどうしようなあとなっていて、
nakano とあーでもないこーでもない言ってたら生えた。
O(N^2logN) の少し重めの実装になって、とりあえずTLEかどうか投げてから考えようと思ってたら通った (3:59 AC)

D 問題

これ最初の方からずっと考えていて、今それぞれの文字でどのインデックスにいるかの dp やるだけなのは割とすぐ見えていたんですが…
これのややこしいバージョンを解いたことがあって、経路復元パートで直前に使った数字しか記憶しないことに起因して、直前の状態が一意に定まらない、みたいな理解をしてしまい、実装がめんどくさいなーと思って後回しにしてしまった。K問題で虚無っていたというのもあるけど。
この場合、現状態として解となりうる状態の頂点集合を持ちながら、復元していく(最終的には一意的になる)実装になる。
でまあなんとか1発で通ったわけですが (4:41 AC)、これで通ってなかったら戦犯だな。
普通に BFS で0を優先的に使っていく遷移をすれば、直前の状態は一意的に定まっているので本当にやるだけでした。なーにやってんだか。

ここからは本番で解いてない問題

F 問題

nakano に解ける解ける言われて kazuma と2人で全力拒否していた問題。
どう考えてもこのセットで飛びついていいものではない。他にやることあるからね。

H 問題

解説聞いてかなりおもろいな~と思った。
グラフの形が特徴的だから、座標の辞書順に埋めていけば、すでに色が塗られている頂点は高々4個しか無い、というのがうまく効いていてすごい。
色の塗替えのあの発想は彩色問題の証明で見たテクな気がする。

I 問題

未だに完全理解していない。本番で4チームも通してるのすごくない?

J 問題

kazuma が O(N(logN)^3) ならわかったとのこと。
15分でかけねえし絶対バグるし想定じゃないのは明らかだしで面白かった。
LCA でいい感じにするやつは実は過去に(違う地区の問題?)出たことがあるらしい。要復習。

懇親会

ご飯おいしかった。ごちそうさまです。
今年はブースもちゃんと回ることにした。
毎年1社はでかいカバンを配っているような気がするので、最初にそこにいくと後が楽でいいと思う。
Indeed ブースでコネクションハントをし、頑張って集めて T シャツゲット。
別のブースで真剣にコーヒー淹れていた人がいたんですが、なんか話しかけられない空気でちょっと怖かった…。

感想

決意表明として、来年も同じチームで来ることを誓おうと思います。

今年は同大学の earlybird が WF に行けそうなので、一緒に応援しましょう!!
あわよくばメダルを取って帰ってきてほしいですね~。

AOJ 2884 Tanka Number

解法

二分探索 + 桁DP ……ではなく貪欲に解く。
基本的に上の桁から順番に数字を確定させていって、
n 番目を超えないギリギリを選択する、というよくあるやり方。
当然だが各桁は小さい数字から順番に選択していくようにする。

まず、ちょうど d 桁の短歌数は 81 * (2^(d-1) - 1) 個あるので、答えが何桁かは簡単に決定できる。
(2つの数字の決め方で 9 * 9 通り、2桁目以降の数字の割り当て方で 2^(d-1) 通りで、すべてが1桁目と同じ数になる 1通りを省くと先の式になる)
あとは数字を決めるだけ。

上から1桁目は簡単で、1桁目を決めたら、そのような短歌数は 9 * (2^(d-1) - 1) 個あるわけだから、これを超えないギリギリが1桁目で確定する。

2桁目以降は、小さい数字から(同じように)順番に見ていくのだが、

  • これまでにすでに2つの異なる数字を選んでいるか
  • まだ1つの数字しか選んでいないなら、今の桁に割り当てようとしている数字が1桁目と同じかどうか

に注意して短歌数の個数を数える必要がある。

計算量は O(logN)

ソースコード

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

using ll = long long;

int main() {
    ll n;
    while(cin >> n, n) {
        ll keta = 2, cnt = 0;
        while(cnt + 9 * 9 * ((1LL << (keta - 1)) - 1) < n) {
            cnt += 9 * 9 * ((1LL << (keta - 1)) - 1);
            keta += 1;
        }
        cnt = n - cnt;

        string ans;
        function<void(int, int, int)> solve = [&] (int d, int a, int b) {
            if(d == keta) return;
            if(a == -1) {
                for(a = 1; a <= 9; ++a) {
                    if(cnt > 9 * ((1LL << (keta - 1)) - 1)) {
                        cnt -= 9 * ((1LL << (keta - 1)) - 1);
                        continue;
                    }
                    break;
                }
                ans += '0' + a;
                solve(d + 1, a, b);
            } else if(b == -1) {
                for(b = 0; b <= 9; ++b) {
                    if(a != b) {
                        if(cnt > (1LL << (keta - d - 1))) {
                            cnt -= 1LL << (keta - d - 1);
                            continue;
                        }
                        break;
                    } else {
                        if(cnt > 9 * ((1LL << (keta - d - 1)) - 1)) {
                            cnt -= 9 * ((1LL << (keta - d - 1)) - 1);
                            continue;
                        }
                        break;
                    }
                }
                ans += '0' + b;
                if(a == b) solve(d + 1, a, -1);
                else       solve(d + 1, a, b);
            } else {
                const int ma = max(a, b), mi = min(a, b);
                if(cnt > (1LL << (keta - d - 1))) {
                    cnt -= 1LL << (keta - d - 1);
                    ans += '0' + ma;
                } else {
                    ans += '0' + mi;
                }
                solve(d + 1, a, b);
            }
        };
        solve(0, -1, -1);

        cout << ans << endl;
    }
}

感想

模擬国内本番では二分探索 + 桁DP (数が大きいので文字列同士の足し算をする) で解いてしまったので、まともなほうで解き直した。

AOJ 2787 Pipe Fitter and the Fierce Dogs

解法

一番上の行のすべての家は special pipe 確定だから、(W + 1) / 2 > K なら不可能であり、それ以外は可能である。
それ以外については、一旦 special pipe を使わないとして考えよう。
すると、以下の dp で解くことができる。
dp[i][j][k] := i 行目 j 列目の家まで考えた時に、使った家の状態が k である場合の最小コスト
i, j は家がないところを圧縮しておく(MLEするため)。
家の状態 k についてだが、これは (左上が使われている) or (真上が使われている) の2通りしかないので、丁寧に場合分けして十分。

こうして求まった答えを X とする。
もし犬を完全に回避できれば、((H - 1) / 2) * ((W + 1) / 2) のコストで common pipe を配置できる。
もし X がこれを超えていれば、その分だけ犬のマスに pipe を配置したことがわかる。
あとは、残っている special pipe を犬のマスに優先的に割りあて、それでも special pipe が残っているなら、その数だけ答えから引いてやれば良い。
サンプルにもあるが、引きすぎて負の値にならないようにすること。

計算量は O(wh) となる。

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
const int inf = 1e9;
 
int main() {
    int w, h, k; cin >> w >> h >> k;
    int n; cin >> n;
    vector<vector<int>> cost(w, vector<int>(h / 2, 1));
    for(int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;
        x--, y--;
        if(y % 2 == 0) continue;
        cost[x][y / 2] = 2;
    }
 
    k -= (w + 1) / 2;
    if(k < 0) {
        cout << -1 << endl;
        return 0;
    }
 
    const int hz = (h - 1) / 2, wz = (w + 1) / 2;
    vector<vector<int>> dp(wz + 1, vector<int>(2, inf));
    dp[0][0] = 0;
    for(int y = 0; y < hz; ++y) {
        for(int x = 0; x < wz; ++x) {
            if(dp[x][0] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][0] + cost[x * 2][y]);
                if(x != wz - 1) {
                    dp[x + 1][1] = min(dp[x + 1][1], dp[x][0] + cost[x * 2 + 1][y]);
                }
            }
            if(dp[x][1] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][1] + cost[x * 2 - 1][y]);
            }
        }
        const int ns = dp[wz][0];
        for(int x = 0; x <= wz; ++x) {
            for(int S = 0; S < 2; ++S) {
                dp[x][S] = inf;
            }
        }
        dp[0][0] = ns;
    }
 
    int ans = dp[0][0];
    const int tcnt = min(k, ans - hz * wz);
    const int ocnt = max(0, k - tcnt);
    ans = max(0, ans - tcnt * 2 - ocnt);
    cout << ans << endl;
}

感想

cost の2次元配列が贅沢すぎるから、map とか使ってもいいかもしれない。
ほかはまあこんなもんでしょう。

AOJ 2432 Sports Days 2.0

解法

行列累乗で解く。
A[u][v] := u -> v のウォークで最大となるもの
と定義すると、A を n 回かけた行列 An は、長さ n のウォークについて考えたものになる。これは超典型。
行列積の計算だが、A[i][j] = max(A[i][j], B[i][k] + C[k][j]) とする。
max は結合則を満たすので、上で定義した行列積について繰り返し二乗法を用いることができる。

よって、入力で行列を作ったあと、ウォークの長さ n についての二分探索をする。これで長さは求まる。
このとき、パスを陽に持つと当然TLEするので、パスの復元は後にやる必要がある。
具体的に出力する必要があるパスの長さは最大100だから、これは愚直に dp で求め直してやれば良い。

計算量は O(V^3) だが、まあまあ重いため、定数倍に注意。
以下の実装は定数倍改善をあまり考慮せずに書いているが、TL 3sec のところ 2.6sec だった。

ソースコード

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

using matrix = vector<vector<int>>;

matrix mat_op(matrix a, matrix b) {
    const int n = a.size();
    matrix res(n, vector<int>(n, -1));
    for(int k = 0; k < n; ++k) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(a[i][k] == -1 || b[k][j] == -1) continue;
                res[i][j] = max(res[i][j], a[i][k] + b[k][j]);
            }
        }
    }
    return res;
}

matrix matpow(matrix a, int n) {
    const int V = a.size();
    matrix res(V, vector<int>(V, -1));
    for(int i = 0; i < V; ++i) {
        res[i][i] = 0;
    }
    while(n > 0) {
        if(n & 1) res = mat_op(move(res), a);
        a = mat_op(a, a);
        n >>= 1;
    }
    return res;
}


int main() {
    int V, E, K; cin >> V >> E >> K;
    matrix a(V, vector<int>(V, -1));
    for(int i = 0; i < V; ++i) {
        a[i][i] = 0;
    }
    for(int i = 0; i < E; ++i) {
        int u, v, c; cin >> u >> v >> c;
        a[u][v] = max(a[u][v], c);
    }

    auto check = [&] (int cnt) {
        const auto res = matpow(a, cnt);
        for(int i = 0; i < V; ++i) {
            for(int j = 0; j < V; ++j) {
                if(res[i][j] >= K) return true;
            }
        }
        return false;
    };
    int lb = 0, ub = K + 1;
    while(ub - lb > 1) {
        const auto mid = (lb + ub) >> 1;
        (check(mid) ? ub : lb) = mid;
    }

    if(ub == K + 1) {
        cout << -1 << endl;
        return 0;
    }

    cout << ub << endl;
    if(ub <= 100) {
        vector<int> dp(V);
        vector<vector<int>> path(V);
        for(int i = 0; i < V; ++i) {
            path[i] = {i};
        }
        for(int i = 0; i < ub; ++i) {
            vector<int> ndp(V, -1), nfrom(V, -1);
            vector<vector<int>> npath(V);
            for(int from = 0; from < V; ++from) {
                if(dp[from] == -1) continue;
                for(int to = 0; to < V; ++to) {
                    if(from == to || a[from][to] == -1) continue;
                    if(ndp[to] < dp[from] + a[from][to]) {
                        ndp[to] = dp[from] + a[from][to];
                        nfrom[to] = from;
                    }
                }
            }
            for(int j = 0; j < V; ++j) {
                if(nfrom[j] == -1) continue;
                npath[j] = path[nfrom[j]];
                npath[j].push_back(j);
            }
            dp = move(ndp);
            path = move(npath);
        }
        vector<int> ans_path;
        int maxi = -1;
        for(int i = 0; i < V; ++i) {
            if(dp[i] > maxi) {
                maxi = dp[i];
                ans_path = path[i];
            }
        }
        for(int i = 0; i <= ub; ++i) {
            cout << ans_path[i] << " \n"[i == ub];
        }
    }
}

感想

典型良問と言えるのかな。
AOJ-ICPC 700点 にしては簡単だった。