学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

WhiteHatCTF2016 WriteUp

WhiteHatCTF2016にチームHarekazeで参加しました。400点分の write up

write up

Bun cha (crypto 100pts)

やるだけ。diffie-hellmanの鍵共有でメッセージをやり取りしていたと書いてあるが、渡される暗号文やら公開鍵やら見てみるとmod取ってない。何も考えずに割ると平文が出てくる。

flag : WhiteHat{sha1(Bun_cha_ca)}

Banh cuon (crypto 200pts)

やるだけ。RSAでやりとりしたと書いてある。pもqも合成数ということが問題。しかし、p1, p2, ..., p5と怪しい数が書かれていて、試してみるとpqの(確率的素数判定で間違ってなければ)素因数はp1, p2, ..., p5, (pq) / (p1*p2*...*p5) の6つであるとわかる。あとはRSAと同じ理屈でeの逆元をmod phi(pq) = (p1 - 1) * (p2 - 1) * ... でとればよい。

flag : WhiteHat{ff94658cf7612e7f68de6d960caf6f9b92e8a4a4}

English version

需要があるようなので英語版の解説もつけときますね．
Sorry for my poor English skill.

Solution is simple.
We should notice the fact p and q are composite number. There are suspicious numbers p1 to p5. In fact, p1 to p5 are divisor of product of p and q. Moreover, p1, p2, …, p5 and (pq)/(p_1 p_2 p_3 p_4 p_5) are prime. Thus, the prime factorization of pq is p_1 p_2 p_3 p_4 p_5 ( (pq) / (p_1 p_2 p_3 p_4 p_5) ) .

So, we could calculate d such as ed \equiv 1 (\mod \phi(pq)) and decipher the cipher text c by calculate c^d (\mod pq).

The flag is WhiteHat{ff94658cf7612e7f68de6d960caf6f9b92e8a4a4}

Banh da Ke (misc 100pts)

やるだけ。対話的なプログラムがサーバの上で走っていて、コマンドを実行してくれる。ただし、catやlessやheadなどのコマンドは受け付けない。0 - 9999 の10000個のディレクトリの中に"乱数.乱数"という名前のファイルがフラグ文字列の長さと同じ数だけ作られ、そのそれぞれにフラグの文字がひとつづつ書き込まれている。なお、ファイルに書き込まれる文字のフラグ文字列中での順序と、フラグの文字が書き込まれたディレクトリの数の順序は一致する。

catが使えなければgrepを使えばいいじゃない。ということで grep -r "." で dirname/filename/:Fの形式の出力が得られる。あとはディレクトリ名をキーにしてソートしてフラグを復元するだけ。

flag : WhiteHat{sha1(WhiteHat{ke3p_c4lm_4nD_try_h4rd})}

WhiteHat{}ごとsha1とらないといけないところが悪質。

感想

自明問しか解けてなくてつらい。

SECCON2016qual 参加記

プログラミング 雑記 CTF

はじめに

SECCON2016予選にチームHarekazeの黒木洋美として参戦していました。

普段は競技プログラミングをしているのですが、ある日hiwwさんからお誘いいただきCTFに参加することになりました。

(現在の記事は速報版です)
2016/12/12 深夜 更新(未完。まあちまちま完成に向けて更新していきます。)
2016/12/15 完成？

結果

個人的0完。延長戦でcrypt200pts Backpacker's Capricious Cipher を解いたので解説(CTF界隈ではWriteUpと言うらしい？)を貼っておきます。コンテスト中は競技の知識に付け焼刃でなんとかなりそうな暗号問に取り組んでました。

Backpacker's Capricious Cipher (crypt 200pts) 解法

解法概要

つらいやるだけ。手計算をがんばる。オイラーフェルマーの小定理を知っていれば小学生でも解ける。

問題概要

暗号化/復号用のソースコードと、公開鍵と暗号文が渡されるので復号してくださいという問題。暗号化のアルゴリズムは部分和問題の難しさを拠り所にしたものでした。後述しますが、この問題の場合はナップザック問題を解くことなく復号できます。

蛇足。同じく部分和問題の難しさを拠り所にした暗号にはナップザック暗号というものがあるらしいです（チームメイトが教えてくれました）。しかし、この問題の暗号はナップザック暗号ではないようです。これは次の理由によります。Wikipediaの解説によればナップザック暗号は超増加数列というものを利用するらしいのですが、ナップザック暗号で用いる素数Pは使用する超増加列の総和よりも大きく選ぶ必要があります。数列の和が最小となるような超増加列は\{1,2,4,8,16,32,...\}と、初項1、公比2の等比数列であり（このことは帰納法で証明できる）、その総和は長さNの超増加列では2^N-1となります。ところがこの問題で与えられるパラメータを見てみると、2^N -1 \gt Pでありナップザック暗号のPの選び方からは外れていることがわかります（ナップザック暗号だという勘違いを防ぐいいヒントですね！）。よって、この問題がナップザック暗号ではなく、別の何かの方法で暗号化されていてこれを復号する必要があるということがわかります。ナップザック暗号だと思って時間を溶かした各位は反省しましょう。

