第三回ドワンゴからの挑戦状(dwacon)参加記
予選
Aやるだけ,B問題に手間取った.B問題に手間取ったときはもうだめかと思ったが,C問題D問題が得意な感じの問題だったので助かった.E問題の部分点確定で18卒パワーを使って予選通過が決まると思ったでEの部分点を取りに行った.方針は比較的早く立ったが,苦手な感じのDPで部分点を確定させるのに手間取ってしまった.
結局32位に食い込むことができ,非18卒が上に11人以上居れば通過が確定.後日予選通過メールが届いた.
本戦
前日
オープンコンテストの告知で公開された500-1100-1200(25)-1300という配点を見て凍りつく.Acで525ptsとった後は座るだけになることが見える.変な貪欲が想定解法の500ptsだと最悪0完もあり得るなと絶望するなどしていた.
本戦開始前
集合時刻の4時間前に宿泊先のホテルを出て,部屋は清掃中の時間だし行くあて無いなーとか言いつつ歌舞伎座周辺をぶらぶら.
15時頃にドワンゴのオフィスに上がる.
集合時刻が15時というドワンゴ的かつ人道的な時間.さすがドワンゴ.
受付が終わった後,控え室でTシャツを着たりニコ生用のアンケートを記入するなどする.Tシャツにタグがついていたのだけれど,はさみを持っていなかったので噛み切ろうと試みるも失敗.思いっきり引っ張ってみたらタグの糸が切れてタグを外すことができた.
準急さんやtozangezanさんが,「自己紹介書けないんだけど」と言いながら競プロerのいつものノリで会話をしていた.
コンテスト
A問題を500点と思って舐めてかかったら痛い目を見た.30分経ってもA問題の方針が見えない.辛い.正しい式にできるかどうかの判定は式が破綻した部分を数える感じで判定できることが分かったが,式の計算結果の最大化の方法が全くわからない.DPできる感じに見えなかったので必死になって貪欲を考える.
A解けないことが有り得ると思い,先にCの部分点を確保しに行く.Cの部分点は自明に二重ループ回すだけだった.35分ちょっとで25ptsを確定させる.
再びA.頭を冷やして考える.段々とDPが見えてくるが状態の持ち方がわからない.スタックの状態どうやって持つのとか言っていた.このあたりでは貪欲の可能性は完全に捨てていたが状態の持ち方が見えない.
続A.さらに冷静になって考える.O(|S|^3 * K^2)の区間DPがようやく見える.区間DPだと気付いた後の遷移のさせ方は単純なので迷わなかった.実装量はDPにしては多いと思ったが,そんなにバグる要素は無かったので落ち着いて実装.しかし答えを出力する部分で謎のbool値を出力する痛恨のミスを犯し10分ほど溶かす.死.82分ちょっとでAC.これ500ptsとは思えない.
C問題は考察しやすそうだったが,残り時間であの手の問題の実装をするのは無理だと判断し,順位表を見てBに着手する.問題設定からして「これ平方分割だよな〜」という感じの問題.いい感じの平方分割を思いついたと思ったが,実装を進めているとMLEしてしまうことに気づき無事死亡.MLE防ぐにはTLEする方法しか見えないしこれなんなんだーって言っていたらコンテストが終わった.
Acで19位.DDCCの順位も19位だったのでこの数には何かと縁がある模様.
解説
A問題の解説でchokudaiさんが「ここに居る人はこんなのサクッと通しましたよね〜」と18卒パワーで通った弱小コーダーを煽る.つらい.
B問題ついに逃げ続けてきたMo's Algorithmと向き合う日が来たのかと思った.ちゃんと勉強しようね.うん.
C問題は「なるほどね」って感じだった.コンテストが終わって実装したい感じの問題ではない.
D問題は読んで無いので解説もよくわからなかったが面白そうな雰囲気を感じたので後で解いておこうと思います.
表彰式
yutaka1999さんの名前が間違えられたのがハイライト
懇親会
タダ酒とタダ飯にありつく.人の金で飲み食いするのは楽しかった.
kobaさんやkimiyukiさんとお話しする.競プロな人とお話し.もるさんとお話ししたり,江添さんとお話ししたり,どわんごな人とお話し.
余興のぷよぷよ大会でchokudaiさんが優勝する.完全にプロ.ぷよぷよ大会の後 chokudaiさんを捕まえて,「A問題本当にあれ500ptsですか?」と聞いたところ「典型典型〜」とのこと.
あとケーキ
テレビちゃんが厚い。ブラウン管だったのか。 #dwacon pic.twitter.com/9LTagyFbrw
— kusanoさん@がんばらない (@kusano_k) 2017年1月14日
帰路
おひらきになったあと,ホテルまで戻る電車ではかみぺさんと一緒だった.Mo's algorithmのお話しとか「SRMのd1m埋めは効くぞ」という話しをしてもらう.「今日のA問題あれ500ptsじゃなくて800ptsぐらいあると思うんですけど」と言ったところ「800ptsも無くて多分600ptsぐらい.典型と言えば典型だし.」という意見をもらう.僕がDP苦手なだけだった.
その後,かみぺさんとお別れしホテルに戻りドワコン終了.
感想
コンテストは辛かったが,社内見学と懇親会は楽しかった.タダ飯はうまい.ドワコンのレベル的に自分が本戦に来れるとは思っていなかったので,本戦に出れたこと自体嬉しかった.
DDCC2016参加記
要約
切る削る磨くのコンテストで19位でした.
予選
A,Bやるだけ.Cは大根2に出といて助かったなという感じだった.Dはマージテクを疑いつつも解けず.18卒パワーで予選通過した.
本戦
コンテスト
配点を確認してできて3完だなーと思う.席が自由席で近くにヘクトさんゆらふなさんしょらーさんが居たので雑談してた.
A問題はやるだけだったのでやる.
B問題は冷静になって考えると,貪欲で良いことが分かるので貪欲にやると通った.27分でAC.
C問題はさすが700ptsという感じだったが,落ち着いて考察を詰めると普通に探索でとけるのでまあ700pts.61分でAC.
D問題は途中まで貪欲で詳細をDPで詰めるタイプの問題だなーと思ったのでそういう考察を詰めて実装したがWAだった.考察の方針は合ってそうだがよくわからん.
DDCC特別ビュッフェ
Discoの飯は旨い.高そうなご飯が並んでいた.チョコレートフォンデュを食べたり,t9qmib各位とお話ししたり,その他18卒の知り合いとお話ししていた.
さてさんを闇討ちするため「ドーモ,サテサン.コンジョウデス.」と挨拶する.結局闇討ちには失敗した.
会社見学
福利厚生施設すごい.あと,B問題の答え合わせ(物理)がDisco社によって行われた.
懇親会
1回のコンテストで2回も旨い飯が食べられるとは思ってなかった.お酒も出た.あとケーキ.
予選も含めて参加してくれた、すべて〜〜〜の皆さーん、本当にありがとうございました‼️‼️‼️#DDCC2016 pic.twitter.com/1YfuwNr4U9
— ディスカバリーチャンネル (@DiscoveryJapan) 2016年12月3日
懇親会にて順位表の凍結が解除され,表彰式が行われるなどする.順位表凍結前にantaさんが全完して1位を確定させていたので完全に茶番.最終結果19位でした.
らて君やasiさんと初対面するなどする.中二双子やまるーんさんも居たが,声をかける勇気なし.らて君が久留米の人でよかった.多少声がかけやすかった.
感想
Disco含めプロコンを開いてくれる企業は良い企業です.最終結果19位はなかなかパフォーマンス出ていたと思う.ratedでなかったのが残念.コンテストの成績はまあ良いほうだったし,ご飯は美味しいしで大満足でした.
参加者の皆様,スタッフの皆様,ありがとうございました.
CODE FESTIVAL 2016 参加記
予選
予選A
インターン中だったので,インターンの滞在先から出ていた.早解きしてどうにか通過できた.10分前後で勝負が決まってしまうのってどうなの...理想を言えば予選Aでは800ptsが解けるかどうかぐらいが通過ラインになって欲しいんだけどな...
予選B
予選B通過できなかった.
予選C
予選C通過できなかった.
本戦
0日目
昨年,当日に福岡出発だと間に合わないということが実測で分かっていたので今年は前泊を申請.前泊が認められ確率統計のテストが終わった(オワタ)後東京へ飛んだ.B787に乗ってみようと思って便を取っていたのだが機材変更でB777になった.1WA.
はじめて787に乗ります
— 紺青 (@konjo_p) 2016年11月25日
777やんけ(機材変更
— 紺青 (@konjo_p) 2016年11月25日
東京に到着し,ホテルへ向かう.
京急線から大江戸線へ乗り入れている電車に乗ったのだけど「会社違うんだから当然乗り換えやろ〜〜」と言って電車を降りてしまう.同じ電車でよかったことはその電車が出発した後で気づきました.2WA.
大江戸線の人形町駅と日本橋駅を間違えて降りる.3WA.
東京の終電って恐ろしいですね.文字通りすし詰めで体が当たるとか荷物引っかかって人の迷惑とかそんなこと考えてたら電車から降りることができないなんて.
そうして人形町駅を降りて宿泊先のホテルへ.
ここに宿泊先があるじゃろ pic.twitter.com/4ztr69Wjtl
— 紺青 (@konjo_p) 2016年11月25日
.@konjo_p これをこうして pic.twitter.com/bW4LbgVHeE
— 紺青 (@konjo_p) 2016年11月25日
@konjo_p お分りいただけただろうか
— 紺青 (@konjo_p) 2016年11月25日
宿泊先のホテルをGoogleさん勘違いしてる4WA.ちなみに,4WA目にはペナルティとしてタクシー代が1200円つきました.電車終わってたし仕方なし.
さすがにタクシーがホテルの場所を間違えることはなかった.無事にホテル到着.
1日目
本戦
105位.Ω\ζ゜)チーン
A-Dまでは割とすんなり溶けたがEが難しかった.難しかったけどパーカーがかかっていたので Convex hull で殴りにいってパーカーを獲得した.暴力的に得点を取ってしまったので反省.
tourist トーク
7歳から始める競技プログラミング.
英語力が低いので内容の理解は通訳任せ.プログラミング用語含めて訳していて本業の通訳の恐るべく実力を知った.
山本一成さん講演
山本さん「みんなご飯食べてきなよ.なくなっちゃうよ.」
との計らいで開始が15分ずれ込む.寿司・肉・ピザおいしかったです.山本さんが「みんなkaggleやろうよ.なんでやってないの.」と発言したことによりTODOにkaggleが積まれた.
書道コーディング
「数弱黄色」と書いておいた.
2日目
会場まで
会場まで歩いているとバタ子さんと合う.「本戦F問題1000ptsも無いですよ.さっさと解きましょ.」と煽られる.(後日解いたけど確かに1000ptsもなさそう)
トーナメント
asa!
今年はレベル別に30分,30分,40分のコンテスト3本でトーナメントをやるらしい.
トーナメント1回戦
0完.満点解が見えたので取りに行ったら実装が間に合わなかった.MSTとLCAを使う結構重めの実装だったのに満点を狙いに行ったのがだめだったらしい.
トーナメント2回戦オープン
部分点だけ.普通にDPすればよかったらしいが,DPの方針を間違えてて死.やっぱり自分は青なのだなあ.
トーナメント3回戦オープン
1完!.やったね.ついに1完できたよ.スライド最小値を実装したことはなかったのだけど,hadroriさんの書いた記事を見ながら実装したらどうにかなった.しかし,3回戦が40分だったので救われたというところがあって辛い.
お昼ご飯
あまり見ない鳥の肉のお弁当を食べた(雉?鴨?どっちだっけ).鶏肉とそんなに歯ごたえは変わらない.
体力測定
前屈をしたら腹筋を攣った.あとは右利きのはずなのに左手の方が10kg握力が強かったりとか.
りんごさんクイズ
例によって例のごとくあのノリで競プロのプロたちにクイズを出していた.地図を使ったゲームで「これ自明に勝てる手が存在するんですけど」とか言われていたのが面白かった.
リレー
gcdやるだけ問題の担当だった.
リレーにて,よすぽさんは天才ということを再確認した.
感想
こどふぇはやはりこどふぇだった.今年も面白かった.
参加者の皆様,スタッフの皆様,ありがとうございました.
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 are prime. Thus, the prime factorization of pq is .
So, we could calculate d such as and decipher the cipher text c by calculate .
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 参加記
はじめに
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の等比数列であり(このことは帰納法で証明できる)、その総和は長さNの超増加列ではとなります。ところがこの問題で与えられるパラメータを見てみると、でありナップザック暗号の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_B | R0[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(既知)
: 鍵iの部分集合の和(既知)
: 乱数(未知)
: 乱数(未知)
: 乱数(未知)
: enc.txtの[i,j]に紐付く内容(既知)
解読
以下が成り立つ。
式4から
ここからを消去して整理すると
さらに式4から導かれる式と連立して
これを解いて
式4を変形して
が既知なので、上式を用いてすべてのに対してを求めることができる。(とすればよい)
式2,3より
これを変形して
右辺は既知なので、R1の総和 が求まる。
式1より
となり、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初心者の私には良い影響を与えてくれたと思う。現代暗号面白そうなのでがんばろう。
AOJ2335 : 10-Year-Old Dynamic Programming / 10歳の動的計画 解説(別解)
はじめに
AOJ2335:10歳の動的計画法を解いたが、非想定解で解説記事が書かれてなかったので書くことにした。別解の中で使ってるテクニックは他でも使おうと思えば使える気がします。
問題概要
2次元平面上で、次のルールで(0,0)から(N,M)まで移動するときの経路数を答えよ。
- 移動は複数のステップからなる
- 1ステップではx軸またはy軸に沿う方向に1だけ移動できる
- x軸負方向またはy軸負方向への移動回数の合計はKステップである
- 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) 回
となる。
つまり、答えは次の式で求まることになる。
二項係数の計算は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を行えば、
としてf(k,M)とf(k,N)を求めることができる。
さて、K回以上正方向に移動を行っていれば、その後どのような順番で移動しようともルールを満たしながら移動することができる。つまり、2*K回以上の移動を行った後であれば、どのタイミングで負方向への移動を行っても構わないことになる。
2*K回の移動が終わるまではDPで経路数をもとめ、2*K回以上の移動を行う経路については2*K回の移動が終わった時点のDPの結果をもとに計算すればよい。
つまり、
で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は引退になってしまうので寂しい.