Yukicoder No.495 (^^*) Easy

,

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

perl $30$byteを提出。

print~~s/\*\)//g,$",y/*//for<>

左向き*)を数えつつ除去し、残る*を数えれば右向きの数になる。 s///gはlistを返すので~~は整数化、y///は整数を返すのでそのまま。

鑑賞

tailsさんがperl $29$byteを出してた: http://yukicoder.me/submissions/159554

... for ~ <>として各文字反転させることで\によるescapingを不要にしている。


Yukicoder No.494 yukicoder

,

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

implementation

perl $32$byteを提出。

$ cat a.pl | sed -f<(echo 's/\0/\\\\0/')
print'?'^(<>^yukicoder)=~s/\0//gr

各文字でxorしてnull byteを除去して引き戻すだけ。

鑑賞

私のそれからさらに改善があって、

最終的にはruby $16$byteになっていた: http://yukicoder.me/submissions/159654

これは以下のような性質を用いるもの。

>>> chr(sum(map(ord, 'yukicoder')) - sum(map(ord, 'yuki?oder')) + ord('?'))
'c'

「みんなのプロコン」本選: 参加記

,

http://linotice.tumblr.com/post/157643101269/20170224

問題

A問題

典型やるだけ。しかし競プロに慣れてない人には十分難しいやつ。

B問題

これも(予選を通るような人には)すぐ。

C問題

$O(QN)$しようとしたが定数倍高速化力が足りず通せなかった。 $O(Q \log N)$だがunordered_mapの遅い$O(1)$のせいでTLEしてた人も多く見かけた。

無理矢理にでも通すべく色々頑張っていたので、後から「けっこう変な提出してましたよね」みたいな話になったりした。

TopCoder SRM 711 Div1 Easy

懇親会終了後すぐにするめがあったので、Yahooさんのところのコワーキングスペースを使わせてもらって参加した。 $10$人ぐらい参加していた。意外と少ない。registrationが間に合わずで出れずの人もいた。

早解き。

TopCoder SRM 711 Div1 Medium

早解き。

メモ化忘れによる計算量上昇や定数倍らしき何かで落としている人もいた。

TopCoder SRM 711 Div1 Hard

方針は分かったがまったく間に合わず。 今回はそういう回だったらしい。

  • $30$位だった。精進が足りない
  • Yahoo JAPANの名は(ICPCもだけど)セキュリティキャンプやSECCONのスポンサーのイメージだったが、認識が更新された
  • となりでGoコンがなされていた
  • 「みんなの」とは言うが、やはりどうしても予選通過はいつもの人々という感があった
  • けっこう楽しかった。ありがとうございました

TopCoder SRM 711 Div1 Easy: OrderedProduct

,

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

Div1 $40$位を取ってレート爆上げした。嬉しい。

problem

巨大な整数$X$が素因数分解された形で与えられる。$1$を含まない整数列で総乗が$X$になるものの数を答えよ。

solution

長さを固定してそれぞれ計算する。包除原理を陽あるいは陰に使う。$\max a_i \le N$としてまとめて書いて$O(N^4 \log N)$。適切にやれば$O(N^3)$。

列の長さを$l$として、係数$a_i$らを総乗が$X$になるように分配することを考える。 $1$を要素として含むことを許容すれば$k = \prod_i {}_lH_{a_i}$個の異なる列が作れる。ただし${}_nH_r$は重複組み合わせ。 $1$を要素として含むことは禁止されているので$\mathrm{dp}_l = k - \sum_{i \lt l} \mathrm{dp}_i$とする。

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 OrderedProduct { public: int count(vector<int> a); };