暗号化手法(配布されたコード中での)

私のような脳みそ空っぽ人間にはrubyで書かれた元のコードは難しすぎた。ということで、cipher.rbと等価なコードをpythonで書きました（等価になってるはず？）。python固有の機能はほぼ使ってないし、コメントもたくさんいれたので動作は理解できるはず？

#!/usr/bin/env python3
# -*- coding : utf-8 -*-
import random

def keygen(N, P) :
	k = [] # 鍵の集合(公開鍵)
	K = 0  # kの部分和(公開鍵)
	priv = [] # 和がKとなるようなkの選び方(秘密鍵)
	for i in range(N) :
		# [0,P)の区間から整数を一つランダムに選ぶ
		k.append(random.randint(0,P-1))
	for i in k :
		# 1/2の確立でkからアイテムを選択する
		if random.randint(0,1) :
			K = (K+i) % P
			priv.append(1)
		else :
			priv.append(0)

	return K, k, priv # (公開鍵,公開鍵,秘密鍵)

def encrypt(msg, N, k, K, P) :
	# vec_Aの内容は、[ [-K,[]], [k[0], [0]], [k[1], [1]], ... ]
	vec_A = [[-K,[]]]
	for i, key in enumerate(k) :
		vec_A.append([key,[i]])

	# 暗号化に使用する乱数を事前生成しておく
	R0 = []
	R1 = []
	R2 = []
	for i in range(N) :
		R0.append(random.randint(0,P-1))
		R1.append(random.randint(0,P-1))
		R2.append(random.randint(0,P-1))
	
	# vec_Bの内容は [ [R0[0], [0]], [R1[0], []], [R0[1], [1]], [R1[1], []], ... ]
	vec_B = []
	for i in range(N) :
		vec_B.append([R0[i], [i]])
		vec_B.append([R1[i], []])
	
	# normalize + multiply を含んだ処理。addはvec_Bを生成しているので考えなくてよい
	enc_dic = {tuple([]):msg} # もとのコードのrに相当
	for i in vec_A :
		for j in vec_B :
			# この辺はmultiplyに相当
			mul = (i[0] * j[0]) % P

			# この辺はnormalizeに相当
			vec_key = i[1] + j[1]
			# vec_key[0] <= vec_key[1] を保証
			if len(vec_key) == 2 and vec_key[0] > vec_key[1] :
				# swap
				vec_key[0], vec_key[1] = vec_key[1], vec_key[0]

			# vec_keyをキーとしたハッシュテーブルに値を足しこむ
			if not(tuple(vec_key) in enc_dic) :
				enc_dic[tuple(vec_key)] = 0
			enc_dic[tuple(vec_key)] = (enc_dic[tuple(vec_key)] + mul) % P
	
	for i in range(N) :
		enc_dic[tuple([i])] = (enc_dic[tuple([i])] - R2[i] + P) % P
		enc_dic[tuple([i,i])] = (enc_dic[tuple([i,i])] + R2[i]) % P
	
	# return用にencを成形する。特に意味はない。
	enc = []
	for i in range(N+1) :
		for j in range(i,N+1) :
			vec_key = [i-1,j-1]
			if i == 0 and j == 0 :
				vec_key = []
			elif i == 0 :
				vec_key = [j-1]
			enc.append([enc_dic[tuple(vec_key)], vec_key])
	return enc

def decrypt(enc, p) : #暗号文、秘密鍵
	msg = 0
	for i in enc :
		# i は [num,[a,b]] の形で、[a,b]はencryptのvec_keyに相当するもの
		add_flg = True
		for j in i[1] :
			add_flg = add_flg and p[j]

		# iが[num,[a,b]]であり、k[a]とk[b]がともに公開鍵Kを作るために使われていればnumを加算
		if add_flg :
			msg = (msg + i[0]) % P
	return msg

if __name__ == "__main__" :
	# 試しに暗号化/復号をしてみる
	N = 128
	P = 79228162514264337593543950319
	K, k, priv = keygen(N,P)
	# こいつを暗号化
	msg = 12345678987654321
	enc = encrypt(msg, N, k, K, P)
	msg_ = decrypt(enc, priv)

	print(msg, msg_)

暗号化に用いられているコードを読むと、それと等価なpythonのコード中でvec_Aとvec_Bの乗算が行われていることがわかる。この手のコードを読むには表を書いてしまうのが楽なので表を書くと次のようになる。

