ACM-ICPC 2018 国内予選 参加記

はじめに

7/6 に行われた ACM-ICPC 2018 国内予選の参加記です.
忘れないうちに書こうと思います.
今年は大雨で関西勢は大変でしたね.自分の大学もリモート参加推奨,という形になってしまいかなりバタバタしていました.

結果

チーム Zerokan_Sunshine として kazuma, nakano と一緒に参加しました.
結果はABCDEFの6問を通して全体6位,学内1位でした.
僕はA, C, Fを書きました.実装担当なのに楽なのしか書いてなくない?実装担当やめてね.

コンテスト中の流れ

  • A 読むとさすがにはいなので書きます (3:47 AC)
  • kazuma が B を書き始める.
  • その間に C を読んで考察,Cでミスると最悪なので一応 nakano に相談して確認しまくる.
  • B がバグっていた(?)ので時々交代して C を書く.
  • B を投げると WA だったらしい.というかサンプルが合っていなかったらしい.面白い(いいえ)
  • kazuma が直して B が通る (27:09 AC)
  • ついでに僕が C を通す (31:27 AC)
  • D はなんかやるだけっぽく,普段なら僕が書いてそうだけどFがやりたかったので kazuma に丸投げした.
  • 若干E聞いたけど嫌いなので(は?)nakano にまかせて F に集中することにした.
  • F で最初に自分が書いていたのは嘘なので nakano に修正してもらって,詰めてからこれなら解けるな,となった.O(n^2lognlogM) なのでどうかなあみたいな感じだった.M は三角形の長さの最大値.
  • kazuma の D と並列して F を書きはじめる.
  • D が通る.はいプロ.(1:13:10 AC)
  • nakano が E を大体紙コーディングしていた(神か?)ので kazuma にやってもらう.
  • E と F を並列で頑張る.どっちも結構バグっていてつらい.
  • E が先に通る.さすがプロ.(1:54:58 AC)
  • F もなんかバグは治ったけどさすがに遅い.
  • 一旦実行止めて定数倍改善してから,とりあえず裏で走らせておく戦略をとる(途中でオーダー落とせたら書き直す感じで).
  • まあ思いつかなかったよね.そうこうしているうちに通ってしまった.(2:45:02 AC)
  • ちなみに実行に10分ぐらいかかりました(最悪)
  • この時点で6位だった.まじか.予想順位より10位ぐらい高いなあ,という話をメンバーとした.
  • 15分でGを書くのは厳しいので,感想戦をして適当に過ごす.
  • コンテスト終了,結局順位は変わらなかった.

[追記]
そういえば今年はかなり特殊な実施状況だったので勘違いされないように注意しておくと,「並列して書く」というのはもちろん複数台使うという意味ではなく,1台のPCで時々交代しながら,という意味です.

感想

今年は京大勢が奮闘していたようです.その中で学内1位を取れたのはかなり嬉しかった.
正直AtCoderが苦手すぎてICPCに逃げているみたいなところがあったので,ちゃんと結果に現れててよかった.
F はなんかズルしたみたいな気持ちになるのが心残りです.ルール的にはもちろん問題ないんですけどねえ.O(nlognlogM) とかで解かせたいのかな,と思っていたんですが n がどうしても落ちなくて辛かった.ひょっとすると (n^2 logM) で適当に定数倍改善すれば十分早かったのかな.
G は明らかに僕担当だったんですけど時間的に厳しかったなあ.あと30分ぐらいあれば書いていそう.
アジアではもっと貢献できるように頑張りたいと思います.