constexpr int mod = 1e9+7;
int powmod(int x, int y) { // O(log 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) { // p must be a prime, O(log p)
    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(\log n)
    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 multichoose(int n, int r) {
    if (n == 0 and r == 0) return 1;
    return choose(n+r-1, r);
}

int OrderedProduct::count(vector<int> a) {
    int n = a.size();
    int sum_a = accumulate(a.begin(), a.end(), 0);
    vector<int> dp(sum_a+1);
    repeat (l,sum_a+1) {
        ll cnt = 1;
        repeat (i,n) {
            cnt = cnt * multichoose(l, a[i]) % mod;
        }
        repeat (l1,l) {
            cnt += - dp[l1] *(ll) choose(l, l1) % mod + mod;
        }
        dp[l] = cnt % mod;
    }
    return accumulate(dp.begin(), dp.end(), 0ll) % mod;
}

TopCoder SRM 711 Div1 Easy: ConsecutiveOnes

,

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

problem

整数$N, K$が与えられる。$N \le M$かつ$2$進数展開すると全て$1$な連続する$K$ bitがある、を満たす最小の整数$M$を答えよ。

solution

貪欲。$O((k + \log n)^2)$ぐらい。

とりあえず全てのbitを立てて(あるいは下位$k$ bitを立てて)、大きい側から貪欲に倒していけばよい。

implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
class ConsecutiveOnes { public: ll get(ll n, int k); };

ll ConsecutiveOnes::get(ll n, int k) {
    ll mask = 0; repeat (i,k) mask = (mask << 1) | 1;
    auto pred = [&](ll m) {
        for (ll s = mask; s > 0; s <<= 1) {
            if ((m & s) == s) {
                return true;
            }
        }
        return false;
    };
    ll m = n | mask;
    for (ll i = 1ll << 52; i; i >>= 1) {
        ll nm = m & (~ i);
        if (n <= nm and pred(nm)) {
            m = nm;
        }
    }
    return m;
}

AtCoder Beginner Contest 057: A - Remaining Time

,

http://abc057.contest.atcoder.jp/tasks/abc057_a

awk $15$byteを提出した。

$0=($1+$2)%24""

反省

hanada3355さんのそれが暫定最短(http://abc057.contest.atcoder.jp/submissions/1180872)であった。

私の提出の""aで置き換えたもの。 真偽値として真にするため、整数0に空文字列""を文字列連結して文字列"0"にしているのだが、未使用の変数aも空文字列として評価されるためこれを使っているようだ。

頻出テクだろうし一度は見ているはずだが、まったく記憶になかった。


「みんなのプロコン」本選: C - 倍数クエリ

,

http://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_c

SIMDを意識しすぎてreadとcache missを増やしすぎてTLEし続けていた。精進が足りない。

solution

愚直。$O(QN)$。

SIMDを意識しつつ適切に書けば通る。

implementation

http://yahoo-procon2017-final-open.contest.atcoder.jp/submissions/1180256

#include <cstdio>
#include <cstdint>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
constexpr int max_n = 100000;
int32_t a[max_n];
int main() {
    int n, m, q; scanf("%d%d%d", &n, &m, &q);
    repeat (i,n) {
        scanf("%d", &a[i]);
        a[i] %= m;
    }
    while (q --) {
        int l, r, d; scanf("%d%d%d", &l, &r, &d); -- l; d %= m;
        int cnt = 0;
        for (int i = l; i < r; ++ i) {
            a[i] += d;
            if (a[i] >= m) a[i] -= m;
            cnt += not a[i];
        }
        printf("%d\n", cnt);
    }
    return 0;
}

「みんなのプロコン」本選: B - チーム決め

,

http://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_b

solution

二分探索。上限が固定されれば貪欲。$X = \max \{ \max a_i, \max b_j \}$として $O((N + M) \log X)$。

答え$\mathrm{ans}$が$\mathrm{ans} \le \mathrm{limit}$であるかの述語$\phi(\mathrm{limit})$を計算する。 $a, b$をsortし、$i$をひとつずつ増やしながら、$|a_i - b_j|$でまだ使われていない最小の$j$を(存在すれば)対応させていく。これは$O(N + M)$なので間に合う。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#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;
const int inf = 1e9+7;
int main() {
    int n; scanf("%d", &n);
    int m; scanf("%d", &m);
    int k; scanf("%d", &k);
    vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);
    vector<int> b(m); repeat (i,m) scanf("%d", &b[i]);
    whole(sort, a);
    whole(sort, b);
    auto pred = [&](int limit) {
        int cnt = 0;
        for (int i = 0, j = 0; i < n and j < m; ++ i) {
            while (j < m and b[j] < a[i] - limit) ++ j;
            if (j < m and abs(a[i] - b[j]) <= limit) {
                ++ j;
                ++ cnt;
            }
        }
        return k <= cnt;
    };
    int l = -1, r = inf;
    while (r - l > 1) {
        int m = (r + l) / 2;
        (pred(m) ? r : l) = m;
    }
    printf("%d\n", r);
    return 0;
}

「みんなのプロコン」本選: A - YahooYahooYahoo

,

http://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_a

solution

DP。$O(N)$。

編集距離を求めるのだが編集先を複数から選べる。 yahooを作ればよいのでそのどこまで埋めたかを引数に持って、$\mathrm{dp} : (N+1) \times \{ \mathrm{y}, \mathrm{ya}, \mathrm{yah}, \mathrm{yaho}, \mathrm{yahoo} \} \to \mathbb{N}$みたいにすればよい。

更新の際には注意があって、yahoo上を動くloopは$2$周ぐらい必要。挿入後に元の文字列の文字を使ってまた挿入するパターンがあるため。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
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 inf = 1e9+7;
int main() {
    string s; cin >> s;
    int n = s.length();
    auto dp = vectors(5, n+1, inf);
    dp[0][0] = 0;
    repeat (i,n) {
        repeat (j,11) {
            if ((s[i] == 'y' and j%5 == 0)
                    or (s[i] == 'a' and j%5 == 1)
                    or (s[i] == 'h' and j%5 == 2)
                    or (s[i] == 'o' and (j%5 == 3 or j%5 == 4))) {
                setmin(dp[(j+1)%5][i+1], dp[j%5][i]);
            }
            setmin(dp[(j+1)%5][i+1], dp[j%5][i] + 1); // replace
            setmin(dp[j%5][i+1],     dp[j%5][i] + 1); // delete
            setmin(dp[(j+1)%5][i+1], dp[j%5][i+1] + 1); // insert
        }
    }
    cout << dp[0][n] << endl;
    return 0;
}

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