2018-08-06

Codeforces Round #307 (Div.2) D. GukiZ and Binary Operations

問題文

http://codeforces.com/contest/551/problem/D

解法

結論をいうと行列累乗で解ける．
まず重要なポイントとして，各ビットは独立に考えて良い（全く同じ条件なので）．
つまり，結局この問題は1ビットの問題に帰着される．
1ビットの n 個の整数を，問題文に記された式で計算した結果が0になるような場合の個数を求めたい．
dp[i][j] := i 個まで見て，それまでの結果が j (0 or 1) であるような場合の数
とすると，遷移は
dp[i + 1][0] = dp[i][0] + dp[i][1];
dp[i + 1][1] = dp[i][0];
である．これはフィボナッチ数なので，行列累乗により O(logn) で求まる．
これが求まれば，余事象を考えて結果が 1 の場合の数も求まる．
結果が0，1となる場合の数をそれぞれ a, b とおく．
最後に k について求めれば終わり．
popcount(k) = X とおく．すると明らかに，求める答えは a^(l - X) * b^X である．

l が小さすぎて k を超えない場合は明らかに0なので，先に弾いておくとよい．特に l == 64 の場合は，条件を雑に書くとオーバーフローするので注意．

ソースコード

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

using ull = unsigned long long;
using matrix = vector<vector<ull>>;

matrix mul(matrix const& a, matrix const& b, const ull mod) {
    const int n = a.size();
    const int m = b[0].size();
    assert((int)a[0].size() == n && (int)b.size() == n);
    matrix res(n, vector<ull>(m));
    for(int i = 0; i < n; ++i) {
        for(int k = 0; k < n; ++k) {
            for(int j = 0; j < m; ++j) {
                (res[i][j] += a[i][k] * b[k][j]) %= mod;
            }
        }
    }
    return res;
}

matrix matpow(matrix A, ull n, const ull mod) {
    const int m = A.size();
    matrix res(m, vector<ull>(m));
    for(int i = 0; i < m; ++i) res[i][i] = 1;
    while(n > 0) {
        if(n & 1) res = mul(move(res), A, mod);
        A = mul(A, A, mod);
        n >>= 1;
    }
    return res;
}

ull modpow(ull x, ull n, const ull mod) {
    ull res = 1;
    x %= mod;
    while(n > 0) {
        if(n & 1) (res *= x) %= mod;
        (x *= x) %= mod;
        n >>= 1;
    }
    return res;
}

int main() {
    ull n, k, l, m;
    cin >> n >> k >> l >> m;
    if(l < 64 && k >= (1ULL << l)) {
        cout << 0 << endl;
        return 0;
    }

    matrix A(2, vector<ull>(2)), b(2, vector<ull>(1));
    A[0][0] = 1, A[0][1] = 1;
    A[1][0] = 1;
    b[0][0] = 1;
    A = matpow(A, n, m);
    auto y = mul(A, b, m);
    const int cnt2 = __builtin_popcountll(k), cnt1 = l - cnt2;
    const ull v1 = (y[0][0] + y[1][0]) % m;
    const ull v2 = (modpow(2, n, m) - v1 + m) % m;
    cout << (modpow(v1, cnt1, m) * modpow(v2, cnt2, m) % m) << endl;
}

感想

本番中に通せたけど，builtin_popcount を32ビット版で使ってて1WA．
気をつけないといけませんね．

2018-08-05

Codeforces Round #305 (Div.1) C. Mike and Foam

Codeforces 競プロ

問題文

http://codeforces.com/contest/547/problem/C

解法

与えられた値を素因数分解して出てくる素数の数は高々6個しかない．
gcd を考えるときはこれだけで十分である．
今回は直接答えを求めず，gcd(a, b) != 1 となる個数を求めて最後にトータルから引くことにする．

値 a を素因数分解して出てきた素数を p1, p2, ..., pk とする．
また，今の棚にあるお酒で，値 v と互いに素でないものの個数を vs[v] と表すことにする．
すると，値 a が追加された時に gcd(a, b) != 1 となる個数の増減は，
vs[p1] + vs[p2] + ... + vs[pk] - vs[p1 * p2] - vs[p1 * p3] - ...
のように包除で求めることができる．
項の個数は 2^6 しかないので，この部分は愚直に計算して良い．
これを各クエリごとにやるので，クエリパートは O(2^6 * q) となる．
前計算（p1 とか求める部分）も同様なのでこれで解ける．

