2017-07-15

ACM-ICPC 2017 国内予選参加記

競プロ ICPC

ICPC国内予選にチーム KazumaDragon として参加しました．
チームメンバーは suibaka(僕), kazuma, nakano の3人．
結果は全体で 18 位，大学内で 2位でした．
目標は20位以内に入ることだったので，達成できて良かったです．

以下本番終了までの流れを書き残しておきます．

本番当日　開始直前

実験室（会場）が開かれるまで部屋の前でのんびりしていた．
やるだけ問題を解いて軽くエンジンをかけたあと，外に散歩して頭をリフレッシュ．この時，空から何故かアリが降ってきたので，縁起がいいなぁ（？）と思いつつ部屋に戻る．
部屋に入った後は，チームメンバーでチーム戦略を再確認して待機．

本番

役割分担

役割分担としては，僕が実装担当，kazumaはデバッグと考察担当，nakanoは考察（適宜デバッグもする）担当という感じでやりました．
デバッグの比重はかなり重めにしました．

解いた流れ

僕がAを読む．書く．その間にBをkazumaが読んでくれた．nakanoは C 以降に目を通してもらって，考察と全体の配分をイメージしてもらっていた．

Aが通った (5:27) ので，僕も B を読む．これは誤読対策．それでkazumaと解法や制約を突き合わせて，はいということになった．
ちょっと手間どってしまったがなんとかAC (17:42)．

次にCをkazumaと 2人で読む．制約を読むとサイズが小さすぎてびっくらこいた．サンプルでREを起こして焦ったがkazumaが添字の書き間違いに気がついてくれた．AC(29:27)．

次にDを読む．先に読んでいたnakanoに考察を聞いてみると n と m のサイズで場合分けして半分全列挙 or bitDPでよいらしい．考察するの早くない？一応ちょっと考えると，合っていそうなので書く．Dはバグが怖い（模擬国内での教訓）ので2人に見てもらっていた．一発AC (1:01:03)．

（あとになって考えるとなんで30分もかかってるんだろう？あ，僕の実装が遅かっただけか．）

ここら辺で順位を確認すると悪くなかったので，これ以降は安全に行くということになった．

次に E を見る．式短いし，まあ適当に全部試せるんでは？と思いつつnakanoに聞いてみると，dpっぽくやっていくと良いらしい．なるほど，とは思ったもののバグりそうで怖かったので後回し．

ここでどうやら F が簡単そうとnakanoとkazumaが気づく．僕は問題を見た瞬間に拒絶反応が出たので逃亡．2人は得意そうだったのでFを任せて，それ以外で簡単そうな G を読む．H は実装がめんどくさそうなのでパス．

Gを読むと明らかにぐるっと大回りするしかなく，右手法でやれるやろというのはすぐに分かった．nakanoとkazumaに聞いてみると，意見が一致していたので，Fが終わり次第やるかという感じに．

すると F がバグっていてつらそうだったので，デバッグをnakanoにまかせてとりあえず G をkazumaと2人で取り組むことに．
適当にDFSを書いて投げるとTLEしてしまい（実装力のNASA），どうしようかなぁと考えていると，対角線でそれぞれ流量2のフローを流せばいけるんではという神 (nakano) のお告げが．
ちょっと正当性を考えてみたが，正しそうだったため，フローと入力とる部分だけ実装して，辺を張る部分は nakano に書いてもらった．するとサンプルが通る．天才か？と思いつつ投げると AC (2:40:24)．

ここで順位表を見ると，20位の目標は達成できそうで大喜び．あまり時間もないので，だいたい出来てる F のデバッグをすることに．
とはいえ，僕は拒絶反応が出てるわ，コードがビット演算で大変なことになってるわで，僕の手には負えなかったので後ろから念を送ったり地蔵になったりした．

結局バグが取れず終了．

コンテスト終了後

順位表を見ると京大からDragonチームが3チーム予選通過していて，一安心しました．他のチームの話を聞いてみると先輩たちがかなり不調でつらそうでした．

実験室を出た後はモツ鍋を食べた．美味しかった．

感想

チームとしては機能したほうだと思う．練習の成果があってよかった．
来年は 6 ～ 7 完ぐらいしたいなぁ．
結構チームメイトに頼ってたので，次は自分も貢献したい．
あとデバッグは大切．慢心はダメ．誤読対策もしつこいぐらいがちょうど良かった．そんなにロスにならないし．

2017-07-09

AOJ 1358 Sibling Rivalry

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1358

解法

終点から更新していくベルマンフォードのように解いた．
まず，各頂点から a, b, c で行ける頂点を予め求めておく．
d[v] := その頂点から終点に必ずたどり着けるなら，その時の最小値
とする．d[n-1] = 0 とする．
すると，d[v] は v から a, b, c それぞれで行ける頂点集合を Va, Vb, Vc とおけば，d[v] = max( min( d[Va] ), min( d[Vb] ), min( d[Vc] ) ) となることがわかる．
あとは，ベルマンフォードの要領で，更新が終わるまで続けるとよい．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 1e9;
 