vec_A
-K, [ ]k[0], [0]k[1], [1]...k[N-1], [N-1]
vec_BR0[0], [0]-K*R0[0], [0]k[0]*R0[0], [0,0]k[1]*R0[0], [0,1]...k[N-1]*R0[0], [0,N-1]
R1[0], [ ]-K*R1[0], [ ]k[0]*R1[0], [0]k[1]*R1[0], [1]...k[N-1]*R1[0], [N-1]
R0[1], [1]-K*R0[1], [1]k[0]*R0[1], [0,1]k[1]*R0[1], [1,1]...k[N-1]*R0[1], [1,N-1]
R1[1], [ ]-K*R1[1], [ ]k[0]*R1[1], [0]k[1]*R1[1], [1]...k[N-1]*R1[1], [N-1]
..................
R0[N-1], [N-1]-K*R0[N-1], [N-1]k[0]*R0[N-1], [0,N-1]k[1]*R0[N-1], [1,N-1]...k[N-1]*R0[N-1], [N-1,N-1]
R1[N-1], [ ]-K*R1[N-1], [ ]k[0]*R1[N-1], [0]
k[1]*R1[N-1], [1]
...k[N-1]*R1[N-1], [N-1]

この表の内容の要素を足しあげて暗号化を行っているので、表の要素の和をキーとなるリストの要素ごとに取ると、

[] : -K*sum(R1)
[i] : -K*R0[i] + k[i]*sum(R1)
[i,i] : R0[i]*k[i]
[i,j] : R0[i]*k[j] + R0[j]*k[i] (i < j)

となる。さらに平文・乱数が足しこまれ、最終的には

[] : msg - K*sum(R1)
[i] : -K*R0[i] + k[i]*sum(R1) - R2[i]
[i,i] : R0[i]*k[i] + R2[i]
[i,j] : R0[i]*k[j] + R0[j]*k[i] (i < j)

となる。暗号文は、各キーとそれに紐づく数のタプルの集合である。

復号手法(配布されたコード中での)

秘密鍵として保存された、公開鍵Kをつくるような鍵kのインデックスの集合をIとすると、[], [i], [i,i], [i,j] (i, j \in I)に紐付く数を足し上げることで復号を行っている。実際に足し上げると
msg + (\sum_{i \in I} k_i - K)(\sum_{i \in I} R0_i + \sum_{i}R1_i)
となることが分かり、\sum_{i \in I} k_i = Kであるから、配布されたコード中に記された方法で確かに復号できることがわかる。

解読手法

記号類の定義

msg : 復号を目指す数(未知)
k_i : 鍵i(既知)
K : 鍵iの部分集合の和(既知)
R0_i : 乱数(未知)
R1_i : 乱数(未知)
R2_i : 乱数(未知)
S_{i,j} : enc.txtの[i,j]に紐付く内容 (i \lt j)(既知)

また、合同式の法は常に素数Pとする。

解読

以下が成り立つ。

  1. S_{Null,Null} \equiv msg - K \sum_{i}R1_i
  2. S_{i,Null} \equiv -K \cdot R0_i + k_i \cdot \sum_{j}R1_j - R2_i
  3. S_{i,i} \equiv R0_i \cdot k_i + R2_i
  4. S_{i,j} \equiv R0_i \cdot k_j + R0_j \cdot k_i