ソースコード

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

using ll = long long;

int main() {
    constexpr int max_val = 1 << 19;
    vector<bool> is_prime(max_val, true);
    vector<int> prime;
    for(int i = 2; i < max_val; ++i) {
        if(is_prime[i]) {
            prime.push_back(i);
            for(int j = i * 2; j < max_val; j += i) {
                is_prime[j] = false;
            }
        }
    }

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<vector<int>> ps(n);
    auto insert_val = [&] (vector<int>& v, int val) {
        vector<int> added = {val};
        for(auto y : v) {
            added.push_back(-y * val);
        }
        v.insert(end(v), begin(added), end(added));
    };
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        int x = a[i];
        for(auto p : prime) {
            if(p * p > x) break;
            if(x % p == 0) {
                insert_val(ps[i], p);
                while(x % p == 0) x /= p;
            }
        }
        if(x > 1) insert_val(ps[i], x);
    }

    ll used_num = 0, tans = 0;
    vector<bool> used(n);
    vector<int> vs(max_val);
    while(q--) {
        int idx; cin >> idx;
        idx--;
        if(used[idx]) {
            used_num -= 1;
            for(auto x : ps[idx]) {
                const int sign = x < 0 ? 1 : -1;
                vs[abs(x)]--;
                tans += sign * vs[abs(x)];
            }
        } else {
            used_num += 1;
            for(auto x : ps[idx]) {
                const int sign = x < 0 ? -1 : 1;
                tans += sign * vs[abs(x)];
                vs[abs(x)]++;
            }
        }
        used[idx] = !used[idx];
        cout << used_num * (used_num - 1) / 2 - tans << endl;
    }
}

感想

これ苦手．ジャッジ解のコードは遠回りせず直接求めるもので，かなり簡潔だった．
多分僕がジャッジ解と同じように書くとバグるからこれで良かったのかも．

2018-08-04

Codeforces Round #305 (Div.1) B. Mike and Feet

競プロ Codeforces

問題文

解法1

値の大きい方から追加していって，区間やその幅をset, multiset で管理して頑張るだけ．
実装が悲しい感じになる．

ソースコード1

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

using pii = pair<int, int>;
constexpr int inf = 1e9;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), as;
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        as.push_back(a[i]);
    }
    sort(begin(as), end(as));
    as.erase(unique(begin(as), end(as)), end(as));
    for(auto& h : a) {
        h = lower_bound(begin(as), end(as), h) - begin(as);
    }

    vector<vector<int>> pos(as.size());
    for(int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
    }

    set<pii> segs;
    multiset<int> lens; // segment length
    vector<int> ans(n, -1);

    auto erase_seg = [&](pii s) {
        segs.erase(s);
        lens.erase(lens.lower_bound(s.second - s.first + 1));
    };
    auto insert_seg = [&] (pii s) {
        segs.insert(s);
        lens.insert(s.second - s.first + 1);
    };
    for(int i = as.size() - 1; i >= 0; --i) {
        for(auto& p : pos[i]) {
            if(segs.empty()) {
                insert_seg(make_pair(p, p));
                continue;
            }
            auto it = segs.lower_bound(make_pair(p, -1));
            if(end(segs) != it && begin(segs) != it) {
                auto pre = prev(it);
                if(it->first == p + 1 && pre->second + 1 == p) { // combine two seg
                    auto s1 = *pre, s2 = *it;
                    erase_seg(s1);
                    erase_seg(s2);
                    insert_seg(make_pair(s1.first, s2.second));
                } else if(it->first == p + 1) {
                    auto s = *it;
                    erase_seg(s);
                    insert_seg(make_pair(s.first - 1, s.second));
                } else if(pre->second + 1 == p) {
                    auto s = *pre;
                    erase_seg(s);
                    insert_seg(make_pair(s.first, s.second + 1));
                } else {
                    insert_seg(make_pair(p, p));
                }
            } else if(end(segs) != it) {
                auto s = *it;
                if(s.first == p + 1) {
                    erase_seg(s);
                    insert_seg(make_pair(s.first - 1, s.second));
                } else {
                    insert_seg(make_pair(p, p));
                }
            } else {
                it = prev(it);
                auto s = *it;
                if(s.second + 1 == p) {
                    erase_seg(s);
                    insert_seg(make_pair(s.first, s.second + 1));
                } else {
                    insert_seg(make_pair(p, p));
                }
            }
        }
        auto maxi_len = *prev(end(lens));
        ans[maxi_len - 1] = max(ans[maxi_len - 1], as[i]);
    }

    for(int i = n - 1; i >= 1; --i) {
        ans[i - 1] = max(ans[i - 1], ans[i]);
    }

    for(int i = 0; i < n; ++i) {
        printf("%d\n", ans[i]);
    }
}