int main() {
    int n, m;
    vector<int> a(3);
    cin >> n >> m >> a[0] >> a[1] >> a[2];
    vector<vector<int>> g(n);
    for(int i=0; i<m; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
    }
    vector<vector<vector<int>>> to(n, vector<vector<int>>(3));
    for(int v = 0; v < n; ++v) {
        vector<vector<bool>> visited(101, vector<bool>(n));
        visited[0][v] = true;
        for(int i = 0; i < 100; ++i) {
            for(int j = 0; j < n; ++j) {
                if(visited[i][j]) {
                    for(auto t : g[j]) {
                        visited[i+1][t] = true;
                    }
                }
            }
        }
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < n; ++j) {
                if(visited[a[i]][j]) {
                    to[v][i].push_back(j);
                }
            }
        }
    }
    vector<int> d(n, INF);
    d[n-1] = 0;
    while(true) {
        bool update = false;
        for(int v = 0; v < n; ++v) {
            vector<int> mi(3, INF);
            for(int j = 0; j < 3; ++j) {
                for(auto t : to[v][j]) {
                    mi[j] = min(mi[j], d[t]);
                }
            }
            int ma = *max_element(mi.begin(), mi.end()) + 1;
            if(ma < d[v]) {
                update = true;
                d[v] = ma;
            }
        }
        if(!update) {
            break;
        }
    }
 
    if(d[0] == INF) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << d[0] << endl;
    }
}

2017-07-08

AOJ 1613 Deciphering Characters

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613&lang=jp

解法

包含関係は，一番背景連結成分を根とした木構造になっていることがわかる．
よって，背景連結成分を根として，各再帰段階でBFSをするDFSを行えば，その木構造が得られる．
あとは，木が同一のものであるかを判定する必要があるが，これは木を文字列によって表現することで実現ができる（ノードの数はそんなに多くないはずなので）．
各ノードの部分木を表す文字列が得られれば，それをソートして結合し，括弧でくくったものを返せば，木の一意的な表現が得られる．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using pii = pair<int, int>;
 
constexpr int dx[2][8] = {{0, 1, 0, -1, 0, 0, 0, 0}, {0, 1, 1, 1, 0, -1, -1, -1}};
constexpr int dy[2][8] = {{1, 0, -1, 0, 0, 0, 0, 0}, {-1, -1, 0, 1, 1, 1, 0, -1}};
 
string dfs(int y, int x, vector<vector<bool>>& visited, vector<string> const& v) {
    const int H = v.size();
    const int W = v[0].size();
    bool black = v[y][x] == '#';
    visited[y][x] = true;
    queue<pii> que;
    que.push(make_pair(y, x));
    vector<pii> next;
    while(!que.empty()) {
        auto p = que.front();
        int y2 = p.first,
            x2 = p.second;
        que.pop();
        for(int i = 0; i < (black ? 8 : 4); ++i) {
            int ny = y2 + dy[black][i],
                nx = x2 + dx[black][i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || visited[ny][nx]) {
                continue;
            }
            if(v[ny][nx] != v[y][x]) {
                next.push_back(make_pair(ny, nx));
            } else {
                visited[ny][nx] = true;
                que.push(make_pair(ny, nx));
            }
        }
    }
 
    string res = "(";
    vector<string> tmp;
    for(auto& to : next) {
        if(visited[to.first][to.second]) {
            continue;
        }
        tmp.push_back(dfs(to.first, to.second, visited, v));
    }
    sort(tmp.begin(), tmp.end());
    for(auto& s : tmp) {
        res += move(s);
    }
    res += ")";
    return res;
}
 
int main() {
    int h1, w1;
    while(cin >> h1 >> w1, h1) {
        vector<string> v(h1 + 2, string(w1 + 2, '.'));
        vector<vector<bool>> visited1(h1 + 2, vector<bool>(w1 + 2));
        for(int i = 1; i <= h1; ++i) {
            string s;
            cin >> s;
            v[i] = "." + s + ".";
        }
        int h2, w2;
        cin >> h2 >> w2;
        vector<string> v2(h2 + 2, string(w2 + 2, '.'));
        vector<vector<bool>> visited2(h2 + 2, vector<bool>(w2 + 2));
        for(int i = 1; i <= h2; ++i) {
            string s;
            cin >> s;
            v2[i] = "." + s + ".";
        }
        bool same = dfs(0, 0, visited1, v) == dfs(0, 0, visited2, v2);
        cout << (same ? "yes" : "no") << endl;
    }
}