ところで,11位で予選通過できなかった同期のチームがあるのはかなり残念ですね…(東大勢はもっと激しいと考えると恐ろしいな…

謝辞

この大雨の中,運営とのやり取りなどを行ってくださった先生やコーチの方々,そして僕を大学まで平常通り送り届けてくれた近鉄と京阪に感謝の意を表し,終わりの言葉とさせていただきます.

AOJ 2702 Alternate Escape

解法

後退解析で解く.
ゲームの探索なので,最初は始点からDFSしたくなるかもしれないが,普通に状態が自分に戻ってくるような遷移があるので困る.
こういうときは確定しているところから探索を始めて,始点に戻ってこれるか,みたいに考える.
最初,Alice が勝つことができる位置は,端で,壁の状態がどちらでもゴールできるような位置である.
これを queue なりなんなりに入れて管理しておき,そこから遷移できるところの勝利フラグを立てていく.
以降は勝利フラグが壁の状態によらず立っている場合に,新たに勝利確定状態として queue に突っ込む.
探索が終わったときに (r, c) の勝利確定フラグを確認して終わり.
計算量は O(wh).

ソースコード

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

using pii = pair<int, int>;

template<typename T>
std::vector<T> table(int n, T v) { return std::vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return std::vector<decltype(val)>(n, std::move(val));
}

int main() {
    int h, w, r, c;
    while(cin >> h >> w >> r >> c, h) {
        r--; c--;
        vector<vector<int>> horz(h + 1, vector<int>(w)), vert(h, vector<int>(w + 1));
        for(int i = 0; i < 2 * h + 1; ++i) {
            if(i & 1) {
                for(int j = 0; j < w + 1; ++j) {
                    cin >> vert[i / 2][j];
                }
            } else {
                for(int j = 0; j < w; ++j) {
                    cin >> horz[i / 2][j];
                }
            }
        }
        auto win = table(h, w, 2, -1); // 1: alice, 0: bob, -1: ?
        queue<tuple<int, int, int>> que;
        for(int i = 0; i < h; ++i) {
            win[i][0][vert[i][0]] = win[i][w - 1][vert[i][w]] = 1;
        }
        for(int i = 0; i < w; ++i) {
            win[0][i][horz[0][i]] = win[h - 1][i][horz[h][i]] = 1;
        }
        for(int i = 0; i < h; ++i) {
            if(win[i][0][0] == 1 && win[i][0][1] == 1) {
                que.emplace(i, 0, 0);
                que.emplace(i, 0, 1);
            }
        }
        for(int i = 0; i < w; ++i) {
            if(win[0][i][0] == 1 && win[0][i][1] == 1) {
                que.emplace(0, i, 0);
                que.emplace(0, i, 1);
            }
        }

        constexpr int dx[4] = {0, 1, 0, -1};
        constexpr int dy[4] = {1, 0, -1, 0};
        auto in_range = [&] (int y, int x) {
            return 0 <= y && y < h && 0 <= x && x < w;
        };
        auto check_wall = [&] (int y, int x, int dir, int f) {
            if(dir & 1) { // move x
                return vert[y][x + (dir == 1)] == f;
            } else {
                return horz[y + (dir == 0)][x] == f;
            }
        };
        while(!que.empty()) {
            int y, x, f;
            tie(y, x, f) = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i) {
                int ny = y + dy[i], nx = x + dx[i];
                if(!in_range(ny, nx)) continue;
                for(int nf = 0; nf < 2; ++nf) {
                    if(check_wall(y, x, i, nf) && win[ny][nx][nf] == -1) {
                        win[ny][nx][nf] = 1;
                        if(win[ny][nx][!nf] == 1) {
                            que.emplace(ny, nx, 0);
                            que.emplace(ny, nx, 1);
                        }
                    }
                }
            }
        }

        if(win[r][c][0] == 1) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

感想

昔問題で出されて,その時は解けなかった気がする.

AOJ 0324 Downhill Race

解法

ダイクストラで解く.
与えられるグラフはDAGになっていて,この上で2回違う条件で最短経路を求めたい.しかし依存関係にあるので独立にはできない.
こういうときは1回目と2回めを同時に処理するのが定番な気がするので,それで考えてみる.つまり,2つの頂点を同時に持つようにする.
そしてこれもある意味定番なのだが,これらの2つの頂点ないし遷移は,ある規則によって順序付けられるようにすると良い.
今回であればトポロジカル順序を利用する.

dist[fst_v][sec_v] := 1回目の経路の末端が頂点 fst_v であり,2回目の経路の末端が頂点 sec_v であるときの最小コスト

とする.

fst_v == sec_v のときの遷移は,以下の2パターンがある.

  • 同じ辺を使って移動する.
  • 違う辺を使って移動する(今回は多重辺がないので違う頂点へ移動する).

辺のコスト t2 を使うのはこの1つ目の場合である.

次に,fst_v != sec_v のときを考える.これは先に述べたトポロジカル順序に則って遷移させる.
トポロジカル順序で fst_v < sec_v のとき,fst_v を先に遷移させる.このとき,遷移時の辺のコストは t1 としてよい.
逆に fst_v > sec_v のときは,sec_v を先に遷移させる.

これでうまくいく.トポロジカル順序で小さい方を先に移動させることで,1回目と2回目の最短経路で t1 を2度使うことはなくなる.
一応示しておく.もし t1 を2回使ってしまうような状況に陥るとしたら,1回めと2回目の経路で共通の頂点を用い,かつそこからの行き先が同じような経路をもつ場合である.
トポロジカル順序で小さい方を先に処理した場合,共通の頂点を使うならば,かならず fst_v == sec_v で処理されるようになる.このときは場合分けしているので t1 を2回使うことはない.
逆に言うとこうしないと t1 を2回使いうる.例えば,共通頂点が v3 として (v1, v2) -> (v3, v2) -> (v4, v2) -> (v4, v3) のように遷移すると,最後の v2 -> v3 のコストでどちらを使えばいいかわからなくなってしまう.

計算量は O( (N^2 + P^2) log N ) となる.

ソースコード

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

using ll = long long;

constexpr ll inf = 1e18;

struct edge {
    int to;
    ll c1, c2;
};

using edges = vector<edge>;
using graph = vector<edges>;

int main() {
    int n, p;
    cin >> n >> p;
    graph g(n);
    for(int i = 0; i < p; ++i) {
        int s, e;
        ll t1, t2;
        cin >> s >> e >> t1 >> t2;
        g[s - 1].push_back(edge{e - 1, t1, t2});
    }

    vector<int> topo(n, -1);
    int idx = 0;
    function<void(int)> calc_topo = [&] (int v) {
        if(topo[v] != -1) return;
        for(auto& e : g[v]) {
            calc_topo(e.to);
        }
        topo[v] = idx++;
    };
    calc_topo(0);

    vector<vector<ll>> dist(n, vector<ll>(n, inf));
    dist[0][0] = 0;
    using state = tuple<ll, int, int>;
    priority_queue<state, vector<state>, greater<state>> que;
    que.emplace(0, 0, 0);
    while(!que.empty()) {
        ll cur_c;
        int fst_v, sec_v;
        tie(cur_c, fst_v, sec_v) = que.top();
        que.pop();
        if(fst_v == sec_v) {
            for(auto& e : g[fst_v]) {
                ll nxt_c = cur_c + e.c1 + e.c2;
                if(dist[e.to][e.to] > nxt_c) {
                    dist[e.to][e.to] = nxt_c;
                    que.emplace(nxt_c, e.to, e.to);
                }
            }

            for(auto& e1 : g[fst_v]) {
                for(auto& e2 : g[sec_v]) {
                    if(e1.to == e2.to) continue;
                    ll nxt_c = cur_c + e1.c1 + e2.c1;
                    if(dist[e1.to][e2.to] > nxt_c) {
                        dist[e1.to][e2.to] = nxt_c;
                        que.emplace(nxt_c, e1.to, e2.to);
                    }
                }
            }
        } else {
            if(topo[fst_v] > topo[sec_v]) {
                for(auto& e : g[fst_v]) {
                    ll nxt_c = cur_c + e.c1;
                    if(dist[e.to][sec_v] > nxt_c) {
                        dist[e.to][sec_v] = nxt_c;
                        que.emplace(nxt_c, e.to, sec_v);
                    }
                }
            } else {
                for(auto& e : g[sec_v]) {
                    ll nxt_c = cur_c + e.c1;
                    if(dist[fst_v][e.to] > nxt_c) {
                        dist[fst_v][e.to] = nxt_c;
                        que.emplace(nxt_c, fst_v, e.to);
                    }
                }
            }
        }
    }

    cout << dist[n - 1][n - 1] << endl;
}

感想

トポロジカル順序で小さい方から遷移するときに,遷移先がもう一方の頂点より大きくないとだめ,みたいなよくわからない処理を書いて(なぜ?)WAを食らってしまった.
他にも最小費用流とか生えそうな見た目をしているけど,経験的に1回め流れるときと2回め流れるときでコストを分けるみたいなフローは書くのが難しいと思う.解けるのかな?
最後に類題を貼り付けておきます.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324

ちなみにこの問題ダイクストラで解きましたがDAGなので普通に DP で良いと思う.log が取れるので定数倍しんどいときは DP で解くべき.

AOJ 0322 Slates

解法

二分探索で解ける.
左が欠けているやつを考えるときは末尾から比べたいので,各文字を反転した文字列集合も別に持っておく.
与えられた石版に ? がある場合は26文字全通り試す.
左が欠けている場合,反転した文字列集合にたいして,石版の文字の末尾をインクリメントした文字の lower_bound と,石版の文字の lower_bound の差がその時の答え.
右が欠けている場合は同じことを反転してないほうの文字列集合にたいしてやる.

たとえば apple, apricot が集合に合って,ap* を調べたい場合,"aq" による lower_bound と "ap" による lower_bound を取ると apple, apricot 分の幅が得られる.

計算量は O(NlogN + M|S|logN).(|S| は石版の文字列長)

ソースコード

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

using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> ws(n);
    set<string> origin;
    for(int i = 0; i < n; ++i) {
        cin >> ws[i];
        origin.insert(ws[i]);
    }
    auto rws = ws;
    for(auto& s : rws) reverse(begin(s), end(s));
    sort(begin(ws), end(ws));
    sort(begin(rws), end(rws));

    while(m--) {
        string ss;
        cin >> ss;
        bool left = ss[0] == '*', right = ss.back() == '*';
        string s;
        for(auto c : ss) {
            if(c != '*') s += c;
        }

        ll ans = 0;
        auto get_cnt = [](vector<string> const& ws, string& s) {
            auto l = lower_bound(begin(ws), end(ws), s);
            s.back() += 1;
            auto r = lower_bound(begin(ws), end(ws), s);
            s.back() -= 1;
            return r - l;
        };
        if(left) {
            reverse(begin(s), end(s));
            ans += get_cnt(rws, s);
        } else if(right) {
            ans += get_cnt(ws, s);
        } else {
            ans += origin.count(s);
        }

        for(int i = 0; i < (int)s.size(); ++i) {
            if(s[i] == '?') {
                for(char c = 'a'; c <= 'z'; ++c) {
                    s[i] = c;
                    if(left) {
                        ans += get_cnt(rws, s);
                    } else if(right) {
                        ans += get_cnt(ws, s);
                    } else {
                        ans += origin.count(s);
                    }
                }
                break;
            }
        }

        cout << ans << endl;
    }
}

感想

最初これにロリハ持ち出して解こうとして最悪だった.挙げ句MLEするし…….うーん…….

AOJ 0321 Investigation of Club Activities

解法

union find 木を使うと楽?
union find の各集合がどのクラブに属するかを別に vector で持っておく.
a と b が同じ部活に所属している場合,マージするのだが違うクラブに属している(少なくともどちらか一方の集合のクラブの情報がない場合はセーフ)ならアウト.
c が部活 x に属しているとき,c の属する集合のクラブの情報と比べて違えばダメ.まだクラブの情報がないなら x を書き込む.
これを上から順番にやる.

ソースコード

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

class union_find {
public:
    union_find(int n) : par(n, -1) {}
    int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
private:
    vector<int> par;
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    union_find uf(n);
    vector<int> club(n, -1);
    int ans = 0;
    for(int i = 0; i < k; ++i) {
        int type; cin >> type;
        if(type == 1) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            int ra = uf.root(a), rb = uf.root(b);
            if(club[ra] == -1 || club[rb] == -1 || club[ra] == club[rb]) {
                uf.unite(a, b);
                club[uf.root(a)] = max(club[ra], club[rb]);
            } else {
                ans = i + 1;
                break;
            }
        } else {
            int c, x;
            cin >> c >> x;
            c--; x--;
            if(club[uf.root(c)] == -1 || club[uf.root(c)] == x) {
                club[uf.root(c)] = x;
            } else {
                ans = i + 1;
                break;
            }
        }
    }
    cout << ans << endl;
}

