Codeforces Round #316 (Div.2) E. Pig and Palindromes

問題文

http://codeforces.com/contest/570/problem/E

解法

前と後ろの状態を同時に持たないことにはどうしようもなさそうだが、愚直に持つとオーダーが悪い。
よく考えると、現状態から i ステップ後の位置は、列か行の位置のどちらか一方を持てばもう一方も計算できる。
よって、結局先頭が何列目にいる、後ろが何列目にいるかで、DPテーブルとしては n * n の状態を持っておけば十分。

何ステップ後まで見るかだが、これは 2 * (i + 1) <= n + m - 2 となるまで遷移をくり返していけばいい（これは、互いがちょうど交わるか、交わらないギリギリのタイミングである）。

遷移するときは、遷移先が同じ文字であること、遷移した後の座標がもう一方を超えてしまって矛盾しないようにすることに注意する。

結局、計算量は O(n^3)、空間計算量は O(n^2) でできた。

ソースコード

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

constexpr int mod = 1e9 + 7;

int main() {
    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>(n));
    constexpr int dx1[2] = {0, 1}, dy1[2] = {1, 0};
    constexpr int dx2[2] = {0, -1}, dy2[2] = {-1, 0};
    auto in_range = [n, m] (int y, int x) {
        return 0 <= y && y < n && 0 <= x && x < m;
    };
    dp[0][n - 1] = v[0][0] == v[n - 1][m - 1];
    for(int i = 0; 2 * (i + 1) <= n + m - 2; ++i) {
        vector<vector<int>> nxt(n, vector<int>(n));
        for(int y1 = 0; y1 < n; ++y1) {
            for(int y2 = 0; y2 < n; ++y2) {
                const int x1 = i - y1, x2 = n + m - 2 - i - y2;
                if(!in_range(y1, x1) || !in_range(y2, x2)) continue;
                for(int d1 = 0; d1 < 2; ++d1) {
                    for(int d2 = 0; d2 < 2; ++d2) {
                        const int ny1 = y1 + dy1[d1], nx1 = x1 + dx1[d1];
                        const int ny2 = y2 + dy2[d2], nx2 = x2 + dx2[d2];
                        if(!in_range(ny1, nx1) || !in_range(ny2, nx2) || v[ny1][nx1] != v[ny2][nx2]) continue;
                        if(ny1 > ny2 || nx1 > nx2) continue;
                        (nxt[ny1][ny2] += dp[y1][y2]) %= mod;
                    }
                }
            }
        }
        dp = move(nxt);
    }
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            (ans += dp[i][j]) %= mod;
        }
    }

    cout << ans << endl;
}

感想

適当に書いたら一発で通ってビビった。
一方の情報からもう一方がわかるという性質からオーダーを落とす典型テクですね。

Codeforces Round #316 (Div.2) D. Tree Requests

問題文

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

解法

部分木の特定の高さのノードだけ取り出すのもオイラーツアーでできる。
この場合は高さごとにノードを管理すればよい。
各ノードが持つ区間は普通のオイラーツアーと同じで、各高さごとに持つデータは (今の index、文字を表す bit の xor sum) とする。
文字を表すビットとは、文字 c に対して 1 << (c - 'a') のことをいう。
どうしてこんなことをするかというと、今回制約が厳しいので 26 * m * log が間に合わないからである（log は区間の左端と右端を検索するのにどうしても必要）。
文字の状態を 32bit int で管理しておけば 26 が落とせるので嬉しい。
オイラーツアーのDFSで、頂点 v に到達したら data[height[v]] に ( l[v], data[height[v]].back() ^ (1 << (s[v] - 'a')) ) を追加する。xor の累積和。
各クエリに対しては、その区間の xor sum の popcount が 2 以上であれば回分にできないし、それ未満であれば回分にできる。

bit で26文字を圧縮して O(m * (log + 26)) で解けた。

ソースコード

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