解法2

各要素の値が効力を持つ幅が分かればいいわけで，これは stack で実装可能．
つまり，ある要素 a[i] が左にどれだけ効力を持つか，言い換えれば j < i で初めて a[j] < a[i] となる j はなにかが分かればよい．右も同様にやる．
答えを ans[i] とすると明らかに ans は単調減少なのでいい感じにマージできて，計算量は O(n)．

ソースコード2

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> st;
    vector<int> llen(n), rlen(n);
    for(int i = 0; i < n; ++i) {
        while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        llen[i] = (st.empty() ? i + 1 : i - st.back());
        st.push_back(i);
    }
    st.clear();
    for(int i = n - 1; i >= 0; --i) {
        while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        rlen[i] = (st.empty() ? n - i : st.back() - i);
        st.push_back(i);
    }

    vector<int> ans(n);
    for(int i = 0; i < n; ++i) {
        ans[llen[i] + rlen[i] - 2] = max(ans[llen[i] + rlen[i] - 2], a[i]);
    }
    for(int i = n - 1; i >= 1; --i) {
        ans[i - 1] = max(ans[i - 1], ans[i]);
    }

    for(int i = 0; i < n; ++i) {
        cout << ans[i] << " \n"[i + 1 == n];
    }
}

感想

実装担当が解法1みたいなコードを書いているようじゃだめなんだよなあ．
まあ適当にかけるという利点はあるかもしれない．

2018-08-02

Codeforces Round #305 (Div.1) A. Mike and Frog

競プロ Codeforces

問題文

http://codeforces.com/contest/547/problem/A

解法

mod を取っているので，それぞれ高々 m 回でループするのはすぐわかる．
とりあえずそれぞれについて目的の高さになるまで愚直にシミュレートする．
この時到達できないならそもそも不可能なので -1．
よって以降はどちらも到達可能であると仮定する．
さらに，現時点で同時刻にどちらも目的の高さになっているならそれが答えなので，そうなっていないと仮定する．
ひとまずカエルを目的の高さになるまで進める（時間 t1 でそうなるとする）と，それ以降はサイクルの大きさ（c1 とおく）の倍数時間だけ進めたときのみ，カエルは目的の高さになっていることがわかる．
ただし，目的の高さに到達可能であっても，サイクル上に目的の高さがないなら不可能であり，この場合は -1 を出力する必要がある．
あとはこの c1 回の遷移を1まとまりとした写像 f を構築して，花のほうに適用するだけでよい．
不可能でないなら，これも高々 m 回でループするはずである．
もし cnt 回目の f の適用で花が目的の高さになったなら，答えは t1 + c1 * cnt となる．

ソースコード

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

using ll = long long;
constexpr ll inf = 1e18;