感想

PCK予選って解説無いんですかね?

AOJ 2693 JAG-channel II

解法

いかにもな bitDP 感がある.
しかしそれでもなんらかの形で順番は保持しないとどうしようもなさそうに見える.
うまくやれば状態に順列持てたりしないかな~と制約を読むと N - 3 <= K <= N - 1 とかいう怪しすぎる制約がある.
冷静に考えてみると,今使ったやつがわかれば先頭 K 文字は確定するので,残りの文字だけの並びを状態に持てば十分である.
N - K はたかだか3だから,この並びの状態は 6 通りしか無い.
したがって,
dp[S][ord] := 使った人の集合が S で,その時のスレッドの並びが ord であるときから始めて,辞書順最小の答え
とするメモ化再帰DPを書く.
あとは一番最初に何を使うか,そしてその時に考えられる初期状態の順列はなにか,を全探索すると解ける.

計算量は O(2^n * n^2 * 6 * 6) ぐらい.

こういう辞書順最小構築はメモ化再帰DPで書くと実装がきれいになりやすいと思う.

ソースコード

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<string> post(n);
    for(int i = 0; i < n; ++i) {
        cin >> post[i];
    }

    vector<map<string, string>> dp(1 << n);
    function<string(int, string)> rec = [&](int S, string order) {
        if(S == (1 << n) - 1) return string();
        if(dp[S].count(order)) return dp[S][order];
        string& res = dp[S][order];
        res = "invalid";
        for(int i = 0; i < n; ++i) {
            if(S & (1 << i)) continue;
            int idx = 0;
            for(int j = 0; j < n; ++j) {
                if(post[i][idx] == order[j]) {
                    idx++;
                }
            }
            if(idx != k) continue;
            string nord = post[i];
            reverse(begin(nord), end(nord));
            for(auto c : order) {
                if(find(begin(nord), end(nord), c) == end(nord)) {
                    nord += c;
                }
            }
            string s = rec(S | (1 << i), nord);
            if(s != "invalid") {
                res = (char)('A' + i) + s;
                break;
            }
        }
        return res;
    };

    string ans = "Z";
    for(int fst = 0; fst < n && ans == "Z"; ++fst) {
        string s = post[fst];
        reverse(begin(s), end(s));
        string remain;
        for(char c = 'A'; c < 'A' + n; ++c) {
            if(find(begin(s), end(s), c) == end(s)) {
                remain += c;
            }
        }
        do {
            string ord = s + remain;
            auto t = rec(1 << fst, ord);
            if(t != "invalid") {
                ans = min(ans, (char)('A' + fst) + t);
            }
        } while(next_permutation(begin(remain), end(remain)));
    }

    cout << ans << endl;
}