using pii = pair<int, int>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i = 1; i < n; ++i) {
        int p; cin >> p;
        g[p - 1].push_back(i);
    }
    string s; cin >> s;
    vector<int> bit(26);
    for(int i = 0; i < 26; ++i) {
        bit[i] = 1 << i;
    }

    vector<vector<pii>> hs(1 << 20, vector<pii>(1, make_pair(0, 0)));
    vector<int> l(n), r(n);
    {
        int cur = 1;
        function<void(int, int)> euler_tour = [&] (int v, int d) {
            l[v] = cur;
            hs[d].emplace_back(cur, hs[d].back().second ^ bit[s[v] - 'a']);
            for(auto to : g[v]) {
                euler_tour(to, d + 1);
            }
            r[v] = ++cur;
        };
        euler_tour(0, 1);
    }

    for(int i = 0; i < m; ++i) {
        int v, h; cin >> v >> h;
        v--;
        const auto lb = lower_bound(begin(hs[h]), end(hs[h]), make_pair(l[v], -1)) - begin(hs[h]) - 1;
        const auto ub = lower_bound(begin(hs[h]), end(hs[h]), make_pair(r[v], -1)) - begin(hs[h]) - 1;
        const auto t = hs[h][ub].second ^ hs[h][lb].second;
        cout << ((t - (t & -t)) == 0 ? "Yes" : "No") << endl;
    }
}

感想

26 を最初落とさなくてTLEしてしまった。
定番テクなのにすぐに思いつけなかったので反省。

AOJ 1383 Pizza Delivery

問題文

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

解法

始点および終点からの最短路を求めておく。それぞれ from_s, from_t とする。

次に s-t 最短路グラフを作る。このとき、グラフには s から t へ行くのに必要になるかもしれない辺のみを追加する（ここがサンプルにないので意外とハマりがち）。必要になりうる辺は、from_s[e.from] + e.cost + from_t[e.to] == from_s[t] となるような辺 e であるから、判定自体は簡単。

ある辺 e について、from_s[e.to] + e.cost + from_t[e.from] <= from_s[t] なら HAPPY か SOSO で、ここはそのまま出力して良い。
そうでないときに、最短路コストが増大するかどうかは、e が最短路グラフで橋になっているかどうかで判定できる。橋なら SAD でそうでなければ SOSO と出力すれば良い。（余計な辺が入っていると、この橋検出で本当は橋と判定すべきところを橋でないと判定してしまうのに注意。）

ソースコード

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

using ll = long long;

constexpr ll inf = 1e18;

struct edge {
    int from, to;
    ll cost;
};

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

void add_edge(graph& g, int from, int to, ll cost) {
    g[from].push_back(edge{from, to, cost});
}

class lowlink { // multiple edges ok
public:
    lowlink(graph const& g)
        : ord(g.size()), low(g.size())
    {
        const int n = g.size();
        std::vector<bool> visited(n);
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            if(!visited[i]) {
                dfs(g, i, -1, cnt, visited);
            }
        }
    }

    std::vector<int> get_articulation_points() const { return articulation_points; }
    std::vector<edge> get_bridges() const            { return bridges; }

    bool is_bridge(int u, int v) const {
        if(ord[u] > ord[v]) std::swap(u, v);
        return ord[u] < low[v];
    }

private:
    void dfs(graph const& g, int v, int prev, int& cnt, std::vector<bool>& visited) {
        visited[v] = true;
        low[v] = ord[v] = cnt++;
        bool is_articulation = false;
        int cnt2 = 0, pcnt = 0;

        for(auto& e : g[v]) {
            if((e.to != prev || (e.to == prev && pcnt == 1)) && visited[e.to]) {
                low[v] = min(low[v], ord[e.to]);
            } else if(!visited[e.to]) {
                cnt2++;
                dfs(g, e.to, v, cnt, visited);
                low[v] = min(low[v], low[e.to]);
                if(prev != -1 && ord[v] <= low[e.to]) {
                    is_articulation = true;
                }
                if(is_bridge(v, e.to)) {
                    bridges.push_back(edge{min(v, e.to), max(v, e.to), e.cost});
                }
            }
            pcnt += e.to == prev;
        }
        is_articulation |= (prev == -1 && cnt2 > 1);
        if(is_articulation) articulation_points.push_back(v);
    }