int main() {
    int m;
    vector<ll> h(2), a(2), x(2), y(2);
    cin >> m;
    for(int i = 0; i < 2; ++i) {
        cin >> h[i] >> a[i] >> x[i] >> y[i];
    }

    vector<ll> t(2), cycle_sz(2);
    bool on_cycle = false;
    for(int i = 0; i < 2; ++i) {
        vector<ll> d(m, inf);
        d[h[i]] = 0;
        ll cur = h[i];
        while(true) {
            const ll nxt = (x[i] * cur + y[i]) % m;
            if(d[nxt] != inf) {
                cycle_sz[i] = (d[cur] - d[nxt] + 1);
                if(i == 0) {
                    on_cycle = d[a[i]] != inf && d[a[i]] >= d[nxt];
                }
                break;
            }
            d[nxt] = d[cur] + 1;
            cur = nxt;
        }
        t[i] = d[a[i]];
    }

    if(t[0] == inf || t[1] == inf) {
        cout << -1 << endl;
        return 0;
    }
    if(t[0] == t[1]) {
        cout << t[0] << endl;
        return 0;
    }
    if(!on_cycle) {
        cout << -1 << endl;
        return 0;
    }

    ll A = 1, B = 0; // calc (f^cycle[0])(x) = Ax + B
    for(int i = 0; i < cycle_sz[0]; ++i) {
        auto nA = (A * x[1]) % m;
        auto nB = (y[1] + x[1] * B) % m;
        A = nA, B = nB;
    }

    ll cur_h2 = h[1];
    for(int i = 0; i < t[0]; ++i) {
        cur_h2 = (x[1] * cur_h2 + y[1]) % m;
    }

    ll cnt = 0;
    while(cur_h2 != a[1] && cnt < m) {
        cur_h2 = (cur_h2 * A + B) % m;
        cnt += 1;
    }

    if(cnt < m && cur_h2 == a[1]) {
        cout << t[0] + cycle_sz[0] * cnt << endl;
    } else {
        cout << -1 << endl;
    }
}

感想

算数に対する基礎体力がなくて手こずりまくった．
サイクルの上にいないなら NG ということに不覚にもしばらく気が付かなかった．

2018-07-30

Codeforces Round #302 (Div.1) C. Remembering Strings

Codeforces 競プロ

問題文

http://codeforces.com/contest/543/problem/C

解法

n <= 20 から bitDP が頭をよぎって，実際そのとおりなんですが，この制約にはもう1つ意味がある．
それは，a-z の26文字より小さいので，各文字は1箇所変更するだけで easy to remember にできるということ．
つまり，ある文字列 i を easy to remember にするには，以下のどちらかしかない．

ある位置 j に着目して，a[i][j] のコストを払う
ある位置 j に着目して，位置 j の他の文字列をすべて見たときに s[i][j] と同じ文字のものを，すべて easy to remember にする（これは，この集合の中で最もコストが大きいもの以外を変えれば良い）

場合によっては，結果的に場合2の部分集合だけ変えるような方法が最適なことがあるかもしれないが，これは1つ目のケースを何回か適用したものであると考えられるので，これで全ケース列挙できる．

bitDP の遷移が問題で，多分いつもどおり bitDP をやろうとすると，各集合 S （ビットで管理してるやつ）から遷移の候補がたくさんあって困る．
そこで，各集合 S について，まだ使ってない文字列の中で最小インデックスの文字列を easy to remember にする遷移だけ考えると，遷移のオーダーが削減できる．
このためにはループの順番を S -> i にしないといけない（0 <= i < m）．
遷移自体は先の2パターンだけ考えればよいので，トータル O(m2^n + 前計算) でできる．

ソースコード

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

constexpr int inf = 1e9;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for(int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    vector<vector<int>> cost(m, vector<int>(n, inf));
    vector<vector<int>> mask(m, vector<int>(n));
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            vector<int> cs;
            int msk = 0;
            for(int k = 0; k < n; ++k) {
                if(s[j][i] == s[k][i]) {
                    cs.push_back(a[k][i]);
                    msk |= (1 << k);
                }
            }
            sort(begin(cs), end(cs));
            cost[i][j] = accumulate(begin(cs), end(cs) - 1, 0);
            mask[i][j] = msk;
        }
    }

    vector<int> dp(1 << n, inf);
    dp[0] = 0;
    for(int S = 0; S < (1 << n) - 1; ++S) {
        int lb = 0;
        while(S & (1 << lb)) ++lb;
        for(int i = 0; i < m; ++i) {
            dp[S | (1 << lb)] = min(dp[S | (1 << lb)], dp[S] + a[lb][i]);
            dp[S | mask[i][lb]] = min(dp[S | mask[i][lb]], dp[S] + cost[i][lb]);
        }
    }

    cout << dp.back() << endl;
}

感想

普通にやろうとすると O(3^n) が出てきてしまってつらくなる．
ちょっと工夫して考える遷移を減らす，みたいなのは bitDP だと結構見る．
例えば O(n^2 2^n) -> O(n2^n) とか，O(3^n) -> O(n^2 2^n) とか．
こないだの ARC でも見たような……．

2018-07-29

VK Cup 2015 - Round 3 F. Quest

