2017-02-24

Wiener's Attack を実装した

はじめに

RSA暗号運用でやってはいけない n のこと #ssmjp from sonickun

このスライドをみてそういえばWiener’s Attack実装したこと無いなと思ったので勉強がてら実装してみました.

元論文はCryptanalysis of Short RSA Secret Exponentsで
理論についての説明は
http://elliptic-shiho.hatenablog.com/entry/2015/12/18/205804
が詳しいです.
ここでは実装について書いていこうと思います.

実装について

Wiener’s Attackは連分数展開と連分数から近似分数を求める2つのパートからなります.
連分数展開に関してはユークリッドの互除法の過程で得られるので素直に実装します.
ユークリッドの互除法の計算量は$O(\log_{10} n)$

def rational_to_contfrac(x: int, y: int) -> Iterator[int]:
    while y:
        a = x // y
        yield a
        x, y = y, x - a * y

連分数から近似分数を求めるパートがあるのですが,まず連分数から有理数を復元するところから説明します.
連分数を後ろから足して逆数求めることを繰り返していけば復元できます.

def contfrac_to_rational(contfrac: List[int]) -> Tuple[int, int]:
    from functools import reduce
    return reduce(
        lambda f,q: (q * f[0] + f[1], f[0]),
        reversed(contfrac),
        (1, 0),
    )

ちなみに上記のコードは使ってないのでrepositoryにはありません.
前から復元する場合は元論文の式6を用いるとできます.実際にはこちらを使います.

$$ \begin{alignat}{2} n_0 & = & q_0, \qquad d_0 & = & 1 \\ n_1 & = & q_0 q_1 + 1, \qquad d_1 & = & q_1 \\ n_i & = & q_i n_{i-1}+n_{i-2}, \qquad d_i & = & q_i d_{i-1}+d_{i-2} \\ \end{alignat} $$

式からもわかる様に前の2つの状態を持っていれば次の状態を作ることができます.
このままだと$i$が$0$と$1$の時条件分岐しないといけません.
$-1$と$-2$の時を条件を満たす様に定義することで実装がシンプルになります.

$$ \begin{alignat}{2} n_{-2} & = & 0, \qquad d_{-2} & = & 1 \\ n_{-1} & = & 1, \qquad d_{-1} & = & 0 \\ n_i & = & q_i n_{i-1}+n_{i-2}, \qquad d_{i} & = & q_i d_{i-1}+d_{i-2} \\ \end{alignat} $$

def contfrac_to_rational_iter(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]:
    n0, d0 = 0, 1
    n1, d1 = 1, 0
    for q in contfrac:
        n = q * n1 + n0
        d = q * d1 + d0
        yield n, d
        n0, d0 = n1, d1
        n1, d1 = n, d

計算量は$O(n)$になります.
用途を考えてgeneratorとして返しています.

近似分数を列挙するのですが元論文の3章のアルゴリズムを用います.
そんなに難しくないので読んでみることをおすすめします.
基本的には連分数を前の方だけ使って復元した値を近似分数とします.
愚直に実装すると以下の様になります.

def convergents_from_contfrac_naive(contfrac: List[int]) -> Iterator[Tuple[int, int]]:
    m = len(contfrac)
    for i in range(m):
        if i % 2 == 0:
            q = contfrac[:i+1]
            q[i] += 1
            yield contfrac_to_rational(q)
        else:
            q = contfrac[:i+1]
            yield contfrac_to_rational(q)

添字が偶数のときは最後の要素を1足した物を有理数に復元し,それを近似分数とします.
これは毎回contfrac_to_rationalを呼んでいて無駄です.
偶数のときの処理が面倒くさい様に見えますが,式を見てみると最後の要素に1を足すという処理は1つ前の結果を足すこと同様だと言うことがわかります.
つまり直前の結果だけ持っていれば良いです.
$i=0$のときは定義した$i=-1$のときの結果を用います.

def convergents_from_contfrac(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]:
    n_, d_ = 1, 0
    for i, (n, d) in enumerate(contfrac_to_rational_iter(contfrac)):
        if i % 2 == 0:
            yield n + n_, d + d_
        else:
            yield n, d
        n_, d_ = n, d

これまで紹介して来たコードを組み合わせてattack関数を定義します.

