math314のブログ

主に競技プログラミング，CTFの結果を載せます

最近開催された大会

  • ICPC アジア地区予選 日本地区 2014
    • チーム kyutOUki で出ていました．11位でした．入賞だそうです．
  • CODE FESTIVAL2014
    • 21位でした，賞金が20位からだったので悔しかった．
    • しかしアジア決勝(!?)に出場できるとの事なので，そこで賞金を得たい．
    • Tシャツ2枚，パーカーを貰いました
  • CODE RUNNER 2014
    • 8位でした． 初の賞金だったので嬉しかったのですが，交通費の関係で赤字になりました．
    • もう少し戦略を練れば3位は取れていたので，次回があれば3位以上を目指したい．
    • Tシャツ，パーカーを貰いました

tkbctf4 簡易writeup

rcrypto

M2 + MB_1 = x, M2 + MB_2 = y (mod N)

という式があるので，Mを求めよという問題．

(１つ目の式)y - (2つ目の式)x = 0 より

(y-x)M2 + (B_1 * y - B_2 * x) M = 0 (mod N)

gcd(M,N) = 1 じゃないと困るので(複合できないし)

\[ (y-x)M + (B_1 * y - B_2 * x) = 0 \]

また， gcd(y-x,N) = 1 だったので

\[ M = (B_2 * x - B_1 * y) * (y-x)^{-1} (mod N) \]

後は代入するだけ．

high-low

次の手が分からないと仮定した場合，最適な戦略で挑んだとすると，1回でもクリア出来る確率が63.2%を超えるのに必要な試行回数は132020回程です．頑張ってください．

amida

これでstage20まで行きました．

https://gist.github.com/math314/24a458d0ffc006d151ff

最後のフラグを投げる前に終わってしまいました．

The flag is "Gh057 in the 1egs, not 5hell!"

天下一プログラマーコンテスト 2014 本戦

先週ですが，id math で出ていました，17位で残念．

公式ページ : http://tenka1.klab.jp/2014/

コンテストページ : http://tenka1-2014-final-open.contest.atcoder.jp/

六本木ヒルズの建物はそれ自体で迷路として完成しており楽しかった．

Tシャツを貰ったので先週から今週にかけて開催されていた ICPC夏合宿 に着て行きました．結果，さわり心地が良く寝間着するとよいのではと感じた．

人の写真だけどこんなの

来年も開催されたら賞金getしたい．

続きを読む

SECCON 2014 オンライン予選(日本語) Writeup

SECCON 2014 オンライン予選(日本語) Writeup

チーム Mr.Takeda で，5人(@aki33524,@chibiegg,@haru2036,@misodengaku,@__math) で出ていました． 結果としては4位で全国大会出場決定，すごい．

誰かわからないけど竹田さんに迷惑じゃないか心配になってきた．

f:id:math314:20140720152945p:plain

私は あみだくじ(プログラミング 300),ダンプを追え！(バイナリ 300)と,箱庭XSSリターンズ(Web 300)の部分点を取りました． 箱庭はみんなでワイワイしながら得点しました．

続きを読む

Heavy-Light Decomposition

最近アツイ*1、木を分解する手法の一つ。 重軽分解 とか、HL-decompositionとか呼ばれている。

アルゴリズム

  1. edgeを"Heavy"と"Light"に分けて
  2. "Heavy"edgeで繋がれた頂点を一つにまとめる

の2段構成。

ここに書いてあるedgeの分け方は元のHeavy Light Decompositionと違うかも

*1:[要出典]

続きを読む