private:
    std::vector<int> articulation_points;
    std::vector<edge> bridges;
    std::vector<int> ord, low;
};

vector<ll> djikstra(graph const& g, int s) {
    const int n = g.size();
    vector<ll> d(n, inf);
    d[s] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que;
    que.emplace(0, s);
    while(!que.empty()) {
        auto now = que.top(); que.pop();
        const int v = now.second;
        if(d[v] < now.first) continue;
        for(auto& e : g[v]) {
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.emplace(d[e.to], e.to);
            }
        }
    }
    return d;
}

int main() {
    int n, m; cin >> n >> m;
    const int s = 0, t = 1;
    edges es;
    graph g(n), rg(n);
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        es.push_back(edge{a - 1, b - 1, c});
        add_edge(g, a - 1, b - 1, c);
        add_edge(rg, b - 1, a - 1, c);
    }
    auto from_s = djikstra(g, s), from_t = djikstra(rg, t);
    const ll dist = from_s[t];
    graph sg(n);
    for(auto& e : es) {
        if(from_s[e.from] + e.cost + from_t[e.to] == dist) {
            add_edge(sg, e.from, e.to, e.cost);
            add_edge(sg, e.to, e.from, e.cost);
        }
    }
    lowlink helper(sg);
    for(auto& e : es) {
        if(from_s[e.to] + from_t[e.from] + e.cost <= dist) {
            if(from_s[e.to] + from_t[e.from] + e.cost < dist) {
                cout << "HAPPY" << endl;
            } else {
                cout << "SOSO" << endl;
            }
        } else if(from_s[e.from] + from_t[e.to] + e.cost == dist && helper.is_bridge(e.from, e.to)) {
            cout << "SAD" << endl;
        } else {
            cout << "SOSO" << endl;
        }
    }
}

感想

本番で誤読して解くのが不可能な問題になっていたのを今でも覚えている…。

Codeforces Round #310 (Div.1) E - Case of Computer Network

問題文

http://codeforces.com/contest/555/problem/E

解法

二重辺連結成分分解をしてくださいと書いてあるので、先にやっておく。
ただし、与えられるグラフは単純グラフとは限らないので、多重辺にも対応しておく。
するとグラフは森になるので、結局木の上で元の問題が解ければ良い。

ある辺について、どちらに向き付すべきかを考えよう。
（各）木について適当に根を決めて、根付き木にする。
ある頂点 v と、その親に伸びている辺について、その部分木に含まれる s[i] の数、d[i] の数、s[i] と d[i] の LCA の数をそれぞれ a, b, c とする（s[i], d[i], LCA の値として同じものがあっても、それらは何度も数える）。
すると、今注目している辺は、a - c が正のとき、上に伸びていなければならないし、逆に b - c が正のとき、下に伸びていなければならない。
これは、v の部分木内で完結している s[i], d[i] のペアの数が部分木に含まれる LCA の数に対応していることを考えれば容易にわかる。
これらがともに正となるとき、与えられた条件を満たす向きづけは存在しない。それ以外のときは、向き付が存在する。

ソースコード

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

struct edge {
    int from, to;
};

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

void add_edge(graph& g, int from, int to) {
    g[from].push_back(edge{from, to});
    g[to].push_back(edge{to, from});
}

class lowlink {
public:
    lowlink(graph const& g)
        : ord(g.size()), low(g.size())
    {
        const int n = g.size();
        std::vector<bool> visited(n);
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            if(!visited[i]) {
                dfs(g, i, -1, cnt, visited);
            }
        }
    }

    std::vector<edge> get_bridges() const            { return bridges; }

    bool is_bridge(int u, int v) const {
        assert(0 <= u && u < (int)ord.size() && 0 <= v && v < (int)ord.size());
        if(ord[u] > ord[v]) std::swap(u, v);
        return ord[u] < low[v];
    }