def attack(e: int, n: int) -> Optional[int]:
    f_ = rational_to_contfrac(e, n)
    for k, dg in convergents_from_contfrac(f_):
        edg = e * dg
        phi = edg // k

        x = n - phi + 1
        if x % 2 == 0 and is_perfect_square((x // 2) ** 2 - n):
            g = edg - phi * k
            return dg // g
    return None

近似分数を総当りでdを特定します.
正しい有理数に復元できたかどうかの判定は元論文のとおりに実装しました.
平方数の判定は$O(log_2n)$程度でできるので,全体の計算量は$O((log_2n)^{2})$になります.
比較的簡単にWiener’s Attackを実装できました.
証明やどういう場合に使えるかについては元論文を読んで見てください.

おまけ

平方数の判定は2分探索を用いることで出来ますが,今回はgmpの実装を参考にしました.
平方数の$\mod256$は$44$パターンしか無いのでまずそれで篩にかけます.
全体の$80\%$程度を瞬時に判定することが出来ます.
残りの$20\%$程度に対して$\mod9,5,7,13,17$で同様のことを行います.
これにより全体の$96\%$に対して判定を行えます. 残りの$4\%$に対してニュートン法を用いて平方数判定を行います.

def is_perfect_square(n: int) -> bool:
    sq_mod256 = (1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0)
    if sq_mod256[n & 0xff] == 0:
        return False

    mt = (
        (9, (1,1,0,0,1,0,0,1,0)),
        (5, (1,1,0,0,1)),
        (7, (1,1,1,0,1,0,0)),
        (13, (1,1,0,1,1,0,0,0,0,1,1,0,1)),
        (17, (1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1))
    )
    a = n % (9 * 5 * 7 * 13 * 17)
    if any(t[a % m] == 0 for m, t in mt):
        return False

    return isqrt(n) ** 2 == n

整数のみを扱うニュートン法を用いました.
ニュートン法は初期値を決めないといけませんが平方根を求める場合は簡単にある程度良い初期値が与えられます.
適切に$n$を決定すると$S \approx \alpha \cdot 2^{2n}$は$0.5 \leq \alpha \lt 2$になります.
$n$は$S$の最上位bitが立ってる場所を2で割ると求めることが出来ます.
$\sqrt{S}\approx\sqrt{\alpha}2^n$になるので初期値を$2^n$にすると正しい答えに近い地点にいるので収束が早くなります.

def isqrt(n: int) -> int:
    if n == 0:
        return 0

    x = 2 ** ((n.bit_length() + 1) // 2)
    while True:
        y = (x + n // x) // 2
        if y >= x:
            return x
        x = y

終わりに

Pythonなりにわかりやすく高速に実装できたかなと思います.
(JavaのBigIntegerを使って実装している例があったのですが読みづらくて辛かった) 実装してみて楽しかったので他の手法も論文を読みながら実装できるくらい頭良くなりたい.

参考文献

Cryptanalysis of Short RSA Secret Exponents:
https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf
公開鍵暗号 - RSA - Wiener’s Attack - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです:
http://elliptic-shiho.hatenablog.com/entry/2015/12/18/205804
pablocelayes/rsa-wiener-attack:
https://github.com/pablocelayes/rsa-wiener-attack
wihoho/Wiener-s-Attack:
https://github.com/wihoho/Wiener-s-Attack
平方数かどうかを高速に判定する方法 - hnwの日記
http://d.hatena.ne.jp/hnw/20140503
Integer square root:
https://en.wikipedia.org/wiki/Integer_square_root
Methods of computing square roots:
https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Rough_estimation

2016-07-26

二辺連結成分分解

ゆらふなさんの記事を見て実装してみようと思ったので記事を書きました。
この記事ではlowlinkを使った方法でやっています。

* 2017年9月30日追記 *
二重辺と表記していましたが二辺と表現するほうが適切と判断したので変更しました.
それに付随して定義などの情報を追加しました.

定義

橋 (Bridge): その一つの辺を取り除くとグラフが非連結になるような辺
K辺連結グラフ: Kより小さい数の辺を取り除いても連結であるグラフ
二辺連結成分 (2-edge connected component): 2より小さい数(=1)の辺を取り除いても連結である部分グラフ -> 橋を含まない部分グラフ

ref: k-edge connected graph

内容

二辺連結成分は橋を含まないような部分グラフなので橋を列挙することで二辺連結成分分解ができることがわかる。
橋の検出、列挙に関しては次のpdfがわかりやすい。グラフ探索アルゴリズムとその応用
基本的には深さ優先探索をするだけで求まる。まずグラフに対して適当な頂点を決めそこから深さ優先探索を行う。

$ord[v]:$ 深さ優先探索でその頂点を何番目に訪れたか
$low[v]:$ 後退辺を一度だけ使ってたどり着ける$ord$の最小値 $(lowlink)$

とすると深さ優先探索木上の辺$uv$が橋であるかの判定は
$$ord[u] < low[v]$$ で行える。$ord$は深さ優先探索木の根方向に行けば行くほど小さくなるので$u$の子である$v$は$ord[u]<ord[v]$を満たす。
$ord[u] >= low[v]$の場合は$u$より根方向に後退辺を用いて移動でき, $u$より根方向の頂点からは$uv$を使わずに$u$に到達できるので
$uv$が橋でないことがわかる。逆に$ord[u]<low[v]$の場合は$v$から$u$より根方向に到達できないので橋であることがわかる。
一度の深さ優先探索で橋を列挙することができるので計算量は$O(n + m)$になる。

橋を列挙できれば橋の端点から橋となる辺を使わないように深さ優先探索で二辺連結成分を列挙できる。
ただ橋が存在しない場合は適当な頂点から深さ優先探索すると良い。
全体の計算量は$O(n + m)$になる。

実装は以下のようになった。

二辺連結成分分解

verifyにはARC039Dを用いた。submission

ARC039D

2016-06-27

ICPC国内予選2016参加記

6/24(金)にあったICPC国内予選2016にICT48(@orisano,@ringoh72,@DeEn_queue)として出場しました。
結果は4完32位と去年より順位は下がってしまいとても悲しかったです。

大会前日

前日に今年用のライブラリを作ってないことに気が付き、去年のライブラリをベースに作成。
いろいろやってたら5時。1限もあるし寝れない。このまま挑むしかない。

大会当日

1限が終了してそのまま学校で就寝。3時間ほど寝てから今回国内予選初参加の
@ringoh72と@DeEn_queueの提出練習とプリンタのテストをして待機してました。

問題

A:全探索
僕がスピードのみを重視して O(n²) のコードを書いてAC。

B:問題を知らず
僕がC,Dを見ているうちに@ringoh72がサンプル合わないと言っていた。
C,Dの解法を考えているうちにACしていた。

C:篩っぽいことをする、最大ケースが与えられていなければ辛そう
@DeEn_queueが解法を考えてくれていたがブランクが長かったからなのか実装に悩んでいたので
僕が代わりにコードを書いてAC。

D:区間DP
僕が担当していて舐めプしてたら結構いろんなミスが見つかって辛かった。
解法自体は制約と見た感じからすぐわかったのだけどうまく実装できず。
そこそこ時間はかかったもののAC。

E:誤読
最初みて幾何かなと思い後回しにする。ちゃんと読むべきだった。
ちゃんと読んでも問題の意味を変に解釈してしまった。おそらく一番時間を費やすべき問題だったと思うし反省。

F:外側から連結成分取り出して木を作って同型性判定
3人で考えてやるべきことはわかったのだが、「同型性判定ライブラリないからできない＞＜」とか
甘えたことを言ってしまい断念。少し考えれば思いつきそうだし取り組むべきだった。

G:誤読
3人ともワープ場は飛行機の線路上に限らず任意の地点に置くことができると勘違いしてしまって断念。
clarができなくてはじめて困ってしまった。

H:わからず
フローのオーラを感じたが経験と知識不足から断念。

まとめ

二人とチームを組んで競プロするのは初めてだったので役割とかその辺がよくわからなかった。
チームで練習すべきだったなと痛感しました。そもそもチームが締め切り当日まで決まってなかったのがやばい。
アジア地区行けるといいな（３年連続になるといいな）

2016-03-08

Git Challengeに参加してきました

3/5に開催されたmixiさん主催のgit challengeというイベントに参加してきました。

参加したきっかけ

@imishinist(たいさん)から「参加しないのですか？？？？？？？」と煽られたのもありますが、
gitは頻繁に使うものの全然使いこなせてない感があり、そろそろスキルアップしたと思っていた矢先だったというのが大きいです。

感想

twitterで知っていた@KAGE_MIKUくんとチームで競技に取り組みました。
@KAGE_MIKUが話しやすい人でわからないところは聞くことができたし、shell芸っぽいところでは手伝うこともできたかなと思います。
結果として4位になり、嬉しさと悔しさがありました。
採点にトラブルがありHumanCIになっていたのが少し残念でしたが、それでもとても楽しめました。

競技終了後に解説があるのがとても良く、こんなコマンドあったんだ、こうやって解決するのか、などの気付きがありました。

こんな面白いイベントを開催してくれたmixiさんに感謝しかないです！
是非後輩たちは参加してみてください！！！！！！！！！！！！！！！！

学校とか部活とかでgit challengeのような取り組みをしてみるとgitの布教に使える気がするし作ってみたい感がある。

2015-12-11

AOJ 0568 Pasta

AOJ0568をErlangで解いてみたのでBlogを書きます。
問題の概要については省略します。

前回と同様に JOI 2011-2012 予選問題・採点用入力から正答することを確認しています。

-module(aoj0568).
-export([main/0]).

main() ->
  {N, K} = get_pair(),
  Fixed = lists:reverse(lists:sort([get_pair() || _ <- lists:seq(1, K)])),
  io:format("~p~n", [pasta(N + 1, Fixed, {0, -1, -2})]),
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

get_pair() ->
  [First, Second] = [to_i(V) || V <- string:tokens(io:get_line(""), " ")],
  {First, Second}.

pasta(N, [{N, P}|_], {Q, _, _}) when P /= Q -> 0;
pasta(N, [{N, P}|T], S={P, _, _}) -> pasta(N, T, S);
pasta(_, _, {P, P, P}) -> 0;
pasta(1, _, _) -> 1;
pasta(N, L, S={P, Q, _}) ->
  case get({N, S}) of
    undefined ->
      Ret = lists:foldl(fun(X, Acc) ->
                            Acc + pasta(N - 1, L, {X, P, Q})
                        end, 0, lists:seq(1, 3)) rem 10000,
      put({N, S}, Ret),
      Ret;
    Memo -> Memo
  end.

コードの概要

入力を受け取って、逆順にソートします。
逆順にソートする理由は引数を減らせるというだけの理由です。
基本的には全探索でパターンマッチにより遷移できない状態排除しています。
本来であれば過去2日分の情報を持つだけで遷移先を決定できるのですが、
過去3日分の情報を持つことでパターンマッチを容易にしています。
遷移する際に過去の情報をスライドさせるだけで良いのでとてもシンプルになります。

終わりに

やっぱりErlangだとプロセス辞書を使ってメモ化再帰が楽に綺麗にかけるので好きです。

2015-12-11

AOJ 0595 Schedule

何を今更と思う方もいると思いますが、AOJ0595をErlangで解いた~~（未確認）~~ので記事を書くことにしました。

追記(4:35) JOI 2013-2014 予選問題文・採点用入出力・解説の入出力例に対してすべて正解していました。

Erlangを書くのが非常に久しぶりだったのですがとても楽しくかけました。

問題概要に関してはAOJを見てください。

以下コードです。ぶっちゃけ普段からErlangを書かないのでErlangとして良いコードかはわかりません。

-module(aoj0595).
-export([main/0]).

main() ->
  _ = io:get_line(""),
  S = string:strip(io:get_line(""), right, $\n),
  io:format("~p~n", [schedule(S, true, false, false)]),
  init:stop().

schedule(S, J, O, I) ->
  (
   schedule(S, true, true, true, J, O, I) +
   schedule(S, true, true, false, J, O, I) +
   schedule(S, true, false, true, J, O, I) +
   schedule(S, true, false, false, J, O, I) +
   schedule(S, false, true, true, J, O, I) +
   schedule(S, false, true, false, J, O, I) +
   schedule(S, false, false, true, J, O, I) +
   schedule(S, false, false, false, J, O, I)
  ) rem 10007.
schedule([$J|_], false, _, _, _, _, _) -> 0;
schedule([$O|_], _, false, _, _, _, _) -> 0;
schedule([$I|_], _, _, false, _, _, _) -> 0;
schedule(_, J, O, I, PJ, PO, PI) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0;
schedule([_], _, _, _, _, _, _) -> 1;
schedule([_|L], J, O, I, _, _, _) ->
  LL = length(L),
  case get({LL, J, O, I}) of
    undefined ->
      Ret = schedule(L, J, O, I),
      put({LL, J, O, I}, Ret),
      Ret;
    Memo -> Memo
  end.

再帰はパターンマッチとか使えるととても書きやすいですね。
Erlangにはプロセス辞書という仕組みがあってメモ化するのも非常に簡単です。
プロセス辞書にキャッシュを入れるのは正しいことなんでしょうかね。。。

追記(3:14):
公開してすぐにもっとシンプルに書けることに気が付きました。Blogに公開することは偉大ですね。

-module(aoj0595).
-export([main/0]).

main() ->
  _ = io:get_line(""),
  S = string:strip(io:get_line(""), right, $\n),
  io:format("~p~n", [schedule(S, {true, false, false})]),
  init:stop().

schedule(S, State) ->
  Bool = [true, false],
  Cand = [{J, O, I} || J <- Bool, O <- Bool, I <- Bool],
  lists:foldl(fun(X,Acc) -> Acc + schedule(S, X, State) end, 0, Cand) rem 10007.

schedule([$J|_], {false, _, _}, _) -> 0;
schedule([$O|_], {_, false, _}, _) -> 0;
schedule([$I|_], {_, _, false}, _) -> 0;
schedule(_, {J, O, I}, {PJ, PO, PI}) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0;
schedule([_], _, _) -> 1;
schedule([_|L], State, _) ->
  LL = length(L),
  case get({LL, State}) of
    undefined ->
      Ret = schedule(L, State),
      put({LL, State}, Ret),
      Ret;
    Memo -> Memo
  end.

コードの概要

書いていることは至ってシンプルでJ君,O君,I君の今日と前の日の状態を持って,
それをパターンマッチによって遷移できない状態を除外しているだけです。
あり得る組み合わせだった場合、次の状態に遷移します。
遷移できる次の状態がたかだか8通りなのですべての遷移を試すコードになっています。
あとは引数によって状態が変わらないのでメモ化することができます。

終わりに

Erlangっぽいコードが書きたいなら競プロするな👊って感じですね。

2015-12-08

第26回高専プロコン競技部門反省会場

この記事はICT Advent Calendar 2015の7日目として書かれました。

はじめに

ブログの更新は1年ぶりになります、@orisanoです。
去年のICT Advent Calendarぶりの投稿になります。
今年はいろんなイベントや大会に参加しましたし、残り短いですがまだまだ参加します。
今年参加した中で個人的に最も注力したのが"""高専プロコン"""です。
読んでると思われる層の人は知っていると思うので詳しくは説明しません。
今年は競技部門に参加してきました。そのことについて書こうと思います。

高専プロコン競技部門と僕

今回の高専プロコン競技部門(以下競技部門)のチームは進捗優先探索という名前で

僕 (専攻科1年) (リーダー兼コーダー)
レオきゅん (4年) (コーダー)
じんくん (2年) (コーダー)
1年生2人

という構成で役割としてはリーダー(初)のような物をやっていました。
ちなみに僕は競技部門に参加するのが今年で4回目になります。

舞鶴大会 (良い問題、なとりうむさんに初めてあった)
有明大会 (サイコロ回、感情喪失)
旭川大会 (サイコロ通信回)
長野大会 (今回)

どの大会も思い出深いですね。（サイコロは絶対にユルサナイ）

初動

今年の競技部門の課題は「石畳職人Z」というタイトルで、
概要としては「全部埋まるかどうかわからないジグソーパズルを出来るだけ埋めよう」というものでした。
詳細が知りたい方はこちら

問題が公開されてすぐに練習場の作成にとりかかりました。
去年と違って競技者として参加するというものあって公開しませんでしたし、内部的にも活用しませんでした。
練習場の作成を通して、ルールの理解や曖昧な部分が理解できるのでとてもおすすめです。
練習場の作成が終わった頃から簡単なサーベイをしたり、チームメンバーに対して
探索アルゴリズムの概要をレクチャーしたりしていました。
それと並行してSiv3Dを用いたビジュアライザー兼手動ソルバーなどを作りました。
（本当はこの辺から一年生に対してちゃんと指示を出したりすべきだったんだろなぁ）

6~8月

土台が出来上がってきたので、ソルバーの実装ににとりかかりました。
非公式練習場（以下練習場）に提出を始めたのこの時期からです。
（練習場自体は5月くらいにはできていて、当時では信じられない解が提出されていた）
今回モチベーションが保てたのも練習場の存在があったからと言っても過言ではないでしょう。
練習場を公開していた@mecha_g3さんには感謝しかないです。
この頃は僕のソルバーはボロボロで全然良い解が出ずとてもつらい思いをしていました。
一方じんくんのソルバーがそれなりに良い解を出しており、評価関数の重みなどを参考にしたところスコアがかなり改善したことを覚えています。
じんくんありがとう。。。
KNCTが練習場にたくさん発生していて上位を独占していた頃でもありました、この時はひたすらKNCT爆発しないかなとか不穏なことを言っていた気がします。

KNCT多すぎてどこの高専かわからないよ！！！！！！！！！！！！いい加減にして！！！！！！！！！！！
— おりさの (@orisano) 2015, 7月 2

KNCT、ランキングに5人くらいいるしやめてくれ
— おりさの (@orisano) 2015, 7月 2

KNCTと名乗ることを法律で禁じよう！（過激派）
— おりさの (@orisano) 2015, 7月 5

競技練習場でKNCTと名乗るやつを爆発させるボタンください #procon26
— おりさの (@orisano) 2015, 7月 6

最終的には僕もKNCTを名乗っていました。

KNCTって名乗ってましたが、これは陰謀によりOkNCTのOがなくなったためです（） #procon26
— おりさの (@orisano) 2015, 10月 13

ブレイクスルーとして高速化のために制限をかけたソルバーが
良いスコアを出すようになり、練習場でほとんどの問題で1位になりました。
8月の後半(?)からTMCITの攻撃が始まって、競争が激化します。
がスコアが全然改善せず、モチベーションがどんどん維持できなくなっていきました。
進捗管理も疎かになりました。ほんとにダメですね。

9月~

夏休みの期間はインターンシップで株式会社ABEJAさんとDeNAさんに行きました。
合わせて3週間ほどでしたがとても良い経験になりました。
その間は開発お休みしていました。( ◞‸◟ )

ここからアルゴリズムベースの改良は少なくし、高速化や提出ツールの作成などに入りました。
tcmallocなど修正無しで高速化が見込めるツールの導入や、
Instrumentsなどを見ながらボトルネックを探して高速化していました。
また_GLIBCXX_PARALLELで楽して並列化を行いました。
これでそれまでの4倍程度の速度が出るようになりました。やったね。

提出ツールの作成にあたって、チームの中で僕が一人だけ
Macユーザだったのでマルチプラットフォームを意識しなければいけなくなりました。
ISUCONのために勉強していたgolangで書きました。クロスコンパイル最高！

問題の1位取得数は6個で1位だったので比較的心おだやかに長野へ向かいました。

本番

長野に到着してからはどうやってTMCITの人を闇討ちするかを考えていました。いませんでした。

初日は練習と1回戦があったのですが練習の様子を見ると
自動で問題取得、解の提出ができないと困るということが分かりました。
空いた時間を使って取得、提出の流れを自動化してくれるツールを作りました。これが1回戦で非常に役に立ちました。
1回戦は第2試合だったのですが、1位、1位、2位と最終成績2位で突破することができました。(NAPROCKを除くと1位)
1問目はほとんど提出の速度を競う勝負になっていたので
自動化ツールが火をふき1位を取ることができました。
1回戦に関しては数ヶ月の努力があったのでそんなに不安はありませんでした。
準決勝は、5位、3位、3位と最終成績3位で突破することができました。
僕は4回目で初の決勝進出だったのでとても嬉しかったです。（顔がニヤついた写真が。。。）
決勝は10位と個人的には残念な結果でしたが、特別賞がもらえたのでよかったです。

反省

リーダーとしてもっとちゃんと仕事をふるべきだった。
進捗確認も絶やさずするべきだったし、困っているところをヒアリングすべきだった。
せっかくチームに入ってもらった1年生たちに仕事を振れず、
かと言って何かを教えることもできず、プロコンの楽しさを
十分に経験させられなかったことが一番の反省点です。本当に申し訳ない。

最後に

なんだかんだ個人的には今年のプロコンとても楽しめたので大満足です。
専攻科に進学した意味があったと思える出来事でした。
現地では他の高専の競技部門の人とそれなりに交流できたし、最高でした！！
チャンスがある後輩の皆さんは自分の武器を磨いて高専プロコンに出ましょう！！
以上、老害からでした。

明日は駐日ユーゴスラビア臨時政府大使館(@ICT_yugosoviet)です。
めちゃくちゃおもしろい記事を書いてくれることを期待しています。

薄いブログ

技術の雑多なことを書く場所

Wiener's Attack を実装した

はじめに

実装について

おまけ

終わりに

参考文献

二辺連結成分分解

定義

内容

ICPC国内予選2016参加記

大会前日

大会当日

問題

まとめ

Git Challengeに参加してきました

参加したきっかけ

感想

AOJ 0568 Pasta

コードの概要

終わりに

AOJ 0595 Schedule

コードの概要

終わりに

第26回高専プロコン競技部門反省会場

はじめに

高専プロコン競技部門と僕

初動

6~8月

9月~

本番

反省

最後に