Codeforces 競プロ

問題文

http://codeforces.com/contest/542/problem/F

解法

DPで解ける．
dp[i][j] := 高さ i に存在するノードが j 個であるようなときの，価値の最大値
とする．
ある高さ i のときに考えるべきタスクは，実はコストが T - i であるものだけでよい．
なぜならば，コスト i のタスクが仮に高さ T - i 以外のところにある場合，そのまま伸ばして高さ T - i のところまで持ってこれるし，そうしたほうが余裕が生まれるので伸ばさない理由がないためである．
遷移だが，仮に今の高さに j 個のノードがすでにあり，そこに k 個のタスクを追加することを考えると，一つ上の高さには最低限 (j + k + 1) / 2 個のノードが必要である．
また，このノードはタスクが置けないノードなので，できるだけ小さい方が良い．したがって，ちょうど (j + k + 1) / 2 個が最適である．故に遷移は
dp[i - 1][(j + k + 1) / 2] = max(dp[i - 1][(j + k + 1) / 2], dp[i][j] + sum[k])
となる．ただし sum[k] はその高さに対応するタスクのなかで価値が大きい方から k 個取ったときの総和である．
計算量は O(Tn^2) となる．

制約的にこれで十分だが，この問題は実は O(T + nlogn) で解ける．
高さ i で2つのタスク q1, q2 を使ったとすると，これはある意味高さ i - 1 で (q1 + q2) のタスクを使ったことと同じになることに注目する．
こうすることで，各高さではすべてのノードが葉であるとみなして解くことができる．
1つ上の高さにタスクを伝搬させる場合は，大きい方から2つずつ取っていって，それらの和を新たなタスクとすればよい（明らかにこれが最適）．
2個ずつ取っていくので log のオーダーで個数が小さくなり，この部分は O(nlogn) ，各高さで見ていくから O(T) で合わせて O(nlogn + T) となる．

ソースコード1

O(Tn^2) のほう．

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

int main() {
    int n, T;
    cin >> n >> T;
    vector<int> t(n), q(n);
    vector<vector<int>> vs(T);
    for(int i = 0; i < n; ++i) {
        cin >> t[i] >> q[i];
        vs[T - t[i]].push_back(q[i]);
    }

    vector<vector<int>> dp(T, vector<int>(n + 1));
    if(!vs[0].empty()) {
        dp[0][1] = *max_element(begin(vs[0]), end(vs[0]));
    }
    for(int i = T - 1; i >= 1; --i) {
        sort(rbegin(vs[i]), rend(vs[i]));
        const int m = vs[i].size();
        vector<int> sum(m + 1);
        for(int j = 0; j < m; ++j) {
            sum[j + 1] = sum[j] + vs[i][j];
        }
        for(int j = 0; j <= n; ++j) {
            for(int k = 0; k <= m; ++k) {
                if((j + k + 1) / 2 > n) continue;
                dp[i - 1][(j + k + 1) / 2] = max(dp[i - 1][(j + k + 1) / 2], dp[i][j] + sum[k]);
            }
        }
    }

    cout << dp[0][1] << endl;
}

ソースコード2

O(T + nlogn) のほう．

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

int main() {
    int n, T;
    cin >> n >> T;
    vector<vector<int>> ts(T);
    for(int i = 0; i < n; ++i) {
        int t, q;
        cin >> t >> q;
        ts[T - t].push_back(q);
    }

    for(int i = T - 1; i >= 1; --i) {
        if(ts[i].size() % 2 == 1) {
            ts[i].push_back(0);
        }
        sort(begin(ts[i]), end(ts[i]));
        const int m = ts[i].size();
        for(int j = 0; j < m / 2; ++j) {
            ts[i - 1].push_back(ts[i][2 * j] + ts[i][2 * j + 1]);
        }
    }

    cout << *max_element(begin(ts[0]), end(ts[0])) << endl;
}

感想

各ノードは葉であるか，必ず2つの子を持つ必要がある，と考えていてハマった（子は別に1つでいい）．

2018-07-07

ACM-ICPC 2018 国内予選参加記

ICPC 競プロ参加記

はじめに

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位で予選通過できなかった同期のチームがあるのはかなり残念ですね…（東大勢はもっと激しいと考えると恐ろしいな…

謝辞

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