感想

N - 3 <= K <= N - 1 とか書かれると意外と気が付かないもんだなあ(反省).

Codeforces Round #491 (Div.2) F. Concise and clear

解法

冪乗の形を使っていかに短くできるか,という問題.
まず,n * m (n, m はただの自然数)のような表現は完全に不利.
例えば 99 * 99 を考えてみるとわかりやすいが,そのまま出力したほうが短いからである.
すると,足し算以外で考えるべきは

  • p ^ q
  • a * p ^ q
  • p ^ q * x ^ y

しかない.
p ^ q として使いうる候補は数えてみるとわかるが多くないので,全部作ってしまう.
p ^ q * x ^ y についてだが,それぞれの p ^ q, x ^ y の長さはたかだか4であるとして良い(つまり3文字か4文字の p ^ qだけ考えればよい).
6文字以上はオーバーするから当然いらない.問題は5文字の p ^ q をなぜ考慮しなくてよいかである.
与えられる入力がたかだか10桁であることに注目する.n = 10^10 の場合は 10 ^ 10 が当然最適なので関係ない.つまり9桁の場合のみ注目すればいい.
すると,p ^ q で5文字使ってしまうと "^" を考慮して x ^ y で使えるのはあと3文字分しかない.
しかし3文字使っていいなら,トータル9文字になるので入力をそのまま出力すればいい.したがって5文字は考えなくて良いことがわかる.