private:
    void dfs(graph const& g, int v, int prev, int& cnt, std::vector<bool>& visited) {
        visited[v] = true;
        low[v] = ord[v] = cnt++;
        int cnt2 = 0, pcnt = 0;

        for(auto& e : g[v]) {
            if((e.to != prev || (e.to == prev && pcnt == 1)) && visited[e.to]) {
                low[v] = min(low[v], ord[e.to]);
            } else if(!visited[e.to]) {
                cnt2++;
                dfs(g, e.to, v, cnt, visited);
                low[v] = min(low[v], low[e.to]);
                if(is_bridge(v, e.to)) {
                    bridges.push_back(edge{min(v, e.to), max(v, e.to)});
                }
            }
            pcnt += e.to == prev;
        }
    }

private:
    std::vector<edge> bridges;
    std::vector<int> ord, low;
};

// require: lowlink
class biconnected_component {
public:
    biconnected_component(graph const& g_)
        : g(g_), helper(g_), belongs_(g_.size(), -1)
    {
        for(auto&& b : helper.get_bridges()) {
            add_component(b.from), add_component(b.to);
        }
        add_component(0);
    }

    graph build() { // if not connected, result is forest
        graph res(cmps.size());
        auto bridges = helper.get_bridges();
        for(auto& b : bridges) {
            add_edge(res, belongs(b.from), belongs(b.to));
        }
        return res;
    }

    int belongs(int u) const { assert(0 <= u && u < (int)belongs_.size()); return belongs_[u]; }

private:
    void fill_component(int c, int u) {
        cmps[c].emplace_back(u);
        belongs_[u] = c;
        for(auto& e : g[u]) {
            if(belongs_[e.to] >= 0 || helper.is_bridge(u, e.to)) continue;
            fill_component(c, e.to);
        }
    }
    void add_component(int u) {
        if(belongs_[u] >= 0) return;
        cmps.emplace_back();
        assert(cmps.size() >= 1u);
        fill_component(cmps.size() - 1, u);
    }

private:
    graph g;
    lowlink helper;
    std::vector<int> belongs_;
    std::vector<std::vector<int>> cmps;
};