式4から
\begin{cases} R0_0 \cdot k_1 + R0_1 \cdot k_0 \equiv S_{0,1} \\ R0_0 \cdot k_2 + R0_2 \cdot k_0 \equiv S_{0,2} \end{cases}
ここからR0_0を消去して整理すると
R0_1 \cdot k_2 - R0_2 \cdot k_1 \equiv (S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^{-1}
さらに式4から導かれる式と連立して
\begin{cases} R0_1 \cdot k_2 + R0_2 \cdot k_1 \equiv S_{1,2} \\ R0_1 \cdot k_2 - R0_2 \cdot k_1 \equiv (S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^{-1} \end{cases}
これを解いて
R0_1 = ((S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^ {-1} + S_{1,2}) \cdot (2k_2) ^{-1}
R0_0 = (S_{0,1} - R0_1 \cdot k_0) \cdot k_1^{-1}

式4を変形して
R0_i = (S_{i,j} - R0_j \cdot k_i) \cdot k_j ^{-1}

R0_0 , R0_1が既知なので、上式を用いてすべてのiに対してR0_iを求めることができる。(j=0とすればよい)

式2,3より
-K \cdot R0_i + k_i \cdot \sum_{j} R1_{j} + R0_i \cdot k_i \equiv S_{i,Null} + S_{i,i}
これを変形して
\sum_{j}R1_j \equiv ((S_{i,Null} + S_{i,i}) + K \cdot R0_{i} - R0_{i} \cdot k_{i} ) \cdot k_i ^{-1}

右辺は既知なので、R1の総和\sum_{i}R1_i が求まる。

式1より
msg \equiv S_{Null,Null} + K \cdot \sum_{i} R1_{i}
となり、msgを復号できる。

msg = 0x534543434f4e7b6b70736b7d
であり、フラグはSECCON{kpsk}

ソースコード
#!/usr/bin/python3

P = 79228162514264337593543950319
k_hs = 14883097866997387203089669453
keys = # 省略します。解説中のk_iを埋め込んでください

def mod_inv(n) :
	global P
	res = 1
	p = P-2
	while p :
		if p % 2 :
			res = (res * n) % P
		p //= 2
		n = (n * n) % P
	return res

# enc.txtから
c = # 省略します。解説中のS_{i,j}を[S_{i,j},[i,j]] のリストの形で埋め込んでください。Nullのところは要素数を減らして対応します。

sum_all = 0
tab = {}

for i in c :
	sum_all += i[0]
	tab[tuple(i[1])] = i[0]
	sum_all %= P

r0 = [0 for i in range(128)]
sum_r0 = 0

r0[1] = mod_inv(2*keys[2]) * ((tab[tuple([0,1])] * keys[2] - tab[tuple([0,2])] * keys[1]) * mod_inv(keys[0]) + tab[tuple([1,2])])
r0[0] = (tab[tuple([0,1])] - r0[1] * keys[0]) * mod_inv(keys[1])

r0[0] = (r0[0] % P + P) % P
r0[1] = (r0[1] % P + P) % P

sum_r0 = r0[0] + r0[1]

for i in range(2,128) :
	r0[i] = (tab[tuple([0,i])] - r0[0] * keys[i]) * mod_inv(keys[0])
	r0[i] = (r0[i] % P + P) % P
	sum_r0 += r0[i]

#assert
for i in range(128) :
	for j in range(i+1,128) :
		#print(i, j, (keys[i] * r0[j] + keys[j] * r0[i]) % P, tab[tuple([i,j])])
		assert((keys[i] * r0[j] + keys[j] * r0[i]) % P == tab[tuple([i,j])]);

sum_r1 = mod_inv(keys[0]) * ((tab[tuple([0,0])]+tab[tuple([0])]) + k_hs * r0[0] - r0[0] * keys[0])

sum_r0 = (sum_r0 % P + P) % P
sum_r1 = (sum_r1 % P + P) % P

#assert
for i in range(1,128) :
	tmp = mod_inv(keys[i]) * (tab[tuple([i,i])] + tab[tuple([i])] + k_hs * r0[i] - r0[i] * keys[i])
	tmp = (tmp % P + P) % P
	assert(sum_r1 == tmp)

ans = sum_all - ((sum(keys) - k_hs) % P) * (sum_r0 + sum_r1)
ans = (ans % P + P) % P

assert(ans == ((tab[tuple([])] + k_hs * sum_r1) % P + P) % P)

print(hex(ans))

問題雑感

初めて解いたCTFの古典暗号でない問題で、面白さを感じた。面白さを感じて解説を書いていたら長文になってしまった。rubyを読むのは辛かったが、解くのにそう必要な知識も多くなく「CTFの暗号問題はクソなぞなぞや謎知識を要求する問題の山」だと思っていたCTF初心者の私には良い影響を与えてくれたと思う。現代暗号面白そうなのでがんばろう。

感想

ひと月ほど準備期間があったが、論文やらCODEFESTIVALやらDDCCやらでなかなか準備できていなかった。正直役に立てる気がしていなかったが案の定役に立ってなかった。

Cryptは数弱にはつらい問題だったが、どうにかなりそうなのがCryptしかなかったのでCryptに取り組んでいた。はじめて読むrubyはつらかった。

オイラーフェルマーの小定理さえ知ってれば小中学生でも解けるCrypt200が解けなかったのは恥としか言えない。今後一層精進したい。

AOJ2335 : 10-Year-Old Dynamic Programming / 10歳の動的計画 解説(別解)

競技プログラミング プログラミング

はじめに

AOJ2335:10歳の動的計画法を解いたが、非想定解で解説記事が書かれてなかったので書くことにした。別解の中で使ってるテクニックは他でも使おうと思えば使える気がします。

問題概要

2次元平面上で、次のルールで(0,0)から(N,M)まで移動するときの経路数を答えよ。

  1. 移動は複数のステップからなる
  2. 1ステップではx軸またはy軸に沿う方向に1だけ移動できる
  3. x軸負方向またはy軸負方向への移動回数の合計はKステップである
  4. x座標、y座標が負となるような移動はできない

制約
1 <= N,M <= 100,000, 0 <= K <= 10,000
8sec, 64MB (AOJ)

解法

想定解はJAGのページにある。この記事ではDPで解く別解について解説する。

まず、x軸方向の移動とy軸方向の移動は分けて考えることができる。

x軸上の移動を考える。k回の負方向への移動を含む移動によってx=pにたどり着いたとする。このときの経路数をf(k,p)と表記する。また、この経路数はy軸上の移動でも同じである。

x軸負方向にk回移動したのちに(N,M)にたどり着いたとしよう。すると、
x軸に沿った移動回数 N+2*k 回
y軸に沿った移動回数 M+2*(K-k) 回
となる。

つまり、答えは次の式で求まることになる。
\sum_{k=0}^{k=K} f(k,N)f(K-k,M)\binom{N+M+2K}{N+2k}

二項係数の計算はO(N+M+K)ぐらいの前計算からO(1)で求まるため、前計算の結果と、f(k,N)とf(k,M)がk<=Kについて分かっていればO(K)で答えが求まることが分かった。f(k,N)とf(k,M)をk<=Kについて求める方法を考えればよい。

O(K * (N+M+K))のDPをすることでf(k,N)とf(k,M)は求まるのだが、これでは時間がかかりすぎてしまう。そうであっても、行うDPは別解とそう変わらないのでこのDPについても説明しておく。

dp(i,k) := i回の移動を行い、そのうちk回が負方向への移動であるような経路数。
として、更新は次の式で行う
dp(i,k) = \begin{cases} dp(i-1,k) + dp(i-1,k-1) & (i \geq 2k \text{ and } k \geq 1) \\ dp(i-1,k) & (\text{else}) \end{cases}
このようにしてDPを行えば、f(k,p) = dp(p+2k,k)
としてf(k,M)とf(k,N)を求めることができる。

さて、K回以上正方向に移動を行っていれば、その後どのような順番で移動しようともルールを満たしながら移動することができる。つまり、2*K回以上の移動を行った後であれば、どのタイミングで負方向への移動を行っても構わないことになる。

2*K回の移動が終わるまではDPで経路数をもとめ、2*K回以上の移動を行う経路については2*K回の移動が終わった時点のDPの結果をもとに計算すればよい。

つまり、
dp(i,k) = \sum_{k'=max(0,2K-i+k)}^{k'=k} dp(2K,k') \binom{i-2K}{k-k'}
でdp(i,k) (i > 2*K) を求めることができる。和をとる範囲について補足する。2*Kステップにk'回の負方向への移動が含まれていた場合、正方向への移動は2*K-k'回である。全体で正方向への移動はi-k回であるから、2*K-k' <= i-k が成立しなければならない。よって、和はk'=max(0,2K-i+k)からとる。

計算量は、DPを途中まで行うのにO(K^2)、DPの結果から、dp(N,k)とdp(M,k)を計算しf(k,N)とf(k,M)を求めるのにO(K)これが0<=k<=Kについて計算されるからO(K^2)となり、f(k,N)とf(k,M)を計算する処理全体でO(K^2)となる。

問題全体を通した計算量は、O(N+M+K^2)である。

実装

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
const ll mod = 1e9+7;
ll tab[10100];
ll tmp[10100];
ll ver[10100];
ll hol[10100];
 
ll fact[300100];
ll inv_fact[300100];
 
int main() {
    fact[0] = inv_fact[0] = 1;
    for(ll i = 1; i < 300100; i++) {
        ll t = mod-2, x;
        fact[i] = (fact[i-1] * i)%mod;
        x = fact[i];
        inv_fact[i] = 1;
        while(t) {
            if(t&1) {
                inv_fact[i]*= x;
                inv_fact[i]%= mod;
            }
            x = x*x%mod;
            t >>= 1;
        }
    }
    ll N, M, K;
    cin >> N >> M >> K;
    tab[0] = 1;
    for(int i = 1; i <= 2*K ; i++) {
        for(int j = 0; j <= K; j++) {
            tmp[j] = 0;
            tmp[j] = (((i >= 2*j && j) ? tab[j-1] : 0)
                + tab[j]) % mod;
        }
        for(int j = 0; j <= K; j++) {
            tab[j] = tmp[j];
            if(i - 2*j == N) {
                ver[j] += tab[j];
                ver[j] %= mod;
            }
            if(i - 2*j == M) {
                hol[j] += tab[j];
                hol[j] %= mod;
            }
        }
    }
    for(int i = 0; i <= K; i++) {
        for(int j = 0; j <= i; j++) {
            if(2*K-N-i <= j && (N+2*i>2*K)) {
                ver[i] += (tab[j] * fact[N+2*i-2*K] % mod)
                    * (inv_fact[i-j] * inv_fact[N+2*i-2*K - (i-j)] % mod);
                ver[i] %= mod;
            }
            if(2*K-M-i <= j && (M+2*i>2*K)) {
                hol[i] += (tab[j] * fact[M+2*i-2*K] % mod)
                    * (inv_fact[i-j] * inv_fact[M+2*i-2*K - (i-j)] % mod);
                hol[i] %= mod;
            }
        }
    }
    ll res = 0;
    for(int i = 0; i <= K; i++) {
        res += ((ver[i] * hol[K-i] % mod) *
            ((fact[2*K+M+N] * inv_fact[N+2*i] % mod) * inv_fact[2*K+M+N -(N+2*i)] % mod)) % mod;
        res %= mod;
    }
    cout << res << endl;
}

感想

想定解あたまいい。今回は非想定解だったけども、途中までDPをしてあとは計算頑張るという方針はどこかで使えそうだ。

ACM-ICPC2016 アジア地区つくば大会参加記

雑記 競技プログラミング

チーム t9qmib (九州大学) でACM-ICPC アジア地区予選つくば大会に参加していました．結果は6完19位．これはその参加記です．

メンバーは私，nola_suz，nikollsonの3名にコーチのgrrifon_zero．同じメンバーで参加するのは昨年以来2度目です．チーム名は我らが偉大なる先輩climpetさんからとりました．

前夜

研究室から帰りアイロンがけやら荷造りやらを始める．荷造り終わった時点で既に日付が変わっていたため絶望する．なぜ8:00発の飛行機を取ってしまったんだ．9:00発でも問題無く間に合っただろと愚痴る．

1日目

なんとか飛行機に間に合う時間に起床．睡眠時間は驚きの3時間．空港行ったら福岡空港第一ターミナル閉鎖の影響でレイアウト変わってるし，保安検査場が異様に混んでるし，もしかして飛行機に乗れないんじゃないかと思った．

なんとか飛行機に乗り，羽田に着くなりメールの着信に気づく．コーチからの「飛行機が欠航した」メールである．そして，チームメイトからも「飛行機が欠航した」のDMが．．．

I hate Jetstar.

飛行機はANAかJALを取るべきである．
この時点でチーム4名中2名の遅刻が確定する．

焦ってもしょうがないので空港で軽食を食べたあとつくばへ向かう．空港から出ていたバスに乗っても良かったのだけどICPC運営の推奨ルートでつくばへ．秋葉原まで出てつくばTXのほうが安い．つくば駅近辺で昼食にする．昼食中にコーチからDMが届く．

コーチ「ねえ，もう一人のチームメイトも遅刻するって知ってる？」
私　　「？？？？？？？」
コーチ「いやぁ，僕も今さっき聞いたんだけどどうやら本部のほうには連絡してるらしんだよね．本部から彼も遅刻するって聞いた．」

＼(^o^)／ｵﾜﾀ

無事1日目チームメンバー1人での参加が確定する．

受付を済ませようとするが，4人揃ってregisterらしい．もちろん弊チームは1人しかいない．受付のアミラーゼ伯爵に「2人は遅刻すると聞いていたけどもう1人は？」みたいな感じのことを聞かれる．

伯爵「あー，九大チームね．二人遅刻ってのは聞いてるけどもう一人は？」
私　「彼も遅刻らしいです」
伯爵「まじかー．．．遅刻する理由とか聞いてない？」
私　「聞いてないです．．．」
伯爵「連絡つく？」
私　「つかいないです」
伯爵「あー．．．．．．ジャッジ団の判断を仰ぎます．多分大丈夫だとは思うけども．」

みたいなやりとりの後，ジャッジからregisterして良いとの判断が出てどうにか失格は回避．ほんとご迷惑おかけしました．

で，「一人しかいないので，注意事項のアナウンスだとかルールについて把握してしっかりメンバーに伝えてくださいね」と言われる．英語ﾆｶﾞﾃ勢には辛いが，registerさせてもらえたのでがんばった．

register後，会場までの案内の時
staff A 「九州大学チーム．．．メンバーは1名？？？」
staff B 「ああ，九大チームね．はいはい．」
staff A 「えっ，よくあることなんですか？？？」

というやりとりがある．さすがに，registerにメンバー1人しか間に合わなかったというのは前代未聞なんじゃないのかな．

九大チームt9qmibの周囲には EfficientCoefficient (東大), Do Touch Everything (阪大), nocow (農工大)と有力チームが配置されていることに気づいてびくびく．JAG合宿でお話ししたヘクトさんやら，yazatenさんやらに声かけるなどする．

その後，トイレに行く時は手を上げてスタッフに声をかけて行くことだとか，割と重要な注意事項を聞いたりする．ちょくだいさんが両手を挙げて「トイレトイレー」と叫びながらトイレに行く理由が分かった．

プラクティスではとりあえず問題としてみたり，わざとWAになる提出をしてジャッジシステムがどういう表示になるのかを確認したりする．practice B問題を使ってジャッジサーバの強さを確認してみたが，浮動小数点の計算で1secで1e8はokで2e8ではだめだということがわかった．どうやら，CFやTCのサーバーほど強くはなさそうだ．また，競技環境にログインする時，ID/パスワードを入力してから実際に操作可能になるまで思いの外時間がかかることもわかった．

プラクティス終了後，他チームはスタックの広さを確認するなどしていたことをtwitterで知る．やっとけばよかったな．

つくば大に移動しての懇親会ではメンバーが2人に増えた．
チーム紹介は割とうまくいったと思う．いらすと屋の猪がのっそのっそ歩くアニメーションは結構笑いを取れたようだ．

懇親会終了後，ホテルにてコーチと合流．これで3/4揃った．
とりあえずTシャツや名札や資料を渡して一般的な注意事項を伝えるなどする．

23:00前に最後のチームメンバーが合流ようやくメンバー全員集合．よかった．

Tシャツや名刺を渡して注意事項の説明，そしてプラクティスで分かったことなど伝える．

布団に入ったのは日付変わってからだった

2日目

4:00ごろに目が覚める．二度寝を決意．
5:00ごろに目が覚める．三度寝を決意．
5:50ごろに目が覚める．もう寝るのはあきらめた．

朝食を摂った後，どうせこなるだろうと思ってあらかじめ準備しておいたユンケル黄帝プレミアムを飲む．備えあれば患いなしとはこのことである．

入場

入場前に持ち物検査がある．筆箱に入れておいたUSBメモリを出し忘れている人が多数居た．これは罠だ．筆箱から必要なものだけを取り出して残りはコーチに預けた．

コンテスト

開始と同時にA問題を読む．やるだけだったので8分でAC．
B,Cは任せてD問題を読む．

Dはにぶたんと嘘解法を立て，Bと並行して実装する．BがACした頃に，Dのにぶたんは嘘解法と気づき，Cを実装してもらう．

CがACしたあと，Dをハッシュで書き直す．D問題までAC．

ここまで2時間．ペース的にはだいぶ遅い．

E問題を読んだnikollsonが「あっ，これやろう」と言い始める．僕とnola_suzは「これ，強実装やるだけだし手を出してはいけないやつだ」と判断していたので止めたがnikollsonが「ｲｹﾙｲｹﾙ」と言ったのでそのまま実装してもらった．結果的にこれが fine play で実装開始から2時間ほどでデバッグまで完了していた．nikollson強い．

で，E問題の実装中にAC数の多いG問題をnola_suzと考察．貪欲にシミュレーションすれば解けそうという話になり，コインを置ける位置を区間で持つ感じのシミュレーションをする解法を立てる．オーダー的に難しいよねみたいな話をしていたがクエリ先読みでオーダー落ちるという結論が出た．nola_suz が実装するものだとばかり思っていたが，「じゃ，実装してください」と言われたので実装する．残り30分で6完．

その後はどうせ残り時間で実装まで終わらせるのは無理そうと言いつつ，どうにかなる問題がないか問題を漁っていた．

6完のままコンテスト終了，最終順位は19位でした．

感想

「6完できたし，PC使ってなかった時間は解ける問題がなくなった最後の30分だけだし，チーム戦略としては上手くいってたよね．」という話になった．解ける問題は全部解いたしあとの問題解けないのは実力不足としか言えないので，本当に上手く行ったと思う．

講評・表彰

会場の壁に魔方陣が描かれていたり（本当によく気づいたな），Cxiv-Dxivと上海交通大チームの争いが熱かったり，上海交通大のインタビューがめちゃくちゃかこよかったりした．講評の最中に地震が起きたがそのままスピーチが続けられた．

懇親会

各社の企業ブースで問題を貰って問題を考えてたりした．google問題のネタバレを聞いたが凝っていて面白かった．

まとめ

酷いトラブルがあったが，大会では今持ってる実力を出し切ったと納得できるだけの仕事はできた．これでICPCは引退になってしまうので寂しい．

Google Code Jam 2016 のTシャツが届いた

Google Code Jam 2016 のTシャツが届いた

Google Code Jam 2016 に参加してました。で、Distributed Code Jamで500位以内に入れたのでTシャツを獲得できました。GCJへのチャレンジは今年で4回目だったのですが、遂に憧れだったTシャツが獲れたのかと思うととても嬉しいです。

来年はDistributedでないCode JamのほうでTシャツを取りたいですね。

f:id:konjo_p:20160817194316j:plain
f:id:konjo_p:20160817194323j:plain

ctf4b2016博多参加記

ctf4b2016博多参加記

ctf4b博多に参加してきましたので参加記を

私のctf経験について

今年4月にgoogle CTFに参加しました．google CTFに参加して0完の洗礼を浴びたCTF初心者です．

web講義

web問題についての講義でした．内容はXSSについて．この講義でgoogle CTFの一番簡単な問題がカバーできたのかなぁ．．．

web問題を解くためのツール類の紹介もあり，google CTFのときに「え？？サーバに盗んだcookie送りつけるの？？管理してるサーバとかないし無理じゃね？？？」と思った私にとっては嬉しい講義だった．

フォレンジックス講義

パッケットキャプチャしたファイルが与えられるから，そこからフラグを探し出してくださいという趣旨の問題群を解くための講義だった．

ツールの機能を活用していかに効率的にパケットを読んでいくか，また，集中して読むべきパケットがどれかという点に焦点を当てての講義だった．前後のパケットの内容から，いつフラグが通信されたかを推測する話や，使用されたプロトコルの統計情報から集中して読むべきパケットを絞り込むと良いらしい．

講義を受けて，プロトコルとその代表的な利用目的について勉強しておくと，通信内容について推測できるから良いのかなと思った．

バイナリ講義

逆アセンブルされたバイナリを読む講義だった．mipsなら3ヶ月ぐらい読んでいたことがあったが，x86は未知の世界．x86はディスティネーションレジスタが決め打ちされてる命令があったりとか，分岐の方法とか覚えるのがmipsと比べて辛い印象を持っている．

幸いにも今回の講義で読んだバイナリたちは素直なバイナリだったので，何がなんだかわからんということはなかった．

パタヘネ読んでたりとか，低級な部分を大学で研究してたりというバックグラウンドがあったせいだろうが，今回の講義の中では一番簡単な講義に感じた．

実際にプログラムを逆アセンブルして読もうとすると，どの処理を集中して読んだら良いかわからん．ということが起こりがちなので，読むべき部分の絞り込みとかの話がもう少し欲しかったかなぁ．．．

あとIDAすごい．ループの構造をグラフィカルに表示してくれる．あれいい．

練習コンテスト

f:id:konjo_p:20160718123928p:plain

コンテストについて

6位でした．やったね！講義でやったことをきっちりやれば解ける問題が出ていたので，練習コンテストとして良い問題セットだったと思う．

MISCと分類されていた問題

基本的にやるだけっぽかった．CountUpGameの必勝法は競技プログラミングのスキルがCTFに活きたなーと．

Webの問題

web100点は憶えてない．web200はダブルクォテーションと山括弧使っていけそうだったけど，うまくいかなかった．あれなんでだろうな．

フォレンジックス
strings hoge.pcap | grep flag

すると良い感じにヒントが取れる．ので，あとはflag.txtだとかflag.pngだとかそれっぽいワードから何が行われているか推測したら200点問題が解けた．

バイナリの問題

100点しか解いてない．grepしたら取れた．

感想

CTF面白かったし，ctf4bも初心者（プロ）向けの話でなくきちんと初心者向けのイベントだったので良かった．ハラスメントが横行していない or 本当の初心者にはハラスメントしない 界隈は良い界隈です．ICPC引退まではCTFにがっつり時間をというわけにもいかないので，10月のICPC引退後には競技プログラミングに割いていた時間を少しばかりCTFに割いてみようかなあ．

最後にctf4bの講師，参加者の皆様ありがとうございました．

ICPC2016国内予選参加記

はじめに

チーム t9qmib としてnikollson, nola_suzと一緒にICPC国内予選に参加しました。結果は4完24位で、正式なアナウンスはまだですがアジア地区筑波大会への参加権を獲得できているはずです。

A問題

A問題の担当でした。2つ目の出力ファイルの作成時間を見ると6分でACしたようです。問題文の印刷が終わらないうちにACしてかなり良い調子。

B問題

nikollsonの担当。30分経過時点で通っていなくて嫌な予感がする。nikollsonの実力でこの時間にAC取れてないのはおかしい。途中でコーダーを交代して51分ごろにAC。図らずもB問題の担当になる。

C問題

素数定理を知っていたので、エラトステネスの篩みたいに書けば計算時間的には問題なく終わることに気づく。最大ケースが与えられていたことにはサンプルを通す段階で気づいた。B問題で詰まっていたので代わってもらい37分でAC。私がコーダーでした。

D問題

問題の概要を説明された時に「これ、TDPCで見た問題だ！」となる。TDPCのiwiの解法の方針は覚えていたものの、細かいところが記憶になかった。もやっとした方針を nola_suz 説明すると「区間DPってこと？」と言われ、そのまま nola_suz が漸化式を立ててコーディングすると64分でACした。強い。自分がiwiを書いたときバグに苦しんだ記憶があったから、バグが出て1時間ぐらいかかることを覚悟していた。

E問題

共有部分の表面積を辺の重みとしたグラフを作って、辺の重みの合計が最大になるような、連結な部分グラフを求める問題。ああでもないこうでもないと言いながら解法が立たずに苦しんでいた。コンテスト終了後にblue_jamさんがやってきて「いやぁ、E問題のEはEASYのEでしたね。」といわれる。一つの立方体は最大でも二つの立方体としか共有部分を持たないという制約を読み落としていたことに気づく。チームメンバーのうち2/3が制約を読み落としていた。

F問題

実装が重いやるだけ問題というnikollsonの直感。根付き木の同型判定を効率的にやる方法を知らなかったが、nola_suzが「ノードを訪れるときに '(' を、ノードから親に戻る時に ')' を文字列に追加するようにして、子から上がってきた文字列を辞書順にソートして親に上げれば良い感じに同型判定できるんじゃない？」と言って効率的に根付き木の同型判定ができることが分かる。完全にプロ。効率的な根付き木の同型判定のアイデアが出た時点で、E問題の解法が立たずに1時間何もしていない状態だったので、何もしないよりは書いていたほうがいいだろうという判断で実装に入る。この時点で残り1時間。途中、H問題の解法が分かったという声が上がったが、その時点で残り30分少々。チームメイトに残り20分時点までに一通りの実装が完了するが、残り20分でデバッグが完了する見込みは薄いことを伝えるが、F問題を解き続けたほうがいいという判断になった。結局間に合わず。1時間PCを占領したのに申し訳ない結果になってしまった。

ちなみに説明された解法はこんなの
f:id:konjo_p:20160626212702p:plain

G問題

よんでない

H問題

やるだけじゃないかという意見が出たが、この時点でコンテスト終了まで残り30分ということで、F問題を書き続けるほうがいいだろうという判断でコーディングせず。

感想

どう見ても5完セット。あわよくば6完狙う感じでやらなきゃだめだった。
A問題の実装、図らずもB問題の実装、C問題の実装、間に合わなかったF問題の実装を担当していました。チーム中レーティング最弱なのになぜこうなった。