最後に,a * (上で求めた冪の形)+ b を全部ためして一番短いやつを選ぶ.

ソースコード

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

using ll = long long;

int main() {
    ll n; cin >> n;

    const ll ub = n;
    map<ll, string> pw, pw_len3or4;
    for(ll i = 2; i * i <= ub; ++i) {
        ll p = i;
        for(int j = 2; p * i <= ub; ++j) {
            p *= i;
            string s = to_string(i) + "^" + to_string(j);
            if(pw.count(p) == 0 || pw[p].size() > s.size()) {
                pw[p] = s;
            }
        }
    }
    for(auto& p : pw) {
        if(p.second.size() == 3 || p.second.size() == 4u) {
            pw_len3or4.insert(p);
        }
    }
    for(auto& p : pw_len3or4) {
        for(auto& q : pw_len3or4) {
            if(p.first > ub / q.first) continue;
            string s = p.second + "*" + q.second;
            ll val = p.first * q.first;
            if(val <= ub && (pw.count(val) == 0 || pw[val].size() > s.size())) {
                pw[val] = s;
            }
        }
    }

    string ans = to_string(n);
    for(auto& p : pw) {
        ll d = n / p.first;
        if(d == 0) break;
        string s;
        if(d > 1) s += to_string(d) + "*";
        s += p.second;
        ll r = n % p.first;
        if(r > 0) {
            s += "+";
            if(pw.count(r) && to_string(r).size() > pw[r].size()) {
                s += pw[r];
            } else {
                s += to_string(r);
            }
        }
        if(ans.size() > s.size()) {
            ans = s;
        }
    }

    cout << ans << endl;
}

感想

本番ではやばいと思ってほとんど考えず諦めて hack に移行してしまったが,もったいなかった.