読者です 読者をやめる 読者になる 読者になる

math314のブログ

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

Størmerの定理

前書き $2^{n} - 3^{k} = 1$ を満たす正の整数 $(n,k)$ をすべて求めなさい。 いきなりですが、上記の問題が解けるでしょうか? まず小さい数を代入していくと、$(n,k) = (2,1)$ の時は $2^{2} - 3^{1} = 1$ となってこれを満たすことがわかります。 それ以…

Windowsで、実行ファイルを書き換えずに既存の.Netアプリケーションのメソッドを置き換える話

動機 昔、箱庭XSSという問題がSECCONで出題されました。 どのような問題だったかは他の方のブログを見て頂ければ分かるかと思います。 nash.hatenablog.com 問題作者のスライドはこちらです。 【XSS Bonsai】 受賞のご挨拶 by @ymzkei5 【SECCON 2014】 - De…

Parindromic Tree

競プロ忘年会 in 東京 2016 で発表したpalindromic tree(eertree, 回文木) についてのスライドとコードを載せておきます。 Palindromic tree from __math www.slideshare.net gist.github.com

ARC059 : F - バイナリハック / Unhappy Hacking

追記3: yosupoが最新版の解説を書いたようです。こちらを見ましょう。 yosupo.hatenablog.com 以下は旧記事です。 AtCoder Regular Contest 059 で出題された F - バイナリハック / Unhappy Hacking の O(n)解法です。 解説はコードに埋め込みました。 カタ…

n以下の素数のsumを高速に計算する

目次 動機 問題概要 準備 計算量 \(1 \le p_b \le n^{1/4} \) の時 \(n^{1/4} \le p_b \le n^{1/2} \) の時 素直なプログラム 最適化したプログラム 余談 動機 Project Euler で、n以下の素数の合計を求める問題がありました。 Problem 10 - Project Euler …

ISUCON5 オンライン予選 通過しました

優勝賞金100万円!今年もやります ISUCON5 開催と日程のお知らせ #isucon : ISUCON公式Blog 「お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係…

任意modでの畳み込み演算をO(n log(n))で

http://misawa.github.io/other/fast_kitamasa_method.html を見て刺激されたので書いた. 畳み込み演算? 任意modでの畳み込み演算 中で使われてる技術達 c++のコード コードと原理の説明をちょっとだけ載せています. コードだけ欲しい人は https://gist.g…

Boston Key Party 2015 Wood Island : 150 Write up

問題概要は省略します…聞きたい人がいたらリプライかコメント下さい

SECCON CTF 2014 決勝戦 サーバ六 write-up

SECCON CTF 2014決勝戦・全国大会カンファレンス SECCON CTF 2014決勝戦・全国大会カンファレンス チーム Mr.Takedashi(メンバー: @misodengaku, @aki33524, @chibiegg, @__math) で出ていました. 9/24位です. 日本人チームの中では4/13位でした.今年はcr…

dwangoプログラミングコンテスト

Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder 26位でした.D問題が通せなかったの悲しいですね.

code festival 2014 上海

id math で出ていました. 5位で表彰された,やったぜ. コンテストページ : http://code-festival-2014-china.contest.atcoder.jp/

最近開催された大会

ICPC アジア地区予選 日本地区 2014 チーム kyutOUki で出ていました.11位でした.入賞だそうです. CODE FESTIVAL2014 21位でした,賞金が20位からだったので悔しかった. しかしアジア決勝(!?)に出場できるとの事なので,そこで賞金を得たい. Tシャツ2枚…

tkbctf4 簡易writeup

rcrypto M2 + MB_1 = x, M2 + MB_2 = y (mod N) という式があるので,Mを求めよという問題. (1つ目の式)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 -…

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

先週ですが,id math で出ていました,17位で残念. 公式ページ : http://tenka1.klab.jp/2014/ コンテストページ : http://tenka1-2014-final-open.contest.atcoder.jp/ 六本木ヒルズの建物はそれ自体で迷路として完成しており楽しかった. Tシャツを貰った…

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

SECCON 2014 オンライン予選(日本語) Writeup チーム Mr.Takeda で,5人(@aki33524,@chibiegg,@haru2036,@misodengaku,@__math) で出ていました. 結果としては4位で全国大会出場決定,すごい. 誰かわからないけど竹田さんに迷惑じゃないか心配になってきた…

ICPC 国内予選 2014

チーム kyutOUki(@__math, @mitaki28, @ustimaw) で出ていました. 6完,6位 でした.

Heavy-Light Decomposition

最近アツイ*1、木を分解する手法の一つ。 重軽分解 とか、HL-decompositionとか呼ばれている。 アルゴリズム edgeを"Heavy"と"Light"に分けて "Heavy"edgeで繋がれた頂点を一つにまとめる の2段構成。 ここに書いてあるedgeの分け方は元のHeavy Light Decomp…

SECUINSIDE 2014 prequal writeup

竹田氏 500pt 52th でした pillow_reader crypto 200pt 唯一のcryptoだった。 ファイルをダウンロードすると python3.2aのコンパイル済みのpycが来る。 pillow_reader.pycにPrimeUtilが必要との事なので、要求される関数を実装することで、import出来る状態…

SECCON CTF 2013 全国大会 Druaga write-up

@misodengaku, @aki33524, @domitry と チーム Takedashi で出ていました、 17/20 位。 Druagaの2つ目のflagが取れなくて悔しかったので解いた。 1個目 80MB程の大き目のファイルがダウンロード出来る。 1日目の最後の方に問題がオープンされたので、ダウン…

SECCON CTF 2013 Online

チーム : 竹田氏 で出ていました。 ところで竹田氏って誰ですか。 7位、3700ptです、予選通るのかな? crypt100,200,300,400,500を解きました。

ICPC Asia 2013 Problem G: Longest Chain

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1341 通りませんでした、辛い 2014/01/05 00:22 通りました 投げたコード(AC) O((m+n) log (m+n))? #include <map> #include <iostream> #include <vector> #include <algorithm> using namespace std; #define FOR(i,n) for(int i =</algorithm></vector></iostream></map>…

期待値と条件付確率

前置き これは、Competitive Programming Advent Calendar Div2013, 第 13 日の記事です。 みんな大好き期待値の問題の基礎について確率変数を使わない縛りで書きたいと思います。 1,2は非常に簡単な内容となっているので読み飛ばしても構いません。