class lowest_common_ancestor {
public:
    lowest_common_ancestor(graph const& g/* int root*/)
        : n(g.size()), log_n(std::ceil(std::log2(g.size())) + 1),
          parent(log_n, std::vector<int>(n, -1)), depth_(n)
    {
        for(int i = 0; i < n; ++i) {
            if(parent[0][i] == -1) dfs(g, i, -1, 0);
        }
        for(int k = 0; k + 1 < log_n; ++k) {
            for(int v = 0; v < n; ++v) {
                if(parent[k][v] < 0) parent[k + 1][v] = -1;
                else                 parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }

    int query(int u, int v) const {
        if(depth_[u] > depth_[v]) {
            std::swap(u, v);
        }
        for(int k = 0; k < log_n; ++k) {
            if((depth_[v] - depth_[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if(u == v) {
            return u;
        }
        for(int k = log_n - 1; k >= 0; --k) {
            if(parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

private:
    void dfs(graph const& g, int v, int p, int d) {
        parent[0][v] = p;
        depth_[v] = d;
        for(auto& e : g[v]) {
            if(e.to != p) {
                dfs(g, e.to, v, d + 1);
            }
        }
    }

private:
    int const n, log_n;
    std::vector<std::vector<int>> parent;
    std::vector<int> depth_;
};

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, q;
    cin >> n >> m >> q;
    graph g(n);
    for(int i = 0; i < m; ++i) {
        int v, u; cin >> v >> u;
        add_edge(g, v - 1, u - 1);
    }
    vector<int> s(q), d(q);
    for(int i = 0; i < q; ++i) {
        cin >> s[i] >> d[i];
        s[i]--, d[i]--;
    }

    biconnected_component bicc(g);
    auto t = bicc.build();
    const int tn = t.size();
    lowest_common_ancestor lca(t);
    union_find uf(tn);
    for(auto& es : t) {
        for(auto& e : es) {
            uf.unite(e.from, e.to);
        }
    }
    vector<int> sum1(tn), sum2(tn), sum3(tn);
    for(int i = 0; i < q; ++i) {
        s[i] = bicc.belongs(s[i]), d[i] = bicc.belongs(d[i]);
        if(!uf.same(s[i], d[i])) {
            cout << "No" << endl;
            return 0;
        }
        sum1[s[i]] += 1, sum2[d[i]] += 1;
        sum3[lca.query(s[i], d[i])] += 1;
    }
    vector<bool> visited(tn);
    function<bool(int, int)> dfs = [&] (int v, int p) {
        bool res = true;
        visited[v] = true;
        for(auto& e : t[v]) {
            if(e.to == p) continue;
            res &= dfs(e.to, v);
            sum1[v] += sum1[e.to], sum2[v] += sum2[e.to], sum3[v] += sum3[e.to];
        }
        return res & (sum1[v] - sum3[v] <= 0 || sum2[v] - sum3[v] <= 0);
    };
    bool ans = true;
    for(int i = 0; i < tn; ++i) {
        if(visited[uf.root(i)]) continue;
        ans &= dfs(uf.root(i), -1);
    }
    cout << (ans ? "Yes" : "No") << endl;
}

感想

単純グラフじゃないのはいいとして、連結である保証すら無いのでいじわるだなあと思った（本質じゃないんだから手を抜いてくれても良いんじゃないかなあ）。
ライブラリがないと実装するの大変そう。ICPCだったら最悪。

後で気がついたけど、テストケースがダメダメっぽい。部分木の総和を求め忘れてても通ってしまっていた。

Codeforces Round #309 (Div.1) D. Nudist Beach

問題文

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

解法

二分探索して BFS で解ける。
最大化したい値を例えば仮に x とおく。
最初、使える集合 S には k 頂点以外のすべての頂点を入れておく。
queue には使えなくなった頂点（初期は k 頂点）を入れる。
(隣接頂点のうち S に含まれる個数) / (次数) が x 未満となる頂点は、その後どうあがいても使えない。
したがって、queue から使えなくなった頂点を取り出して隣接頂点の次数を1つ下げ、この時 x 未満になったら、queue に追加する、ということを繰り返すだけで解ける。
まだ使える頂点が残っていればそれが答え S の候補である。

実装によるが、コーナーケースとして x の最大値が 0 の場合がある。
答えの集合が 0 なら k 個以外の頂点を全部入れるか、二分探索の下界を負の値にしておくとよい。
計算量は O(nlogm)

ソースコード

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

int main() {
    int n, m, k; cin >> n >> m >> k;
    vector<bool> used(n);
    for(int i = 0; i < k; ++i) {
        int v; cin >> v;
        used[v - 1] = true;
    }

    vector<vector<int>> g(n);
    vector<int> deg(n);
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
        deg[a - 1]++, deg[b - 1]++;
    }

    auto check = [&] (double x) mutable {
        queue<int> que;
        auto cur = deg;
        auto erased = used;
        for(int i = 0; i < n; ++i) {
            if(erased[i]) que.push(i);
        }
        while(!que.empty()) {
            const int v = que.front(); que.pop();
            for(auto adj : g[v]) {
                if(erased[adj]) continue;
                if(--cur[adj] < x * deg[adj]) {
                    erased[adj] = true;
                    que.push(adj);
                }
            }
        }
        vector<int> res;
        for(int i = 0; i < n; ++i) {
            if(!erased[i]) res.push_back(i + 1);
        }
        return res;
    };

    vector<int> ans;
    double lb = -1, ub = 2e5;
    for(int lp = 0; lp < 60; ++lp) {
        const auto mid = (lb + ub) / 2;
        auto tans = check(mid);
        if(tans.empty()) {
            ub = mid;
        } else {
            lb = mid;
            ans = move(tans);
        }
    }

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

感想

AGC 027 C と考え方が全く同じ。

JAG夏合宿2018 参加記

はじめに

JAG夏合宿2018の参加記です。

今年が初参加だったのですが、結構濃密な3日間だったので参加してよかったです。

3日間とも、ICPCのときのチーム Zerokan_Sunshine (@nakano, @kazuma, @suibaka) で出ました。

Day1

当日会場まで

原宿からオリセンまでが意外と遠く、その上雨が降っていたので大変だった。
代々木公園からオリセンは目の前に見えるのに、通路が見つからなくてめっちゃ迂回したのだけ覚えてる。

コンテスト

台湾の国内予選2017の問題を使っていたらしい。

僕は ABDEF を実装。

各問題の流れを以下に書く（Day1 に関しては書かなくていい気がするけど）。

• A問題
  • 書いてあることを書けば通ります
• B問題
  • 10年以上前のPCKみたいな問題だった。full house を hull house とタイポして1WA。
• C問題
  • 僕は読んでない。kazuma が通してたかも？誤読して難しい問題解いてたとか聞いた気がする。
• D問題
  • 実装ゲー。今見ている位置の前と後ろを 2 つの deque で管理していい感じに実装した。
• E問題
  • 基本的な解法は瞬で、コーナーケースを忘れてて 1WA。これは割とすぐ気づけて（nakano が見つけてくれて）直した。
• F問題
  • 他の問題を解いている間に nakano が実験して式を生成していた。なのでそのまま書いた。実装ミスって1回REしたけどすぐ気づいて修正（サンプルが弱かったので気づかなかった）。
• G問題
  • どう見ても kazuma が得意なので丸投げ。投げたけど通らなかった。残念。
• H問題
  • 解けなかった。パット見どっちにしろ実装大変そうだな～と思って考察もあまりしていなかった。

コンテスト後

生活リズムが崩壊していたところを徹夜で無理やり戻したため、20時ぐらいに睡魔が襲う。

そのまま寝落ちしてAGC寝ぶっち。

同じ部屋の人に聞いたところBが激しかったらしい。でなくてよかったね

Day2

コンテスト

Gifted Infants の3人 （yosupo, sigma, maroon, 敬称略）のセット。ヤバイ問題がちらほらという感じだった。

僕は ACFH の実装を担当。この日は僕が戦犯と化していた。

• A問題
  • 中国剰余定理いきなり出すのかとビビる
  • 冷静に考えると 17 * 107 通りしか無いのでやるだけだった
• B問題
  • 知らないけど気がついたら kazuma が通してた
• C問題
  • 基本方針はすぐ出て書いたけどサンプルが合わねえ
  • よく考えたら約数を列挙した後にさらにそれを分割できることに nakano が気がつく
  • 直して修正。WA。
  • 偶奇の扱いが雑すぎた（というか修正しているうちに間違えて消していた）のが原因だった。直してAC
  • この問題でぐだってるあたりが僕のチームの弱いところ
• D問題
  • 何もわからないから後回しにしていたらコンテストが終わっていた
• E問題
  • 問題読解して kazuma に投げてみる
  • 伝達ミスがあってロスが発生。kazuma ごめん
  • 僕が違う問題やってるうちにいつの間にか FFT に落ちていて AC
  • 1WA 生えてたけど理由は忘れた
• F問題
  • やるだけじゃん（笑）とかいって実装
  • サンプル2が合わない
  • 間違ったコードを埋め込んでサンプルが通ったと勘違い（サンプル 2 が偶然あってしまって、サンプル1 が代わりに落ちていた）
  • 気づかず投げて WA
  • サンプル2をよく眺めると、誤差爆発を狙ってそう
  • 不可能
  • kazuma神「これ mod で有理数いい感じにやるやつでは？ｗ」
  • 当然ライブラリがないので、その場で適当に生成した（実装量がエグいことになった）
  • if の条件節でトートロジー（s == s みたいなの）を間違えて書いてしまい 1WA が生える
  • 直してAC。これ通ったのは割と嬉しい
• G問題
  • 嘘が生えては一瞬で嘘が判明するみたいなのを5分ぐらいやる
  • 無理なので、無理です（は？）
• H問題
  • なぜか kazuma に丸投げされた
  • KMP すればやるだけというのはすぐわかった
  • 何故かサンプルが合わない
  • 最初に文字列を reverse していて（意味不明）、消し忘れていた。合うわけ無いだろアホか？
  • 直して AC
  • reverse に何故か全く気が付かなくて1時間ぐらい溶けた
    • もしかしてKMPじゃなくて Zalgo だったっけ？とか、あまりにも通らないから SA で頑張って書くかとかいろいろ考えてしまった
• I問題
  • ドン引き
  • kazuma が解けないなら無理という感じで撤退
• J問題
  • kazuma と nakano がやってた
  • サンプルは合うけど全然通らなくてつらそうだった
  • 解説を聞いた後にどうだったか聞いたら、普通に考察ができてなかったらしい
• K問題
  • なんか場合分けしたら 2 パターンぐらいになるなあ
  • 小さい部分問題になるケースと、そうでないケースの2パターン
  • そこからすすまないので撤退、多分考えても解けなかったと思う

コンテスト後

この日は opencup もあったので参加。
opencup 終わってから気がついたけど、解いた問題のすべてを僕が実装していた。
流石に今日は実装しすぎて（一日10時間もコンテストやってるの異常では？）疲れたので、布団に入ったらすぐ寝てしまった。

Day3

今日は JAG の問題セット。典型が多くて僕は楽しめた。

僕は ACGJ の実装を担当。通らなかったけど E とかも書いてた。

• A問題
  • よくわからないけど投げたら通った。こういうのが一番怖い
• B問題
  • kazuma 誤読。WA が来て nakano に誤読を指摘されていた
  • 難なくAC
• C問題
  • nakano に概要聞くとやるだけだった
  • AC
• D問題
  • 最初あんまり誰も考えてなかったので僕がちょっと考える
  • kazuma のほうが得意そうだなあ
  • Trie でいい感じにやっても解けそう、実装は気をつけないと文字列長がでかいのでメモリが危ない？
  • どっちにしろ僕が書くより kazuma が書いたほうがパフォーマンス高そう
  • kazuma に投げると普通に二分探索して2つの範囲求めてやればよくない？となる
  • それはそう
  • 選択肢はいろいろ (Wavelet Matrix でもいいけど写経がめんどくさい）あったけど Merge Segment Tree で通していた
• E問題
  • やるだけやんけ（笑）となり書く
  • T L E
  • Day2 の再来か？となるが冷静に考えると普通に O(N^2) ですありがとうとなる
  • ベクトル（直線）に分けて Convex Hull Trick みたいにやるんじゃないの、という話を適当にする
  • なんかこのタイミングでは反応がいまいちだった（というか、どっちにしろ実装が非常に重い）ので保留
    • 終わり際に CHT の話をしたらそれで解けるじゃん、みたいな空気に。結果的には取り組まなくても良かったけど、ちょっと危ないムーブだった気がする
  • 定数倍改善を考えるがまあ通らないので諦め
• F問題
  • ゲームだし、僕よりは kazuma か nakano のほうがいいので kazuma になげた
  • kazuma は K を書くことになったので nakano が F を考える
  • めっちゃ実験してたように見える
  • 他のチームに比べかなり遅いけどAC。通ればなんでもええんや
• G問題
  • パット見難しそうなので後回しにした気がする
  • あとになって戻ってくると DP を前からやるだけで解けるねとなる
  • 書くまでもなく実装が面倒、これぞICPCだなあ
  • ややこしいパートを前計算しておいてデバッグしやすいようにした
  • サンプルが合うので投げる、WA
  • 前計算パートがちょっとだけバグってた（先頭を 0 or 1 のどちらにするかの場合分けが甘かった）のを nakano が見つけてくれた
  • 直して AC
  • これもかなり時間がかかっていて、大反省
• H問題
  • どう見ても LP なので双対を取ってから最短経路かフローでしょ
  • 最悪シンプレックス法とか（かける人がいないので棄却）
  • 双対を取ってから詳しい人がいません、終了です
• I問題
  • しらないけど kazuma が通してた
• J問題
  • nakano が読んでいたので教えてもらう
  • 奇数長で行けるなら +2k で素数は作れるからという話を聞く
  • すると遇奇でわけて BFS やるだけなので適当に書いてAC
• K問題
  • kazuma と nakano がやってたから関わってない
  • あとで聞いたら超典型っぽい。通ったときはあまり解かれてなかったので意外だった

おわりに

最近まったく精進してなくて、久々の濃密な競プロ生活だったのでいい刺激になりました。

一つ心残りなのは、他の人と全然交流していないことですかねー。すでに知ってる人 or 相部屋になった人とちょっと喋っただけで終わってしまいました。
チェックアウト時も僕は腹痛でトイレに篭っていたのでお別れの挨拶もしていないし…。

夏合宿自体はかなり楽しかったです。夏合宿を運営してくださった方々には本当にお世話になりました。ありがとうございました。

ひょっとすると来年もお邪魔するかもしれないので、そのときはよろしくお願いします。

Codeforces Round #307 (Div.2) E. GukiZ and GukiZiana

問題文

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

解法

平方分割．まあそれはそうだよね．
実装方法はいろいろありそうだけど，10秒制限が意外と厳しいので，map とか set はできるだけ使わないほうが良い．
各塊は2つ目のクエリに答えるために，(val, idx) のソート済み vector を持つようにする．普通に二分探索で求めれば良い．
というか，実装読んでもらったほうが早い．

ソースコード

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

using ll = long long;

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<ll> a(n);
    for(int i = 0; i < n; ++i) {
        scanf("%lld", &a[i]);
    }
    constexpr int B = 512;
    vector<ll> lazy_add((n + B - 1) / B);
    const int b_sz = lazy_add.size();
    vector<vector<pair<ll, int>>> pos(b_sz);
    for(int i = 0; i < n; ++i) {
        pos[i / B].emplace_back(a[i], i);
    }
    for(auto& v : pos) {
        sort(begin(v), end(v));
    }
    auto get_range = [&] (vector<pair<ll, int>> const& vs, ll val) {
        auto lb = lower_bound(begin(vs), end(vs), make_pair(val, -1));
        if(lb == end(vs) || lb->first != val) return make_pair(n, 0);
        auto ub = lower_bound(begin(vs), end(vs), make_pair(val + 1, -1));
        return make_pair(lb->second, prev(ub)->second);
    };
    while(q--) {
        int com; scanf("%d", &com);
        if(com == 1) {
            int l, r, x;
            scanf("%d %d %d", &l, &r, &x);
            l--;
            for(int b = 0; b < b_sz; ++b) {
                const int l2 = b * B, r2 = min(n, (b + 1) * B);
                if(r <= l2 || r2 <= l) continue;
                if(l <= l2 && r2 <= r) {
                    lazy_add[b] += x;
                } else {
                    pos[b].clear();
                    for(int i = l2; i < r2; ++i) {
                        a[i] += lazy_add[b];
                        if(l <= i && i < r) {
                            a[i] += x;
                        }
                        pos[b].emplace_back(a[i], i);
                    }
                    lazy_add[b] = 0;
                    sort(begin(pos[b]), end(pos[b]));
                }
            }
        } else {
            int y; scanf("%d", &y);
            int l = n, r = 0;
            for(int b = 0; b < b_sz; ++b) {
                auto p = get_range(pos[b], y - lazy_add[b]);
                l = min(l, p.first), r = max(r, p.second);
            }
            printf("%d\n", max(-1, r - l));
        }
    }
}

感想

10sec だし多少の定数倍ならまあ通るやろとか言ってたら普通にTLEして大変だった．
もうちょっと早くするとすれば，クエリ2に対して l, r は一回求まったらもう探す必要がないからループを抜ける，とかですかね．
でも結局最悪ケースは同じなので平均したら若干早くなるかなぐらいの気持ちだけど．
こういうの余裕をもって通せたことがないなあ．

この回 Div.2 Only にしては結構大変な気がする．E はあんまり考察いらないからこんなもんですかね？