2017-07-08

AOJ 1615 Gift Exchange Party

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615

解法

友人の助けを借りて解いた．

この問題は最大流の問題に帰着させることができる．（想定解は違う方法だった．）
まず，二部グラフ {V1, V2} をつくる．V1 は n 頂点からなり，各人を表す．V2 は m 頂点からなり，親しい友人関係を表す．
親しい友人関係 i が u, v (V1 の頂点) であるならば， u -> 関係 i, v -> 関係 i にそれぞれ容量 1 の辺をはる．
次に，source -> 各人に容量をいい感じに定めて辺をはる（これはあとで説明する）．
最後に，各関係 -> dest に容量 1 の辺をはる．
こうしでできたグラフに対し，source から dest にフローを流す．この時，source -> 各人の辺に流れている流量が，その人がもらえるプレゼントを表していることがわかる．

あとは，source -> 各人の容量をいい感じに定めていく．

プレゼントを一番多くもらえる人のプレゼントの数の最小値 x は，source ->
各人の辺の容量を小さい方から試していって，初めて m の流量が流れた(つまりプレゼントの受け渡しが完全に終わった)ときの容量に対応していることがわかる．

また，プレゼントを一番もらえない人のプレゼントの数の最大値 y は，source -> 各人の容量を c と定めた時，c * n の流量が流れるような c の最大値に対応することがわかる．
これは，最適な解の時のプレゼントの受け渡し方をフロー上で考えるとわかる．プレゼントを一番もらえない人のプレゼント数を k とすると，それ以外の人は必ず k 以上もらっている．つまり，source -> 各人の容量を k に絞ると，流量は n * k になるはずである．
さらに，このようにフローを流すと，その時の最大値は，先ほど求めた x に対応していることが明らかにわかる(平均的に流せるなら当然そうすべきなので）．

n が小さいので割りと適当に書いても通る．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
struct edge {
    int to, cap, rev;
};
 
using edges = std::vector<edge>;
using graph = std::vector<edges>;
 
void add_edge(graph& g, int from, int to, int cap) {
    g[from].push_back(edge{to, cap, static_cast<int>(g[to].size())});
    g[to].push_back(edge{from, 0, static_cast<int>(g[from].size()-1)});
}
 
int dfs(graph& g, std::vector<bool>& used, int v, int t, int f) {
    if(v == t) {
        return f;
    }
    used[v] = true;
    for(int i=0; i<g[v].size(); ++i) {
        edge& e = g[v][i];
        if(!used[e.to] && e.cap > 0) {
            int d = dfs(g, used, e.to, t, std::min(f, e.cap));
            if(d > 0) {
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
 
int max_flow(graph& g, int s, int t) {
    int flow = 0;
    int INF = 1e9;
    std::vector<bool> used(g.size(), false);
    while(true) {
        std::fill(used.begin(), used.end(), false);
        int f = dfs(g, used, s, t, INF);
        if(f == 0) {
            return flow;
        }
        flow += f;
    }
 
}
 
int calc_max(int n, vector<int> const& u, vector<int> const& v) {
    const int m = u.size();
    graph g(n + m + 2);
    const int source = n + m;
    const int dest = n + m + 1;
    for(int i=0; i<m; ++i) {
        add_edge(g, u[i], n + i, 1);
        add_edge(g, v[i], n + i, 1);
        add_edge(g, n + i, dest, 1);
    }
    for(int i=0; i<n; ++i) {
        add_edge(g, source, i, 0);
    }
    int flow = 0;
    int res = 1;
    for(; ; ++res) {
        for(auto& e : g[source]) {
            e.cap += 1;
        }
        flow += max_flow(g, source, dest);
        if(flow == m) {
            break;
        }
    }
    return res;
}
 
int calc_min(int n, vector<int> const& u, vector<int> const& v) {
    const int m = u.size();
    graph g(n + m + 2);
    const int source = n + m;
    const int dest = n + m + 1;
    for(int i=0; i<m; ++i) {
        add_edge(g, u[i], n + i, 1);
        add_edge(g, v[i], n + i, 1);
        add_edge(g, n + i, dest, 1);
    }
    for(int i=0; i<n; ++i) {
        add_edge(g, source, i, 0);
    }
    int res = 0;
    int flow = 0;
    for(int i = 1; i <= 100; ++i) {
        for(auto& e : g[source]) {
            e.cap += 1;
        }
        flow += max_flow(g, source, dest);
        if(flow == n * i) {
            res = i;
        }
    }
    return res;
}
 
int main() {
    int n, m;
    while(cin >> n >> m, n) {
        vector<int> u(m), v(m);
        for(int i=0; i<m; ++i) {
            cin >> u[i] >> v[i];
            u[i]--;
            v[i]--;
        }
        int ma = calc_max(n, u, v);
        int mi = calc_min(n, u, v);
        cout << mi << ' ' << ma << endl;
    }
}

2017-07-07

AOJ 2237 The Castle

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2237

解法

bitDP．

dp[i][S][j] := i 番目(0-indexed) の敵と j 番目のねこが戦っていて，生き残っている猫が S であるときの勝てる最大確率

とする．このDPテーブルを最後の敵から最初の敵の順に（つまり後ろから）更新していく．
遷移は dp[i][S][j] = dp[i+1][S][j] * p[j][i] + max(dp[i][S & ~(1 << j)][x]) * (1 - p[j][i]) とかける．第1項は勝った場合，第2項は負けた場合である．
maxを適当に取るとTLEするので，maxを取る位置に注意すること．
また，このままDPテーブルを作るとMLEするので，直前の結果（つまり直後の敵の結果）だけを残してやる．
答えは max(dp[0][(1 << m) - 1][x])．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
double dp[2][1 << 16][16];
double memo[1 << 16];
 
int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<double>> p(m, vector<double>(n));
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> p[i][j];
        }
    }
    for(int S = 1; S < (1 << m); ++S) {
        for(int i = 0; i < m; ++i) {
            dp[n & 1][S][i] = 1;
        }
    }
    for(int i = n - 1; i >= 0; --i) {
        for(int S = 0; S < (1 << m); ++S) {
            for(int j = 0; j < m; ++j) {
                dp[i & 1][S][j] = 0;
            }
            for(int j = 0; j < m; ++j) {
                if(!((S >> j) & 1)) {
                    continue;
                }
                dp[i & 1][S][j] = dp[(i + 1) & 1][S][j] * p[j][i] + memo[S & ~(1 << j)] * (1 - p[j][i]);
            }
            double ma = 0;
            for(int j = 0; j < m; ++j) {
                if((S >> j) & 1) {
                    ma = max(ma, dp[i & 1][S][j]);
                }
            }
            memo[S] = ma;
        }
    }
    double res = *max_element(begin(dp[0][(1 << m) - 1]), end(dp[0][(1 << m) - 1]));
    cout << fixed << setprecision(10) << res << endl;
}

2017-07-03

Typical DP Contest F - 準急

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp

解法

dp[i][j] := i 番目の電車まで考えた時，右端が j である (j=0: 停車, j=1: 通過) 場合の数
として更新していく．
右端で停車しない場合は単純に dp[i-1][0] + dp[i-1][1] でよい．
停車する場合は，直前の K-1 回で停車し，かつ駅 1 から駅 i-1 までだけを考えれば条件を満たす場合の数を引く必要がある．
これは dp[i-K][1] で求まる．(直前 K-1 回が停車駅なら，駅 i-K では通過していなければならない)

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
constexpr ll MOD = 1e9+7;

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<ll>> dp(N+1, vector<ll>(2));
    dp[0][0] = dp[0][1] = 1;
    for(int i=1; i<=N; ++i) {
        if(i == 1) {
            dp[1][0] = 1;
            dp[1][1] = 0;
            continue;
        }
        dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD;
        dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD;
        if(i - K >= 0) {
            dp[i][0] = (dp[i][0] - dp[i-K][1] + MOD) % MOD;
        }
    }
    cout << dp[N][0] << endl;
}

2017-07-03

Typical DP Contest E - 数

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_number

解法

いわゆる桁DPというやつ．
dp[i][j][lt] := 上から i 桁目まで見た時，各桁の総和の余りが j であり，かつ N 未満かどうかが lt (less than) のときの場合の数

この dp だと 0 が常に条件を満たすので，最後に 1 を引く．

ソースコード

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

using ll = long long;
constexpr int mod = 1e9 + 7;

int main() {
    int d; cin >> d;
    string n; cin >> n;

    vector<vector<ll>> dp(d, vector<ll>(2));
    dp[0][0] = 1;
    for(int i = 0; i < (int)n.size(); ++i) {
        vector<vector<ll>> nxt(d, vector<ll>(2));
        const int cur = n[i] - '0';
        for(int s = 0; s < d; ++s) {
            for(int lt = 0; lt < 2; ++lt) {
                const int lim = lt ? 9 : cur;
                for(int v = 0; v <= lim; ++v) {
                    const int ns = (s + v) % d;
                    const int nlt = lt | (v < cur);
                    (nxt[ns][nlt] += dp[s][lt]) %= mod;
                }
            }
        }
        dp = move(nxt);
    }

    cout << (dp[0][0] + dp[0][1] + mod - 1) % mod << endl;
}

本番当日 開始直前

本番

役割分担

解いた流れ

コンテスト終了後

感想

問題文

解法

問題文

解法

問題文

解法

問題文

解法

問題文

解法

問題文

解法

本番当日　開始直前