2014-10-23

全国高等専門学校プログラミングコンテスト一関大会

（この本文は約 13,000 文字もあります）

第25回高専プロコン（一関大会）と同時開催された，第6回 NAPROCK 国際プロコンの競技部門に東京大学チームとして ioryz, mfumi2 と参加し，champion を頂きました．以下，自分たちが作成したプログラムについての解説記事になります．

ソースコードは https://github.com/natrium11321/procon2014_ut に公開しています．

NAPROCK とは

高専プロコンと NAPROCK を混同している人が多いので一応解説します．NAPROCK は高専プロコンと同一のルールで同時開催されるものの，両者は別の大会として扱われます．高専プロコンにエントリーした高専生は自動的に NAPROCK にもエントリーしますが，ハノイ，大連などの国外の大学は NAPROCK にのみ参加するという形で行われます．国内の大学は今年度から（来年度もそうかは分かりませんが）NAPROCK に参加することが出来るようになりました．従って，NAPROCK としての優勝は東京大学ですが，高専プロコンとしての優勝は大阪府大高専となり，両者は区別されます．

競技ルール

http://www.procon.gr.jp/uploads/procon25/Apply25.pdf （PDF 注意）の 8 ページ以降を参照してください．

開発環境

以下の環境で開発を行いました．実質の開発期間は8月頭〜本戦までで約2ヶ月半，週三回程度集まりました．総行数約 20,000 行，508 コミットです．

OS
- 開発環境：Mac OS X Mavericks 3台（コーディング）, Windows 7（公式サーバ動作用）
- 本番環境：Mac OS X Mavericks*1 1台（サーバ）, Ubuntu 14.04 2台（クライアント）
言語：C++11*2
コンパイラ
- 開発環境：clang
- 本番環境：clang, gcc 4.8*3
ライブラリ
- boost（全般，画像処理(boost.gil)，ネットワーク(boost.asio)）
- Qt (UI)
- Intel TBB（スレッドライブラリ）
- TC Malloc（高速メモリ管理）
- sparsehash（高速ハッシュテーブル）
ビルドツール：CMake
エディタ・IDE：Sublime Text 3, vim, emacs, Qt Creator
デバッガ：lldb, gdb
バージョン管理：Git (on github)

基本的なアプローチ

今回の問題は，与えられた断片画像（以下，ピース）から元の画像を推定する問題（ジグソーパズル）と，選択・交換操作を繰り返して全てのピースを少ないコストで正しい位置へ運ぶ問題（スライドパズル）に分けられます．この二つのパズルの解法は，基本的に独立に考えることが出来ます．僕達のチームでは，mfumi2 がジグソーパズルを，僕と ioryz がスライドパズルをそれぞれ担当しました．

ジグソーパズル

ジグソーパズルについては，実はもう少し成果を昇華させて，何らかの形で発表出来ないかと考えています．従って，現段階におけるアルゴリズムの詳細やソースコードの公開は控えさせて頂きます．お見せ出来る形になるまでしばしお待ちください．

（以下，mfumi2 の文章を拝借しました）

写真画像のジグソーパズルというと一見簡単そうに見えますが，実は結構難しく，画像処理系の学会である CVPR にも 2009 年から地味に毎年 1 本ずつぐらい論文が投稿されています．最新のだと ECCV 2014 にあります．

いろいろと既存の手法を参考にしつつ，メンバーと話合いながら実装した結果，最新の ECCV のものにほぼ匹敵するというか，論文内で使用されているあるデータセットに対して 1% ほど精度が良く，かつ高速なものができました（精度97%）．とはいっても問題によっては人間がぱっと見て明らかにおかしいものができる場合があり，まだまだ良い手法があるはずだと思います．せっかくなのでこの件についてはもう少し考えていきたいと思っています．

（一番代表的なアプローチ（かつ多分最初に思いつくの）はピース間に類似度というか距離を定義して，その距離の和が最小になる組み合わせを見つけるというものですが，本質的に巡回セールスマン問題の類題に帰着されるので厳密解を見つけるのが困難であり，またその問題の厳密解を見つけたとしてそれが本当の解であるという保障はどこにもありません．）

ちなみに，大会で出題された問題については，単純な貪欲的アプローチでも解くことが出来たようです．

スライドパズル

以下を実装することで，沖縄高専のみなさんが作ってくれた練習競技場の全てのタイトル*4において1位，または1位タイを取る事が出来ました．

基本的な方針は，他高専や他大学と同じでビームサーチです*5．

小さなサイズ用 (AI名: kurage)

主に 10×10 以下の小さなサイズの問題については，以下の二種類の操作を基本遷移としたビームサーチを用いました．

交換操作：上下左右の4通りの移動が行えます．但し，
- 選択セルが盤面の端や角にいる場合は，盤面からはみ出る方向には移動しません．
- 直前の遷移も交換操作だった場合は，直前の移動を打ち消す方向には移動しません．
選択操作：盤面のサイズ (H*W) と同じ通り数の選択が行えます．但し，
- 直前の遷移も選択操作だった場合は，選択操作を行いません．
- 現在選択しているピースと同じピースは選択しません．
- 最後の一回の選択操作の時，盤面の偶奇*6が完成状態の偶奇と一致するようなピースしか選択しません．
- 探索の高速化を図るため，既に正しい位置に存在するピースは選択しません．
- 探索の高速化を図るため，現在選択しているピースが，その正しい位置に近い位置（一致，又は条件によってはその一近傍）に存在する場合のみ，選択操作を行います．

評価関数

用いた評価関数は以下です．http://heuristicswiki.wikispaces.com/N+-+Puzzle を参考にしました．

manhattan distance : 各ピースの現在の位置と正しい位置のマンハッタン距離の総和．
linear conflict : 同一軸上にある2つのピースの対について、両ピースの完成位置も同一軸上にあって、かつそれぞれの正解位置の左右関係（または上下関係）と現在のピースの左右関係（または上下関係）が入れ替わっているものの数。
variance : 正しいピースが存在しないマスの座標 (x, y) についての統計分散の和 ( $s_x$ + $s_y$ )．
random : [0, 1] 上の一様乱数に (現在の manhattan distance)/(最初の manhattan distance) を掛けたもの．
squared manhattan : 各ピースの現在の位置と正しい位置のマンハッタン距離の二乗の総和．
weighted manhattan : 正しい位置が端の方に存在するピースについては大きな重みを，中央付近のピースについては軽い重みを付けた manhattan distance.

最終的な盤面の評価値は，上記の評価関数をある結合係数で線形結合した値を用います．この結合係数は ioryz に最適化して貰いました．練習競技場の問題番号 6 phycolow (8×8, 交換コスト3) に対して上記の評価関数を用いて解を計算すると，ビーム幅 4,000 で概ね以下の様な交換コストが得られました．

manhattan distance のみ : 1700 ~ 1500
上記 + linear conflict : 1500 ~ 1400
上記 + variance : 1500 ~ 1350
上記 + random : 1450 ~ 1350
上記 + squared manhattan : 1250 ~ 1150

個人的には squared manhattan の発見が一つのブレイクスルーだったと思っています．遠いところにあるピースほど大きな重みをかけることで，最終的に遠い二つのピースが交換されたような状態に陥ってしまう，といった現象を防ぐことが出来ます．また，評価関数に乱数を加えると，万が一そのような状態に陥った場合に，その状態から脱出することが出来るようになります．

weighted manhattan は問題番号 13 沖縄高専 (3×16) のような縦横比の偏った問題に対して威力を発揮しました．

多様性の確保

ビームサーチを用いる際は，解の多様性を確保するのが大事だと言われています．これは，似たような盤面ばかりが候補に存在すると，せっかく複数の候補を持つ意味が失われ，互いの弱点を補うことが出来なくなってしまうためです．

そこで僕たちは，候補の多様性を確保するため，同一盤面の除去を行いました．実際に除去を行うと分かりますが，今回の問題でも意外と同一状態（各ピースの位置，選択しているピース，選択回数が一致している状態）は多く存在していました．同一性の判定には，zobrist hashing*7 を用いたハッシュテーブルを使いました．ハッシュテーブルには，google が公開している sparsehash を使いました．

また，多様性を確保するための別の方法として，選択回数によるビーム幅の分割を実装しました．これは，例えば最大選択回数が4, ビーム幅が 4,000 の時，選択回数別（1回〜4回）にそれぞれ 1,000 のビーム幅を振り分けるというものです．選択回数が少ないビーム内に存在する盤面状態は，選択操作を行うことで，それより選択回数の多い状態に遷移することが出来ますが，逆はありません．これにより，選択回数を使い切った状態で埋まってしまう，といった事態を防ぐと共に，多様性を向上させることが出来ます *8．加えて，常にビーム幅を等分割するのではなく，現在の解答の進行度合いに応じて動的に変更するようにしました．

大きなサイズ用 (AI名: dragon)

主に 10×10 よりも大きなサイズの問題に対するソルバーです．このソルバーは，以下の3種類のビームサーチを順に行います．

最初の一回以外選択操作を行わず，交換操作のみを遷移としたビームサーチ．(AI名: whale)
ピースを端から１つずつ確実に埋めていく操作を遷移としたビームサーチ．(AI名: dolphin)
前述した小さなサイズ用のビームサーチ．(AI名: kurage)

whale は kurage とほとんど同じビームサーチですが，whale では選択操作を最初以外行わないところが違います．盤面の各ピースを全体的に正しい位置に近づけ，主に dolphin の手数を削減するのが目的です．これにより，マンハッタン距離の総和は，16×16の盤面だと 2700 程度から 800~200 程度まで下がります．

whale だけだとマンハッタン距離はいずれ下げ止まり，なかなか0にはなりません．そのため，次の AI である dolphin では，端から確実に埋めていくビームサーチを用います．これは，埋めるマスを指定し，交換操作のみでそのマスに正しいピースを運んでくる動作を一遷移としたビームサーチです．埋めることのできるマスは限られており，最初は四隅で，あるマスを埋めるとその一近傍を新たに埋めることが出来るようになります．また，実際に埋める部分のアルゴリズムは ioryz が実装しました．行や列の最後の2マスを埋めるときには逆にしないといけないなど，コーナーケースが無数にあり，かなり実装難易度の高い実装だったと思います．マスを埋めるアルゴリズムの内部では，始点と終点を指定して，ピースを運ぶ関数を用いています．これは僕が A* 探索を用いて実装しました．更にその内部では，選択中のピースを指定した点まで移動させる関数を用いています．こちらは幅優先探索を用いて実装しました．その内部でも，なるべくマンハッタン距離が上がらないような経路を選ぶなど，細かい最適化を幾つかかけています*9．評価関数としては，manhattan distance, linear conflict の他，揃ってない領域がどれだけ扁平でないかを表す値などを使いました．dolphin は，中央の 10×10 を除いた領域が完全に埋まるまで動作を続けます．

最後に，10×10 の領域について，前述した小さなサイズ用の AI を走らせておしまいです．以上をまとめると，大きなサイズの問題については

ビームサーチ（ビーム幅 4000)
↓
ビームサーチ（ビーム幅 200) → A* → 幅優先
↓
ビームサーチ（ビーム幅 4000)

という三段構造の探索を行っている，ということになります．

参考のため，問題番号 9 草原 (16×16) をこの AI に解かせた動画を作成しました．この動画の最終的な交換回数は 4700 回程度です*10．ピースがその正しい位置から遠いと青っぽく，近づくと赤っぽくなり，正しい位置に揃うとオレンジになります．

whale: 最初〜1:57
dolphin: 1:57〜2:53
kurage: 2:53〜最後

dragon solver - YouTube

操作列の最適化

操作列の部分列を，それと等価でより短い部分列に変更する処理を行いました．例えば，操作列に「上へ移動」「下へ移動」という連続した二つの交換操作が含まれていたら，これは無駄な操作なので，共に消し去ることが出来ます．普通にビームサーチを組んでいたら発生しそうにないですが，今回のプログラムで言うと，前述の三段ビームサーチによる解答を接続した際に起こりえます．

また他にも，2×2 の領域における回転操作を短くすることが出来ます．「上右下左」で時計回りに一回転すると，選択しているピースは元の位置に戻ってきますが，選択ピースが通った3つのセルは，1つずつピースが入れ替わります．従って，同じ向きに3周すると，全てのピースの位置が最初の状態に戻ります*11．これを用いると，例えば時計回りに7回動かしている操作列は，反時計回りに5回動かすのと等価であることが分かるので，解答を短くすることができます．この最適化は地味に有効で，16×16 だと 20 手くらい削ることが出来ます．

高速化

今回の問題は，かなり時間のウェイトが重く，解答を高速に計算することが求められました．従って，以下の様なコードレベルの最適化を行いました．結果的に，16×16 でも交換回数 4,000 台後半の解答を安定して 5 秒で作成できるようになりました．

評価関数の差分計算

状態を遷移する毎に評価関数を毎回計算し直すのは無駄です．以前の計算結果を利用して，少しの計算量で評価関数を更新することが出来ます．簡単なように見えますが，実装は意外とややこしいです．

並列化と lock-free

ビームサーチはメタヒューリスティクスアルゴリズムの中でも並列化しやすい方だと思います．Intel TBB を用いて並列実装したところ，4コア8スレッドの CPU でシングルスレッドの 4 倍程度の実行速度が得られました．また，極限まで lock を掛けなければならない部分を削減し，lock がどうしても必要な場所でも spin lock を用いることで，高速な並列処理を実現しました．尚，並列処理が入った部分のデバッグは再現性が低いことも多く，かなりしんどいです．デバッガを活用しましょう．

解答復元

当然ですが，ビームサーチにおける探索では，各盤面における今までの操作の履歴を残しておかないといけません．メンバとして操作列を全ての盤面に動的配列として持たせておく実装も考えられますが，盤面のメモリ上のサイズが肥大化し，またヒープ領域の確保及び解放が頻発するため，好ましくありません．この問題に対処するため，最初，shared pointer が親を指しているリンク構造のツリーを作成しました．これは，子孫が途絶えたら先代に遡ってノードを根絶やしにする構造で，不要になったメモリをその場で開放できるため，メモリの使用効率は最も良いと思われます．しかしながら，確保と解放を動的に繰り返すため，セグメンテーションが起きやすい，という点と，shared pointer がそもそも重い（ポインタのデリファレンスが頻発する，データ競合が起きないことを保証するため，内部で atomic 操作を行っている，など）という点が存在し，暫くの間代替技術が望まれていました．本戦の一週間ほど前に，通常の動的配列をリンク構造として用いる実装に変更し，これらの欠点を克服しました．

テンプレートと branch

盤面の最大サイズは 16×16 であり，このサイズで固定長として確保してしまうと，例えば 4×4 の問題を解くときはメモリの無駄が多く発生します．メモリの無駄は容量を食うだけではなく，キャッシュ効率も落としてしまうため，忌むべき存在です．可変長として確保すると，今度はメモリの動的な確保・解放が増えてしまいます．唯一の解決策は，最小サイズの 2×2 から最大サイズの 16×16 まで，225 パターンすべての状態を静的に確保出来るよう，テンプレートを駆使することです．一応，テンプレートのパラメータ次第で 16×16 の固定長の一部を使う実装にも切り替えられるようにしました．branch.hpp にはこの二つの実装の橋渡しを行う関数が定義されており，大変なことになっています．尚，本プログラムはフルコンパイルに1時間程度かかるのですが，主な原因はコイツです．

速いマシン

やはり最後はマシンスペックです．僕が普段使用している 1kg 程度の MacBook Airに対し，感覚的に 2.5kg くらいある Ubuntu マシン（Intel Core i7-3630QM CPU @ 2.40GHz × 8，16GB RAM）は同じプログラムでも 2~2.5 倍程度の計算速度を誇っていました．開発環境と本番環境の PC が異なるのはこのためです．上記の 5 秒という計算時間は，この速いマシンにおける測定値であり，開発機だと 13 秒程度かかります．

システム

UI

UI は全て mfumi2 が Qt で書いてくれました．Qt はマルチプラットフォーム用の UI フレームワークなので，Mac で作成した UI がそのまま Ubuntu で動きました*12．確認していませんが恐らく Windows でも動くと思います．

UI の機能としては，ソルバーや後述する通信部分の設定の他，ジグソーパズルの結果が間違っていた時に手動で修正する事のできるインタフェースも付いています．

通信・分散処理

今回は 3 台の PC を同時に使えるため，分散処理を行いました．一台の PC でサーバを立ち上げ，それに他の二台の PC が接続する形です．まず，サーバ PC が運営のサーバから問題を取得し，ジグソーパズルを解きます（1秒以下で解けます）．次に，サーバ PC がクライアント PC にジグソーパズルの結果を配信すると同時に，自分自身もスライドパズルを解き始めます．サーバ PC が使うスライドパズルのソルバーは1秒以下でそれなりの答えが出せる設定のものであり，サーバ PC はこれを運営サーバに送信することで，ジグソーパズルの解答の答え合わせを行います．

一方，サーバ PC からジグソーパズルの解答を受け取った二台のクライアント PC は，それぞれスライドパズルを解き始めます．二台の PC は微妙に設定の異なるソルバーを用いており，解答が出来次第，サーバ PC に送信します．サーバ PC は解答を受信した後，内部で持っている送信回数や以前の提出解答と照らし合わせ，運営サーバに送信すべきだと判断した時に解答を送信します．

コードは全て mfumi2 が boost.asio を使って書いてくれました．以上の通信・分散処理は自分が現役時代からあると良いなと思っていたもので，今回彼が実現してくれてとても嬉しく思っています．

しかし実際は，サーバのレスポンスがかなり遅く（意図的に遅くしていたらしい？），良い解答が送られるタイミングが後ろにずれ，結果的に時間コストを増大させてしまうという作戦ミスがありました．

readable, sustainable なコード

今回開発を行う上で，コードを極力「読みやすく，保守しやすい」状態を保つことに苦心しました．高専プロコンの競技部門は，長時間の開発であり，当然のことながら短時間でコードを書く TopCoder の Single Round Match や AtCoder の AtCoder Regular Contest などに比べて，高い保守性が要求されます．また，TopCoder の Marathon Match や CodeVS 等の類似した長距離系コンテストとは異なり，3人で暫くの間集団開発を行うことになります．従って，他のコンテスト以上に「読みやすい」ことが要求されます．

コードの可読性と保守性を担保するため，完全に作業領域が分離されていた mfumi2 を除いて，僕と ioryz は度々コードレビューを行いました．本番直前はさすがに時間的制約から突貫工事のパッチワークがコンタミしてしまいましたが，それでも二ヶ月半3人で共同開発を行う上で問題ないレベルの可読性・保守性を保つことが出来たと思っています．

プロジェクトの構成について言うと，今回コードの保守性が高かった理由として，CMake を使っていたというのが挙げられるかと思います．CMake はビルド設定に関する環境依存を吸収してくれるので，Mac で開発したコードを少しの修正で Ubuntu でも動作させることが出来ました*13．また，実行可能ファイル（ main 関数を含むファイル）とソルバーの実装を分離し，更にソルバーの実装もジグソーパズルとスライドパズルで分けたのも功を奏したと思っています．モジュール間の関連性をなるべく減らすのは，保守性を高めるための基本ですが，意外とちゃんと実践出来たことがない人も多いのではないでしょうか．

まとめ（現役生に言いたいこと）

一部は繰り返しになってしまいますが，せっかくの機会なので，高専プロコン OB としての立場から，プロコンに取り組む現役生に向けて幾つか老害感溢れるメッセージを発信したいと思います．以下は競技部門の参加者を想定して書いていますが，多くは自由・課題にも共通して言えることだと思います．*印がついているものは，表彰台を狙うベテランチーム向けです．

役割分担を考える

今回僕達のプロジェクトがうまく回っていたのは，役割分担がうまくいったのが大きな理由の一つだと思っています．ジグソーパズルとスライドパズルで作業を分離しやすい問題でした．例年はここまで作業を大別できない出題も多いのですが，チームのリーダーは個々人の得意分野と能力を考え，メンバーに適切にタスクを振りましょう．全体のクラス構造などの設計は経験豊富な上級生が行って，後輩を指導すると良いと思います．

*事前調査をしっかり行う

先人の知恵は偉大です．関連する分野の技術調査を行いましょう．例えば，今年なら画像処理とパズル，去年なら通信・情報理論，一昨年なら機械学習と統計解析などです．また，先人は偉大ですが，得てしてその知識を理解・修得するのは難しいです．時には，高度な数学の知識が要求されることもあります．更に技術を追っていくと，すぐに日本語の文献は尽き，英語の web ページや書籍，最終的には英論文にたどり着きます．従って，技術的な英語の文章を読める必要も出てきます．海外のチームは読んでいます．これらは難しそうに見えますが，いずれ研究を行うときにも要求される能力です．プログラムを書くのは楽しいですが，学校の勉強もきちんとしましょう．

可読性，保守性の高いコードを書く*14

チームで統一するコーディング規約を作りましたか？命名規則は守られていますか？コードの要所に他人が見ても分かるコメントは書かれていますか？ assert を入れていますか？変数の有効範囲は最小限に留めていますか？やたら長い関数はありませんか？ソースが1ファイルに 1000 行とか書かれていませんか？このやたら深いネストは何ですか？

バージョン管理を行う

git と github の使い方は最低限覚えましょう．昔は USB メモリでコードをやりとりした結果，どれが最新版なのか分からなくなったり，SVN で大量の編集競合に悩まされたりしたものですが，今は素晴らしい時代です．今年は github や bitbucket などでコードを管理・公開しているチームが多々あり，良い流れだと思っています．

*高速化は順序付けて行う

早まった高速化，過度な高速化は禁物です．まずは可読性を優先してコードを書きましょう．プログラムが遅いなと思い始めたら，コンパイラの最適化オプションを確かめましょう．それでも遅かったら，プロファイリングを行って，どの部分に時間がかかっているのかを計測しましょう．全体の2割のコードが8割の実行時間を占めていると言われます．時間がかかっていない所を高速化しても，暖簾に腕押しです．時間がかかっている所を特定できたら，ごく簡単に行える無駄な処理の消去などを行います．重い関数を複数回呼んでいたら，最初の計算結果を使い回せないか考えましょう．重いデータをコピー渡ししている関数があったら，参照渡しに変えます．リソースを保持するクラスは，適切に move を利用しましょう．この段階で大幅な書き換えを行っていはいけません．次に，それでもまだ遅かったら，本当に今その場所を最適化しなければならないのかを考えます．将来的にその部分が丸ごと別のプログラムに差し替えられる可能性があるのなら，今最適化したとしても時間の無駄であるどころか，差し替えをしたくなくなってしまう負の要因になります．どうしても今高速化が必要な場合は，まず計算量を下げられるアルゴリズムがないかを考えましょう．定数倍高速化は頑張っても 200 倍速程度ですが，アルゴリズムを変えてオーダを下げれば，時には 20,000 倍動作が速くなることもあり得ます*15．それでもダメなときは，ようやくコードレベルの最適化を行います．ワーキングメモリを削減したりループの順序を変えることで，キャッシュ効率の向上を狙うのは結構効果があり，変更も比較的容易です．次に，並列処理を考えましょう．並列化はなるべく外のループで行ったほうが効率が上がります．lock は重いので，極力かけないようにします．atomic 操作で済むところに lock を使ってはいけません．事前に計算できる部分はテーブルを作るのも手です．ベクトル演算できる処理は SSE や AVX などの採用も考えます．

高速化を進めるにつれ，次第に可読性が失われてしまうのは仕方のないことですが，それでも適切にコメントを残すなど，可能な限り可読性を保つ努力をしましょう．また，手を入れる前にテストコードを書き，随時単体テストを行いながら高速化を進めていくのが望ましいです．

前日はしっかり寝る

ウチもあまり寝てなかったので人のことは言えませんが，やはり夜はちゃんと寝たほうが良いです．せっかく全国のプログラミング好きな高専生が集まるのに，日中寝ぼけ眼でボーっと過ごしてしまうのは，大きな機会損失だと思います．

コーディングを楽しむ

一番大事だと思います．プログラムは苦しみながら書くものではないです．作品（アルゴリズム）をみんなでつくり上げる過程を楽しみましょう٩( ’ω’ )و

*1:本番前日に Yosemite へのアップデートが入りそうになってとても焦った．

*2:icc (Intel C++ Compiler) が C++14(1y) をサポートしていないので対応言語を C++11 に落とし，大量の constexpr を削除しました．

*3:icc の体験版を入れたけど gcc と実行速度がほとんど変わらなかったので，結局使わなかった．

*4:問題番号4の TATAMI だけはなぜか画像サイズが不正なので解けてないです．

*5:ビームサーチについては，http://spheresofa.net/blog/?p=1044 を見ると視覚的に分かりやすいと思いますが，簡単に説明します．まず，ある状態から次の状態への「遷移」を考えます．例えば，交換操作なら上下左右の4種類，選択操作なら盤面のサイズと同じ種類数の遷移が考えられます．必ずしも1回の交換・選択操作を1回の遷移に対応させる必要はなく，複数回の交換操作をまとめて1遷移として扱うことも出来ることに気をつけてください．最初の状態から可能なすべての遷移を試し，最も低いコストで完成状態にたどり着くことが出来れば，理論的には，スライドパズルの最適解を求めることが出来ます．しかしながら，ある状態の遷移数が n の時，二手先の状態数は n²，三手先は n³，…のように，遷移の組み合わせによって得られる盤面の状態数は指数関数的に爆発していくので，すぐにメモリも計算時間も足りなくなります．この爆発的に増加する状態のネットワークを潜り抜け，うまく目的の完成状態を探索する手法を，総称してメタヒューリスティクスと呼びます．ビームサーチはメタヒューリスティクスの一種で，盤面の良し悪しを定量的に評価する関数（評価関数と呼びます）を定義し，決められたある数（ビーム幅と呼びます）だけ，評価関数の値が良い方から盤面の状態を残していく手法です．この手法は，厳密に最も低いコストで完成状態に辿り着ける保証も，または有限回の遷移で完成状態に辿り着ける保証もありませんが，評価関数が盤面をうまく評価してくれれば，それなりに良い解を出すことが出来ます．ビームサーチは今回の問題のように，遷移に順序依存性がある（例えば，上→右と動かすのと右→上と動かすのでは異なる結果になる）問題の場合に威力を発揮する手法として知られています．

*6:選択操作の行えないスライドパズルである古典的な N-Puzzle には偶奇性が存在し，これはいかなる遷移を行っても入れ替わらないことが知られています．http://www.geocities.jp/m_hiroi/puzzle/parity.html，現代数学2014年6月号，など．

*7:ハッシュ値の更新が差分計算で行える．http://en.wikipedia.org/wiki/Zobrist_hashing 参照．

*8:この手法による多様性の確保は，chokudaiサーチからインスピレーションを得たものです．chokudai 先生に感謝します．

*9:府立のコードに近いですが，このあたりの最適化は府立の方が頑張っています．

*10:練習競技場に出している 4100 回程度の解答は，小さなサイズ用のアルゴリズムを無理やり草原に適用したものです．25 秒程度時間がかかるので，時間コストまで考慮すると大きなサイズ用のアルゴリズムが適しています．

*11:位数 12 の巡回群 $Z_{12}$ ．

*12:でもなぜか仮名が文字化けした．

*13:Ubuntu では g++ を使ったので，現れるエラーの種類が clang と若干異なり，その点で修正を余儀なくされた部分はあります．

*14:但し，保守性を意識するあまり，コーディングが全く進まないようになるのなら話は別です．最初はプロトタイプとして書きなぐって，性能を確認して，後からきれいな形に整形するという流れも有効です．git などを使ってきちんとバージョン管理を行っているのなら，いつでも前の状態に戻れますので，コードが一時的に汚れることを恐れる必要はありません．

*15:https://www.youtube.com/watch?v=gZPMtEujEJc

2014-08-30

C++11でメンバ関数を持つ列挙体のようなものを作る

C++

みなさんナイス C++11 ライフを送っていますか．
ご存知のことと思いますが，C++11 では C から存在した列挙型 (enum) の強化が行われ，強い型付けの列挙型 (strongly-typed enum) が導入されました．これには，enum と整数型の暗黙的な型変換の禁止，スコープ指定の強制，整数型の指定，などが含まれます．

例えば，一般的なじゃんけんの手（グー、チョキ、パー）を表す列挙体を考えます．03 以前の C++ では以下の様なコードになります．

enum Janken
{
    Gu,
    Choki,
    Pa
};

Gu, Choki, Pa は Janken 列挙体のメンバですが，いずれも外の名前空間に属しており，列挙体名を明記することなくそのまま Gu などとアクセス出来てしまいます*1．
11 以降の C++ では以下の様なコードで書く事もできます．

enum class Janken : unsigned char
{
    Gu,
    Choki,
    Pa
};

宣言時に enum class と書くと，強い型付けの列挙体となります．Janken 列挙体の各メンバは Janken::Gu のように，列挙体名を指定してアクセスしなくてはなりません．また，クラスの継承のような記法で整数型を書くと，その列挙体メンバが実際に用いる整数型を規定することが出来ます．この場合は unsigned char を指定しているので，Janken 列挙体の実態は 1 バイトの符号なし整数型となります．

メンバ関数を持たせたい

以上のように機能の強化が図られた C++11 の列挙体ですが，まだ出来ないこともあります．例えば，Janken 列挙体に，自分が勝つことのできる手を返す関数 defeat を追加したいとします．

// Invalid
enum class Janken
{
    Gu,
    Choki,
    Pa

    constexpr Janken defeat() const {
        return Janken((int(*this) + 1) % 3);
    }
};

// 例えばこのように使いたい．hand1 及び hand2 はそれぞれ Janken::Choki, Janken::Pa になる
const Janken hand1 = Janken::Gu.defeat();
const Janken hand2 = hand1.defeat();

しかしながら，列挙体がメンバ関数を持つことは許されておらず，このコードは C++11 や，その後継規格である C++14 でも実行することが出来ないようです．一つの解決策は，特定の構造体やクラスに属していないフリー関数として実装することです．勿論，それが妥当な解決策となる場合は多いですが，メンバ関数として提供するのが自然な場合も多々あるかと思います*2．
この代替手段を提案するのが本記事のトピックです．

列挙体を諦める

早速ですが列挙体を使うことを諦めます．列挙体を使う以上，今の C++ の言語仕様ではメンバ関数を配置することが出来ません．クラスを使います．例えば，Janken 列挙体は以下のように Janken クラスとして実装することが出来ます．

Janken.h

class Janken
{
private:
    int data;

public:
    Janken() = default;
    constexpr explicit Janken(const int data) : data(data) {}
    constexpr operator int() const { return data; }
    constexpr Janken defeat() const { return Janken((int(*this) + 1) % 3); }

    static const Janken Gu;
    static const Janken Choki;
    static const Janken Pa;
};

Janken.cpp

#include "Janken.h"
const Janken Janken::Gu(0);
const Janken Janken::Choki(1);
const Janken Janken::Pa(2);

int を引数に取るコンストラクタと， int へのキャスト演算子が定義されているので，int との型変換を行うことが出来ます．また，int を引数に取るコンストラクタに explicit を付けているので，int との暗黙的な型変換を許しません．これだけでも，普通に使うだけなら充分「メンバ関数を持った列挙体」っぽく振る舞わせることが出来ます．

constexpr にしたい

上記のコードでは，Janken::Gu, Janken::Choki, Janken::Pa はいずれもコンパイル時に値が確定するにもかかわらず constexpr 修飾されていません．これは，constexpr を駆使したコードを記述する上で大きな障壁となります．列挙体として Janken を定義していた時は，列挙体のメンバはコンパイル時定数として扱われるので，これは上記のコードのデメリットとなります．また，各翻訳単位で Janken.o をリンクするまで Gu, Choki 及び Pa の値が決まらないので，コンパイラによる最適化を妨げる要因にもなりそうです．これをなんとかして解決したいです．

まずは，以下のように単純に const を constexpr に変更することを考えます．constexpr 変数として宣言することの出来る型には制限があり，クラスの場合は「リテラル型」と呼ばれるクラスである必要があります．クラスがリテラル型として扱われるためには trivial なコピーコンストラクタを持つなどの条件を満たす必要がありますが，この Janken クラスは条件を満たしているため，めでたく constexpr 変数としてインスタンスを作成することが出来ます．

Janken.h

class Janken
{
(略)
    static constexpr Janken Gu{0};
    static constexpr Janken Choki{1};
    static constexpr Janken Pa{2};
};

Janken.cpp

#include "Janken.h"
constexpr Janken Janken::Gu;
constexpr Janken Janken::Choki;
constexpr Janken Janken::Pa;

上記のコードでは，constexpr 変数は宣言と同時に初期化を行わなければならないため，初期化処理を Janken.cpp から Janken.h に移動しています*3．
上記のコードは一見正しく動きそうに見えますが，実はコンパイルが通りません．これは，Gu などは Janken クラスのインスタンスとして宣言されていますが，これらが宣言されている時点では Janken クラスの定義が終了しておらず，本当に Janken クラスがリテラル型かどうかが分からないというのが理由のようです*4．従って，リテラル型は constexpr な変数を作ることが出来るにもかかわらず，自分自身の static constexpr な定数をメンバに持つことが出来ません．アホらしいですが規格なので仕方ないです．

解決策としては，クラスを親クラスと子クラスに分割し，子クラスのメンバとして親クラスの static constexpr な定数を持つという方法が挙げられるかと思います．自然言語で説明してもわかりにくいので，実際に Janken クラスのコードを示します．

Janken.h

class Janken;

class JankenBase
{
private:
    int data;
    JankenBase() = default;
    JankenBase(const JankenBase&) = default;
    constexpr explicit JankenBase(const int data) : data(data) {}

    friend Janken;

public:
    constexpr operator int() const { return data; }
    constexpr JankenBase defeat() const { return JankenBase((int(*this) + 1) % 3); }
};

class Janken : public JankenBase
{
public:
    Janken() = default;
    constexpr explicit Janken(const int data) : JankenBase(data) {}
    constexpr Janken(const JankenBase& base) : JankenBase(base) {}

    static constexpr JankenBase Gu{0};
    static constexpr JankenBase Choki{1};
    static constexpr JankenBase Pa{2};
};

Janken.cpp

#include "Janken.h"
constexpr JankenBase Janken::Gu;
constexpr JankenBase Janken::Choki;
constexpr JankenBase Janken::Pa;

上記のコードでは，JankenBase が Janken の親クラスとなっており，子クラスの Janken が JankenBase 型の static constexpr な定数を持っています．これらの宣言時には既に JankenBase 型の宣言が終了しているので，無事に constexpr 変数を作ることが出来ます．
JankenBase の各種コンストラクタは private で隠されているので，これらを変数で受け取る時は Janken 型として受け取らざるを得ません．Janken は JankenBase を唯一の引数に取る explicit でないコンストラクタを持っているので，暗黙的に JankenBase 型の変数を Janken 型に変換することが出来ます．このように，なるべく JankenBase の存在は隠蔽して Janken 型の使用を強制するコードとなるように配慮しました*5．
int へのキャスト演算子と defeat は Janken ではなく JankenBase で定義し，継承を通してそれを Janken に取り込む形になっています．これは，Janken::Gu.defeat() のような呼び出しを可能にするためです．

使用例

例えば以下のコードがそのまま動きます．このように，Janken の実態がクラスであるということを意識することなく，あたかもメンバ関数を持つ列挙体のように扱うことが出来ます*6．

#include <iostream>
#include "Janken.h"

int main()
{
    constexpr Janken x = Janken::Gu;
    constexpr Janken y = Janken.Pa.defeat();
    constexpr Janken z = y.defeat().defeat();

    switch(z){
    case Janken::Gu:
        std::cout << "Gu" << std::endl;
        break;
    case Janken::Choki:
        std::cout << "Choki" << std::endl;
        break;
    case Janken::Pa:
        std::cout << "Pa" << std::endl;
        break;
    }
}

残る問題点

Janken::Gu を型推論した時に Janken ではなく JankenBase になってしまう
- auto x = Janken::Gu はコンパイルエラー（JankenBase のコンストラクタが private なため）
- auto& x = Janken::Gu は動くが，xの型は Janken& ではなく JankenBase&（ポインタや右辺値参照も同様）
JankenBase が外から丸見え（インスタンスは作れないけど）

*1:C++03 以前では，列挙体名を指定することすら出来ません．C++11 以降では，以前の列挙体についても，列挙体名を指定しても良いこととなっています．

*2:私事ですが，フリー関数はその置き場所に困るのであまり好きではないです．例の場合は JankenHelper のような名前空間の中，または同名のクラスの静的メンバ関数として配置するのが自然かと思いますが，タイプ量が増えてしまいますし，何か苦肉の策感があるような気がしています．折角なら Janken だけで完結させたいです．

*3:初期化時の括弧が丸括弧から波括弧に変わっていますが，これを丸括弧のままにすると，constexpr 関数の宣言と見做されてしまうため，コンパイルエラーになります．いずれにしてもコンパイルの通らないコードなのですが．

*4:c++ - static constexpr member of same type as class being defined - Stack Overflow

*5:Janken は JankenBase の子であると同時に友達 (friend class) でもあるので，隠蔽されたコンストラクタを呼び出すことが出来るようになっています．また，この friend の宣言を行うために Janken を前方宣言しています．

*6:最後の出力を行っている swich 文は，switch 文も使えるということを示すために入れましたが，出力するだけなら ostream& operator<<(ostream&, const JankenBase&) を定義するのが簡便です．

2013-10-25

MacBook Air を買ったので環境導入してみた

Mac OS X

もう幾つ寝ても Retina Display を搭載した MacBook Air が発売されなさそうなので、買ってしまった！

ディスプレイ：13.3インチ
CPU： Intel Core i7 1.7GHz
メモリ：8GB
SSD：512GB
キーボード：US

という訳でフルスペックモデル。

以下環境導入のメモ。

iTerm2（端末）
- ⌘+Return で Visor っぽく画面上部に現れるようにしてる
- Tab style はなんとなく Aqua がカッコイイ
- カラープリセットは solarized にした
  - なんか色彩心理とかが考慮された目と精神に優しいすごいカラースキームらしい
  - https://github.com/altercation/solarized から iterm2-colors-solarized をダウンロードする
  - iTerm2 の Preferences > Profiles > Colors > Load Presets > Import でダウンロードしてきたのを指定する
  - ls した時のファイル名やフォルダ名の色も solarized にしたかったので Bash - LS_COLORSを設定しよう - Qiita を参考に dircolors-soralized を導入
Dropbox （ファイル共有ソフト）
- .ssh/ とか .vimrc とかは Dropbox の dotfiles/ というフォルダの中に入れて共有しているのでホームディレクトリにシンボリックリンクを置いておく
Xcode 5.0.1 （homebrew を動かすのに必要）
- App Store から入れる
- 起動して Preferences から command line tools をインストールする
homebrew 0.9.5（パッケージ管理システム）
- boost 1.54.0（C++のすごいライブラリ）
- OpenCV 2.4.5（C++のコンピュータビジョン用ライブラリ）
- eigen 3.2.0 （C++の行列計算ライブラリ）
- git 1.8.4.1（バージョン管理システム）
- python 2.7.5（端末から使える簡易計算機）
- wget 1.14（端末から使える簡易ダウンローダ）
- zsh 5.0.2（シェル）
  - zsh-completions も一緒に入れると便利
  - homebrew で入れた実行ファイルは基本的に /usr/local/bin/ に配置されるので .zshrc に以下を書き加えてpathの順番を入れ替えたら良い（ついでに補完ファイルの設定もしてます）

typeset -U path cdpath fpath manpath  # パスの重複を省く指定
path=(/usr/local/bin(N-/) /bin(N-/) /usr/sbin(N-/) /sbin(N-/) /usr/bin(N-/) ${path})
export PATH
fpath=(/usr/local/share/zsh-completions(N-/) ${fpath})

- Google Performance Tools 2.1（プロファイラ）
- cmake 2.8.12 （自動でメイクするやつ）
- coreutils 8.21 （GNU系のコマンドが入る）
  - 前述の dircolors-solarized に必要
- MacVim Kaoriya 7.4.22（テキストエディタ）
  - 標準の formula には無いのでこちらを参考にしました：homebrewを使ってちょっと新しめのMacVim KaoriYaを使おう - かなりすごいブログ
  - Shougo/neobundle（vimのプラグイン管理）
    - Shougo/unite.vim （vimfiler に必要）
    - Shougo/vimfiler （vim がファイルエクスプローラになる）
    - altercation/vim-colors-solarized （vim 用 solarized）
    - itchyny/lightline.vim （vim のステータスバーをカッコよくする）
      - powerline-patched font が必要なので https://gist.github.com/qrush/1595572 から好きなのをダウンロードしてきてインストールする（自分はmenloを使うので Menlo-Powerline.otf ）
  - 以下のように.zshrcにエイリアスを貼っておくと端末から簡単に使えて便利

alias vim="/usr/local/Cellar/macvim-kaoriya/HEAD/MacVim.app/Contents/MacOS/mvim -v"

oh-my-zsh（zshがすごくなるやつ）
- テーマは agnoster にした
  - oh-my-zsh を入れた時に一緒に入るテーマファイル（~/.oh-my-zsh/themes/agnoster.zsh-theme）は文字化けしてておかしいので https://gist.github.com/agnoster/3712874 から自分で引っ張ってくると良い
  - 要 powerline-patched font
  - .zshrc に以下を書いておくと指定したユーザの時にコマンドラインが短くなるよ

DEFAULT_USER=（普段使うユーザ名）

Sublime Text 3（テキストエディタ）
- /usr/local/bin/ に subl という名前で /Applications/Sublime Text.app/Contents/SharedSupport/bin/subl へのシンボリックリンクを置いてるので端末から簡単に使えて便利
- Package Control （Sublime Text のプラグイン管理）
  - SublimeCodeIntel （賢そうなコード補完）
  - Vintagous （キーバインドを vim っぽくする）
Google Japanese Input 1.11 （日本語入力システム）
Evernote 5.4.2 （クラウドノート管理ソフト）
Mendeley Desktop 1.10.1 （クラウド論文管理ソフト）
Skype 6.9 （SMS・通話）
Google Chrome 30（Webブラウザ）
Keynote 6.0（プレゼンテーション作成ソフト）
- 気がついたらポチってた。App Store + クレジットカードの手軽さヤバイ
- 買った時1,700円だったのに今見たら2,000円に値上がりしている
Adobe Photoshop Elements 9.0.3 （画像処理ソフト）
- 高専プロコンの戦利品
SourceTree 1.7.3 （git をGUIから扱える）
BetterTouchTools 0.98 （Windows7 みたいにウィンドウサイズを変更できる）
gnuplot 4.6 （グラフ描画ソフト）
- 端末として x11 と aqua を使いたかったのでまず以下のソフトウェアをインストール
  - XQuartz 2.7.4（X Window System）
  - AquaTerm 1.1.1 （綺麗にグラフを描けるターミナル）
- AquaTerm の実行ファイルとインクルードファイルとライブラリが /Library/Frameworks/AquaTerm.framework/ に入っているので https://github.com/AquaTerm/AquaTerm/blob/master/aquaterm/INSTALL を参考にして /usr/local/ 以下にシンボリックリンクを置く
- https://github.com/mxcl/homebrew/issues/14647#issuecomment-21132477 を参考にして gnuplot の formula を書き換える
- brew install gnuplot --aquaterm --with-x でめでたく完成！
Mac OS X 10.9 (Mavericks) （オペレーティングシステム）
- 入れたは良いけどC++の標準ライブラリファイルが libstdc++ から libc++ に変わっていて libstdc++ の時にコンパイルしたライブラリを使おうとするとリンカエラーを起こすからライブラリ類全部コンパイルし直し＼(^o^)／

2013-03-14

立命合宿2013

競技プログラミング

2013/03/11-13に滋賀県・草津市の立命館大学草津キャンパスで行われた、立命合宿2013に参加して来ました。

楽しかったのでブログ記事を書きます。

Day-1

朝5時に起床して移動開始。陸路と空路を使ったのですが会場に着いたのは13時過ぎだったので移動に相当時間がかかった。

既にチーム編成が行われていたので、主催側の@komi_222さんと同じく遅れて来た@denkounezumiさんとチームを結成。チーム名Hello Worldにしていたら衝突が発生したので1字削ってHell Worldにした。

3時間7問セット。チームメイトの二人には問題の読解をお願いし、自分はA,B,D,Eを通した。最後に想定誤解法でGを通してくれた（制約が甘かったらしい）ので5完で全体の5位を取れた。まずまずの出だし。

懇親会では色々な方と話をさせて頂きました。初対面の人、ICPC以来の人、JOI以来の人など色々な人がいたので楽しかった。

Day-2

僕が今年@todo314さんとICPCのチームを組みたいと思っていて、かつ@k_operafanさんも同学年の自分と一度組んでみたいと思っていたらしいので電通のお二人とチームpasswordを結成。本当にめちゃくちゃ出来る人とチーム組むの初めてだったので足を引っ張らないか本当に不安でした:;(∩´﹏`∩);:

この日は5時間12問セット。少し時間が要るけどやるだけのJを通しました。ルービックキューブの遷移の列挙間違ってなくて良かったけど、別のコードSubmitして1WA、デバッグ出力残して1WAを貰ってしまってまじで申し訳なかった。

その他放物線の長さを求める問題で少し手応えのある積分をしてIを通し（高専の数学の教科書に載っているので高専生有利！！）、その後は@k_operafanさんとEのペアプロをしてました。8WA貰った挙句通らなかったけど。

結果は7完で全体の3位。隣でどんどん問題が解かれていく感覚がすごく新鮮でした。@k_operafanさんぱなくてコード組む時にタイピングの手が止まらないんだよね。止めどない思考。僕もできるようになりたいけど、添字がたくさんあったり少し難しいロジックを組もうと思ったらすぐに思考停止しちゃうんだよなあ。

Day-3

僕のわがままを聞いてもらい、@kyuridenamida、@li_sakuとチームJABEEを組ませてもらいました。久留米、府立、沖縄による現役高専生3人のドリームチーム！！今こそ高専生の底力を周囲の大学生に見せつけるときなのです。

3時間7問セット。僕は基本的に解法を考える作業だけをやってきゅうりとさくにコーディングをしてもらいました。Aは二人がいつの間にかACしてて、CはDAGの最長路求めるだけなのできゅうり＆さくに渡して速攻でAC（First Acceptance）。BもDPできゅうりが解いてくれた。

その後Dの構文解析をきゅうりが頑張っている間、Gの数え上げお姉さん問題を考える。きゅうり2WAを貰うもDをAC。Gは分かってしまえば実装はすごく簡単なDPなので自分がコーディングし、制約の確認不足による1WAの後AC。この時点で1時間程度残ってて、E解こうとしてていろいろきゅうり頑張ってたんだけど時間切れ。

結果5完、全体順位5位（Onsiteだと4位）。Onsiteで上に居たのはそれぞれレッドコーダー（以上）の@japljくん、@rng_58さん、@k_operafanさんを含むチームだったのでこの結果は上々でしょう。きゅうり実装力高いしさくは的確にコーディングのミス見つけてくれてかなり良い感じのペアプロ出来てたので普通に強かった。高専の底力を外に見せつけられたと思います！！チーム組んでくれてありがとうございました。競技プログラミングにおける高専の未来は明るそうなので、これで安心して高専を卒業できます（？）。ほんとうに楽しかった＼(^o^)／

おわりに

立命合宿2013本当に楽しかったです。@Respect2Dさんを始めとする主催・運営の方々、作問して下さった方々、僕とチームを組んでくれた方々、その他合宿でお世話になったみなさん、本当にありがとうございました。また機会があればよろしくお願いします。

2012-12-20

競技において最もコーディング効率を高める飲み物に関する一研究

TopCoder

（この記事はCompetitive Programming Advent Calendar Div2012の20日目の記事として書かれました。）

Introduction
Experiment
Result
Discussion
Conclusion
References

1. Introduction

みなさんは、普段競技プログラミングの大会に参加する際に、何のドリンクを飲みますか？「俺はコーラだ！」とか「シンプルにお茶です」とか、様々な方がいらっしゃるかと思います。しかし、既にマイドリンクを決めている方は良いですが、競技プログラマの中には毎回飲み物のチョイスに困っている方もいらっしゃるのではないでしょうか…？

そこで今回、TopCoderを用いて臨床実験を行い、「どの飲み物が最も競技プログラミングの効率を上げるのか」という大きな問に一つの答えを与え、飲み物のチョイスの道標を作ってみようと考えました。

そこそこ、いや、結構長いですが是非最後までお付き合いいただけると光栄ですヽ(ﾟ∀ﾟ)ﾉ

2. Experiment

実験は以下のルールに従って行いました。

実験期間は12/01から12/20。
1日1つ飲み物を決めて、TopCoder SRMの過去問を解く。
n日目にはSRM(n+199)のDiv2の問題を解く。
Easy、Medium、HardのうちSystem Testを通った問題の提出点の合計値をその飲み物の評価とする。
但し、Easyは250点、Mediumは500点、Hardは1000点を基準とし、設定された点数が基準と異なる場合は満点がそれぞれ250, 500, 1000点になるように補正を掛ける。
制限時間は実際のSRMに基づき75分とする。

Div2にしたのは僕のRatingが現段階で黄色底辺であり、Div1にすると実質Easyの点数だけで順位が決まってしまいそうだと思ったからです。

途中経過は点数は表記せずにSystem Testに通った/通らなかったのみを記載しています。

さて、それでは、競技プログラミングの「最強のオトモ」決定戦（？）、どうぞ！

（なげぇ…と感じた場合は3節のResultは読み飛ばしてもらっても構いません。途中経過長いから結果だけ見たい、という人は4節のDiscussionからどうぞ！）

＊＊！免責事項！＊＊

「俺の愛してるあの飲み物がねえ！」とか「お前の能力が低いだけだろ飲み物のせいにすんな」とか「研究として全く体をなしてない」とか「解く問題違うんだから単純に比較できないだろ」とか「もっと母数増やさなきゃ」等言いたくなるのはごもっともですが、半分ネタのような企画なので、何卒温かい目で見ていただくようよろしくお願いします。。

あと念のため言及しておきますがバックのペットボトルの空とかは毎回全部ちゃんと洗って干してますよ。

3. Result

12/01, Day1

f:id:natrium11321:20121201174341j:plain

初日はコカ・コーラ社の爽健美茶です！。爽健美茶ってお茶のわりに結構好き嫌い分かれますよね。僕は割と好きなんですけど…。

この日はSRM200 Div2です。さて、この日のSRMの結果は・・・？

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

「あれ、何か簡単すぎじゃね…？」

Div2とは言え30分で全完出来てしまうのはマズイだろう…これじゃあ早解きに最適な飲み物検証になってしまうぞ…そもそもDiv2ってここまで簡単だったっけ…？

どうやらTopCoderは昔に行くほど問題が簡単になっていく傾向にあるようで、当時のDiv2はかなり簡単な部類に入ってしまうっぽいです。ちょっとイージーモードを選びすぎた。笑

しかし問題の難易度を出来るだけ統一するために変えるわけには行きません。むしろこれはこれで早解きに最適な飲み物検証ということで良いんじゃないかと開き直ることにしました。

ちなみにこの日の午前中は普通のSRMがありました。A cucumbermanが登場して戦慄した記憶があります。Not Ratedになったけど。

12/02, Day2

f:id:natrium11321:20121202100403j:plain

2日目に選ばれたのは、綾鷹でした。同じくコカ・コーラ社。

綾鷹美味しいよね。よく買ってます。

この日はSRM201 Div2です。さて、この日のSRMの結果は・・・？

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

3つ全部無事に通りました！。Run System Testの文字を押す時って結構ドキドキするよね。

ちなみにこの日はUTPCがありました。僕は「久留米高専の誇りを賭けた最後の共同戦線」というチームの一員として参加してました。

12/03, Day3

f:id:natrium11321:20121203110218j:plain

3日目はまたもやコカ・コーラ社の超有名スポーツ飲料アクエリアス / AQUARIUSです。ポカリより好きです。

ちなみに僕が参加した時の日本情報オリンピック（JOI）の本選や代表選抜合宿では、各競技前にこのアクエリアスかビタミンガードのどちらかが貰えて競技中に飲むことができました。と言うことは、これらの飲料はJOI公認ということで飲むと競技の問題を解きやすくなる…！？期待が高まります。

この日はSRM202 Div2です。さて、SRMの結果はどうだったのでしょう！

Easy	Passed System Test
Medium	Failed System Test
Hard	Passed System Test

Mediumが落ちた！！！

JOI公認アクエリやばいですね。これは今度からはビタミンガードの方を貰うべきなのでは！！？！？！？。！？

12/04, Day4

f:id:natrium11321:20121204104208j:plain

はい。予想出来た方も居るかと思いますが、4日目はコカ・コーラ社のアクエリアスビタミンガードです。JOI公認ドリンクその2です。ビタミンCパワーです。ちなみにJOIの競技中は体を動かさないのにこれらのドリンクを結構飲むせいで頻尿になります。

この日はSRM203 Div2です。さて、SRMの結果は！

Easy	Passed System Test
Medium	Failed System Test
Hard	Passed System Test

！？Mediumが落ちた！！！！！！

悲しみに包まれました。どうやらJOIの公認するドリンクはどちらも飲むとMediumが落ちてしまようです･ﾟ･(つД｀)･ﾟ･　今度からアレですね、爽健美茶と綾鷹を配ったほうがよさそうですね。。ｗ

12/05, Day5

f:id:natrium11321:20121205102742j:plain

5日目はコカ・コーラ社のコカ・コーラです。僕は割とコーディングするときにコーラを飲むのが好きで、例えば去年の高専プロコンの開発の時には毎日1.5Lコーラを2本買って3人で飲んでました。他にも今年のICPCアジア地区予選でも競技会場に1.5Lコーラを持ち込んで飲んでました。

ところでどうでもいいですがこのコーラのパッケージ可愛くないですか！！！

この日はSRM204 Div2です。さて、SRMの結果はいかがだったのでしょう？？

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

久々の全完です。しかもMediumを491.59ptsで通せたのでマジCoolです。さすがコカ・コーラさんだ！！

12/06, Day6

f:id:natrium11321:20121206153526j:plain

さて、コーラと対をなす飲み物といえばアサヒ飲料の三ツ矢サイダーですよね！。三ツ矢サイダー癖がなくて飲みやすいです。なんかペットボトルがスラッとしてて無駄にかっこいいしね。

この日はSRM205 Div2です。さて、SRMの結果は？？

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

全部解けました！しかしMediumにやや時間を取られてしまった＼(^o^)／　コカ・コーラに一歩及ばず…という感じでした。

12/07, Day7

f:id:natrium11321:20121207143417j:plain

さてさて炭酸飲料シリーズが続きます。この日の飲み物はコカ・コーラ社のカナダドライジンジャーエール / CANADA DRY。甘さ控えめな大人の炭酸飲料です。UTPCの時はこれを飲んで参加してましたよお。

この日はSRM206 Div2です。SRMの結果はこちら！。

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

うーん、Hardに時間がかかってしまったなあ。というかReading Hardだとどうしても時間を食われてしまうんだよなあ…。

12/08, Day8

f:id:natrium11321:20121208125005j:plain

お次はまたもや炭酸飲料、コカ・コーラ社のファンタグレープです。ファンタシリーズの中では一番好きです。最近学校の売店にストロベリークリーム味なるファンタが売られていたんですがなんかアレやばかった。

この日はSRM207 Div2です。SRMの結果はこちら！。

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

またもや全完！特にHardを早めに解けたことが高得点につながりました。なんか炭酸飲料系安定してるなあ。

ちなみにこの日はWUPCがありました。WAを貰いまくった結果僕の順位は21位でした。

12/09, Day9

f:id:natrium11321:20121209152515j:plain

長く続いた炭酸シリーズももう終わり、この日はサントリーのなっちゃんオレンジです。今年の高専プロコンでホテルでデスマしてたときはなっちゃんを飲んだりしてました。ICPCの立食パーティーでも飲み物としてなっちゃんが頂けた記憶があります。

この日はSRM208 Div2です。SRMの結果をどうぞ！。

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

EasyとMediumはそこそこ高い点数だったんですけど、Hardの点数が低くなってしましました＼(^o^)／

ちなみにこの日の午前二時に普通のSRMがありました。眠い目をこすって参加した結果Easyを落として0点をもらいレーティングが100近く下がりました☆（ゝω・）v

12/10, Day10

f:id:natrium11321:20121210173422j:plain

さて、フルーツ・野菜つながりで、折り返し地点10日目の飲み物は伊藤園の一日分の野菜と熟トマトです。野菜ジュースとトマトジュース！なんか写真背景にある変なジョーギは気にしないでください。

この日はSRM209 Div2です。食物繊維パワーを得たSRMの結果はいかに！？

Easy	Passed System Test
Medium	Passed System Test
Hard	Failed System Test

Hardが落ちた（悲しみ）

いや違うんですよこれはトマトジュースのせい。EasyとMediumはおいしい野菜ジュースを飲んで解いていたんですけど、これはかなり高得点だったんですよ。Hardにさしかかってトマトジュースを口にした瞬間に思考能力が落ちて、しかもトマトジュース美味しくなくて、やっとの思いで提出したら落ちるという。まあ原因はDPの添字が1つずれていたことなんですけど、確定しました競技プログラミングにトマトジュースは向いていないです！（トマトジュースファンの方がいたらごめんなさい）

12/11, Day11

f:id:natrium11321:20121211150602j:plain

お次はフルーティなグリコのマイルドいちごオーレです。

ところで突然の告白ですが僕はいちごオレが苦手です。なんか飲んでると気分悪くなってくｒ（省略されました）

この日はSRM210 Div2です。SRMの結果は以下です！

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

再び3完し人権を取り戻しました！いちごオレ苦手なはずなのに何故かスコア高いんだよなあ・・・。

12/12, Day12

f:id:natrium11321:20121212141850j:plain

12日目はミルクつながりでダイドーのおいしいミルクココアです。

ココア、美味しいですよね。特に今年の冬のような厳しい寒さの時に飲むと、体が芯から温まります。

この日はSRM211 Div2です。結果はコチラ。

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

全部通ったヽ(ﾟ∀ﾟ)ﾉ

ちなみにこの日は沖縄高専の方々によるJOI模擬予選が行われました。いちおうちゃんと全完して後輩に示しをつけることができました（？）。

それとこの日のふつうのSRMはRegisterが間に合わず見逃してしまいました☆

12/13, Day13

f:id:natrium11321:20121213170024j:plain

13日目はヤクルトです。ヤクルトって初めて自分で買ったんですが結構高いんですね…。

しかし高いだけの価値はあります、特定保健用食品です。生きたまま腸内に到達する乳酸菌　シロタ株(L.カゼイ YIT 9029)の働きで、良い菌を増やし悪い菌を減らして、腸内の環境を改善し、お腹の調子を整えます（パッケージ原文ママ）。1日あたりの目安摂取量1本（65mL）のところを一度に5本も飲むんだから、これは競技プログラミングにおいても期待ができそうですね！。きっとシロタ株が良いバグを増やし悪いバグを減らしてソースコードの保守性を改善してくれることでしょうヽ(ﾟ∀ﾟ)ﾉ

この日はSRM212 Div2です。期待の結果は、こちら！

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

全部通りました！しかも期待通り、どれも高得点でした。更にSample全部一発で通ったんですよ。やはりヤクルトは僕らの見方だった！！

12/14, Day14

f:id:natrium11321:20121214153054j:plain

14日目は、サントリーのボスとろけるカフェオレです。写真が微妙に事後に見えるのはきっと気のせいです。いちごオレよりカフェオレの方が好きです。

この日はSRM213 Div2です。結果は以下のようになりました！

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

全部通りました！こう250 500 1000の文字が次々に緑になっていく様を眺めるのは楽しいですね。Hardはライブラリとして持っていたツェラーの公式が何かバグってて時間を喰ってしまいましたが。

12/15, Day15

f:id:natrium11321:20121215173154j:plain

この日はコカ・コーラ社のイリーイッシモ　エスプレッソブラックです。無糖です。コーヒー美味しいですよね。以前は先輩が研究室に豆を挽く機械を持ってきてて、時々挽きたてを飲ませてくれたんですよ(・ω<)

この日はSRM214 Div2です。カフェインパワーや如何に？？？

Easy	Passed System Test
Medium	Passed System Test
Hard	Failed System Test

Hardが落ちた悲しみ…。何故でしょうコーヒーが無糖だったからか、はてまて問題がReading Hardな文字列処理だったからか。しかし頭を使うプログラミングにコーヒーは確かにあまり向いてないかもしれません。

12/16, Day16

f:id:natrium11321:20121216174158j:plain

キリンの午後の紅茶　ストレートティーです。

最初に断っておきます、僕は紅茶が苦手です:;(∩´﹏`∩);:

この日はSRM215 Div2です。

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

コーヒーHard落ちたのに紅茶全部通ったのは何故だ（憤慨）

やっぱ紅茶が甘かったからかなぁ…。でも紅茶は苦手です・・・

ちなみにこの日はJOI予選がありました。後輩たちが予選突破してくれると良いなあ。あとAtCoderのARCもありあましたね。DPの実装で死んでいたけど！。

12/17, Day17

f:id:natrium11321:20121217181220j:plain

終わりも近い17日目はカルピスです。紅茶が残ってるように見えるのは気にしない。

どうやらカルピスを飲むと記憶力が上がるらしいですよ。この記事を見てカルピスの原液を買おうかと一瞬思ったんですが流石にやめましたｗ。普通のカルピスウォーターでも効果はあるはず。記憶力が上がれば、あれ？制約なんだっけ？とわざわざ問題を確認しにいく手間が省けますね。

この日はSRM216 Div2です。さて、記憶力を伸ばした結果は…？

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

おぉー全部通りました。実際に記憶力が伸びたかはちょっと分かりませんが、少なくとも飲んで良い効果はありそうな気がします（プラシーボ）。

12/18, Day18

f:id:natrium11321:20121218154323j:plain

18日目はみんな大好きRed Bull。翼を授けます。デスマのオトモです。一本200円します。

缶の側面には「RED BULL^® Energy Drink （エナジードリンク）：パフォーマンスを発揮したい時のために開発されました。アルギニン、カフェイン、ナイアシン、パントテン酸、ビタミンB₆・B₂・B₁₂入り微炭酸飲料。Red Bullは、トップアスリート、多忙なプロフェッショナル、アクティブな学生、ロングドライブをする方など、世界的な評価をいただいています。」と書いてあります。これは本当に期待が高まります。

この日はSRM217 Div2です。無事に翼を得て羽ばたいていけたのでしょうか・・・？

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

点数は1600点近い！！Mediumが600点満点とはいえレッドブルの効果は伊達では無さそうです。これはかなりの高順位を期待できそうです。しかもHardの点数がほぼ777.77点でかなり良い感じですね。いいことが起こりそう！

12/19, Day19

f:id:natrium11321:20121219131631j:plain

！？なんでしょうこれは。

水のように見えますが、よく見るとラベルには「探検ドリランド」と書いてあります。

はい。これはミネラルウォーターです。しかもICPCのエクスカーションでグリーに企業見学に行った時に貰ったものです。物持ちよすぎ…ｗ

まあね、グリーが作っている（？）くらいの水なので、きっとプログラミングにおいて高いパフォーマンスを発揮することが出来るに違いありません！。

取り組むSRMはSRM218 Div2です。さて、結果は・・・？

Easy	Passed System Test
Medium	Passed System Test
Hard	Failed System Test

Hard落ちた／(^o^)＼

GREEさん・・・

12/20, Day20

今日です。最終日です。

最終日に選ばれた栄えある飲み物は・・・

f:id:natrium11321:20121220181712j:plain

シャンメリーです！！！！！！！

まだ早いですけど、クリスマス近いですし？？？

シャンパンを模した子供用飲料を飲んでクリスマス気分を味わうのも粋でしょう(*´∀｀)

ちゃんとグラスに注いで飲みましたよ～

f:id:natrium11321:20121220182931j:plain

さて、取り組んだのはSRM219 Div2です。最後に有終の美を飾ることは出来たのでしょうか！

Easy	Passed System Test
Medium	Passed System Test
Hard	Passed System Test

おーっ！華麗にHardのDPを通すことができました！！

4. Discussion

さてさて、実験結果を集計した結果はこちらになります！。

f:id:natrium11321:20121220193725p:plain

栄えある1位はファンタグレープとなりました！以下、2位シャンメリー、3位コカ・コーラと続きます。

高パフォーマンスを謳ったRed Bullやヤクルトが上位に来ているのは流石ですね。お茶類も割と良い順番に居ます。逆に順位が低いのはアクエリアス系、コーヒー系といったところでしょうか。

ちなみに最も早く解くことが出来たのはコカ・コーラの24分27秒、逆に最も解くのに時間がかかったのはなっちゃんオレンジの62分16秒でした。

ちなみにせっかく色々データが取れたので、それぞれの飲み物について、横軸に各成分（エネルギー・たんぱく質・脂質・ナトリウム等）、縦軸にTopCoderの得点率を取ったグラフを作ってみたりもしたんですよ。そうしたらたんぱく質、脂質、ナトリウムは割と無相関に見えたんですが、エネルギーと得点率が若干面白いグラフになったような気がしたので貼り付けておきます。

f:id:natrium11321:20121220202602p:plain

トマトジュースと野菜ジュースはそれぞれ別に計算しました。またシャンメリーは栄養表示がなかったので省いています。上のグラフ、エネルギーが低い飲み物は低スコアから高スコアまで散らばっていますが、高い飲み物は安定してそこそこのスコアを出せているように見えませんか？？エネルギーと糖質量はほぼ比例します。と言うことは、やっぱり競技のときは甘い飲み物を飲むと脳の栄養になって、高パフォーマンスを叩き出せると言えるんではないでしょうか。

5. Conclusion

今度から競技プログラミングの大会にはファンタグレープまたはコーラを飲みながら参加しましょう。シャンメリーでも良いですがクリスマス前後以外は季節感の無いやつだ…と思われるのでオススメはしません。

6. References

日本コカ・コーラ｜商品情報、http://www.cocacola.co.jp/products/、2012年12月17日閲覧
クリスマス　シャンパン　ノンアルコール - Google 検索、https://www.google.co.jp/search?q=クリスマス　シャンパン　ノンアルコール、2012年12月01日閲覧
ワイングラス　持ち方 - Google検索、https://www.google.co.jp/search?q=ワイングラス　持ち方、2012年12月20日閲覧

2012-10-16

全国高等専門学校プログラミングコンテスト有明大会

競技プログラミング高専プロコン

第23回全国高専プログラミングコンテスト・有明大会に、競技部門のメンバーとして@nikollson、@HETARE09と参加してきました！

結果は…
一回戦4位/6チーム→敗者復活戦4位/6チームでしたorz（通過出来るのはいずれも上位2チーム）

問題内容

大・中・小3種類の大きさのサイコロが、テーブル上に沢山あります。サイコロ以外の物もあります。全体のサイコロの重さも教えます。それぞれの大きさのサイコロがいくつあるのか頑張って数えてね！
というルールです。
超端折りましたが、詳細なルールはこちら(PDF)の7ページ以降に書いてあります。興味が有る方は御覧ください。

あと割と大事なQ&Aで、こういうのもあります。サイコロは自然に散らべ、手で並べたりはしないらしい。

例えばこんな感じです。（クリックすると拡大します）

取り組んだこと

4月

問題が公開される。絶望する。

というのは置いておいて、測定方法をどうするかまず考えました。

機器	分かるもの	メリット	デメリット
カメラ	画像	機器の用意が容易、既存の画像処理アルゴリズムが使える	表面の情報しか読み取れない
ソナー	奥行き	超音波を用いることで表面の凸凹が分かる	機器が高そう
Kinect	奥行き	レーザーを用いることで表面の凹凸が分かる	精度が全然出なさそう
X線CT	サイコロの中の構造	全部のサイコロが見える	X線作業主任者免許保持者がいない
扇風機&風速計	風の流れ	頑張れば山の中の構造が分かる？	流体力学こわい
ヒーター&サーモグラフィ	温度分布と熱伝導率	？	最悪発火する
手動	サイコロの個数	環境変化に頑健	精神状態に左右される、時間内に数えられる量に限度がある

この中で現実的なのはカメラで画像撮ってがんばるくらいですよね。
ということで画像処理に決定。
複数枚の画像撮ってサイコロのマッチングしよう、特徴量抽出がどうの、エピポーラ幾何がどうの、オプティカルフローがどうのって話が賑わっていた記憶があります。

5月、6月

自分は編入試験の勉強で全く動けませんでした。
他の2人にはサイコロを各大きさ500個ずつ購入したり、サイコロを撒くテーブルを作ったりしてもらいました。
テーブルに敷くピンク色のカーペット、4枚で足りるのに沖縄高専は200枚も買ったりしたらしいです！。びっくりですね。

7月

ようやく本格的に動き出しました。SIFTとかSURFとか使えるのかなーとか色々やってみたり…

調査が一段落した後、取り敢えず1枚の画像から見えるサイコロの個数を計算するプログラムを作成しようとしました。
まずはその前段階としてサイコロの目を検出しようと思い

画像にCannyのアルゴリズムを用いてエッジ抽出する
エッジ情報を、同じ楕円を構成しているもの別に頑張って分ける（実際はただの8方向隣接ピクセルを見て繋がってるピクセルにBFSするだけ）
最小二乗法を用いて楕円の方程式のパラメータを算出する

という感じでしました。実装にはOpenCVを用いました。
上記の実装は主にhetare09君にやってもらい、自分は主に幾何ライブラリを作りました。ベクトルや直線や円や楕円を扱えます。結構多機能！
作った幾何ライブラリはhttp://ideone.com/ZI2Lgから見られます！。

8月

nikollsonが1ヶ月東京に行ってしまい居ませんでした。
hetare09君が後半半月SuperConやJOI夏合宿に行ってしまい居ませんでした。夏合宿うらやま！！！！

その間自分は、Canny法によるエッジ抽出がサイコロの目の反射光に弱いとか色々あったので、エッジ抽出の方法を独自に考えたりしました。説明はけっこう面倒なので省きます。隣接ピクセルとの差を見てます。
論文を漁ると最小二乗法はあまり精度が良くないらしく、「最尤推定」とか「超精度最小二乗法」とかあるらしかったんですが、なんかそういうのを新しく勉強する・実装するのに工数を割きたくなかった（本質ではないと思った）ので諦めました*1。

9月

前半は定期試験があったので取り組みませんでした。
後半はnikosllonが工場見学旅行でいませんでした。

hetare09君には、「僕の考えた最強のエッジ抽出法」を使って楕円抽出の精度向上をやってもらっていました。全然最強じゃないし、全然エッジ抽出法じゃないけどね！。

一方自分は、抽出した目情報から、「同じサイコロの同じ面に属している目であるだろう」とおもわれる目同士を線で結んでみるプログラムを作ったりしました。「同じサイコロの同じ面に属している目であるだろう」の判定は、二つの楕円の中心座標を合わせて重ねた時にその共通部分の面積が全体に占める比率を頑張って積分して求めてどうのこうのしてました。
楕円同士の交点計算とか、死ぬかと思ったよ。まじで。

最終的にこんな感じになったりしました！

10月

自動でカウントするのを諦めました☆

カメラで画像を撮った後コンピュータに取り込み、マウスとキーボードを用いてひたすら人力で数えるとってもアナログな手法に切り替えました。例年久留米は基本全自動でやってきていたので、本当は最後まで人力に頼りたくはなかったのですが、何らかの方法で見えるサイコロの個数を正確に数え上げることができても、結局真のサイコロの個数は結局分からず推測せざるを得ないため、あまり意味が無いと思ったためです。画像処理をこのまま続けても実りそうになかったし、そこに工数を割くぐらいなら推測の方に力を入れたかったので。
しかし手動で行くと決まったからには、インタフェースは徹底的に。まずはカウント支援ソフトを作りました。なんと1台のPCにマウスを2台接続して2人が同時にカウントできます！すごい！
あとは指定領域に指定した割合でサイコロのカウントをコピペする機能とかいろいろつけました！。C#さまさま。
クロスケーブルも買ったんだけど結局コンピュータ間の通信機能は間に合いませんでした。。

久留米高専では、恐らく本戦では推測の精度で順位が決まると考え、サイコロの数や比率をいろいろ変えたサイコロ画像180枚に対して、「サイコロ数え上げパーティー*2」を行い、部員達の力を借りて見えるサイコロの数を大中小それぞれ数え上げ、それを基に「見える大・中・小サイコロの数・重さ・比率」を基底（入力変数）として重回帰分析を行い係数を決定し、本番に臨むことにしました。重回帰分析はExcelで出来るんですけど不便だったので最初はmatlabでプログラムを作成し、それを後にC++に移植しました。matlab便利すぎ・・・

こんな風にデータまとめて

こんな風に分析しました。

10月に入ってからは自分とhetare09君でほとんど毎日Excelとにらめっこしてました。「エクセルコンテスト」「確率統計コンテスト」「データマイニングコンテスト」とかそんな名前のコンテストに参加してる気分でした。それでも精度は少しずつ上がってきて、本番直前に行った予行演習では誤差が大0、中2、小20くらいまでは縮めることができました。（小サイコロは本当にずれるので、最大で誤差率±30%は普通にあったかと思います）。
ところで、この時点で行なっていることをよく考えると

手動で見えるサイコロの数を数える
事前に重回帰分析により算出したパラメータを用いて、真のサイコロの個数を推測する

ですよね。つまり、「見えるサイコロの数」をインプットとして与えると、「真のサイコロの数」がアウトプットで返ってくる。これ、よく考えると、別にインプットを「見えるサイコロの数」にする必要はないように思えませんか？例えばコンピュータで抽出可能な量・・・何らかの特徴量だとか、サイコロの目の大きさの分布だとか・・・
その事実に本番1週間くらい前に気がついた久留米高専は一部自動に翻り、SIFTの検出ウィンドウの大きさの分布を使ってみたりーだとかサイコロの目の大きさの分布を使ってみたりーだとかを主にnikollsonがしました。サイコロの目の大きさは、ヒストグラムを作ると中サイコロと大サイコロの所で結構くっきりとピークが現れる二峰性のグラフになっていました。こんなにくっきり現れるのか・・・と割と感心してました。後はピークの間の谷のところで2つに切って大と中それぞれの大きさの目の数だと思われる数値を得てそれを入力にしてまた重回帰分析すればいいよね（・∀・）（小サイコロは重さから求めます）
それで前述した180枚の画像データに対して、目の大きさのヒストグラムを作ってみたりしたんですが……同じ個数の山でも、撮った角度等の要因で容易に割合が変わってしまうことが発覚してしまいました。これでは分析できないよ・・・えーん・・・というわけで一度翻った自動解法は再び下火になってしまいました（フラグ）。

そして、そのまま、本戦に挑むことに。

大会本番

予行演習

なんと、サイコロを撒いた後、手でサイコロの山をならしていました！。「サイコロは自然に散らべ、手で並べたりはしない」と言ってたのに…と思って2度くらい運営に質問と抗議に行きました。結果、サイコロには極力手を触れないことになりました。
久留米の予行演習は上手く行きました！。堂々の1位。

1回戦

一眼レフカメラのバッテリーが切れました！。
目視で頑張りましたが限界があった。敗者復活戦へ。

1日目夜

1日目で運営のサイコロの撒き方が分かったので、その撒き方で30枚の写真を撮り重回帰分析を行いデータを作り直しました。それと色々な高専から1回戦の画像データを譲って頂き、それらについても分析をかけました。快く譲って下さった東京産技高専、沖縄高専、一関高専（それと協力して下さった福島高専）の方々ありがとうございました。この場を借りてお礼申し上げます*3。

敗者復活戦

負けましたorz。
敗因は割とはっきりしていて、「実験データとの明らかな不整合」です。1日目夜の実験では、小サイコロは多くても全体の35%程度しか見えないし、実際にみんなから集めた1回戦のデータはどれもそうでした(一番ひどいものでは156個中20個、割合にして13%程度しか見えていないものもありました)。それが敗者復活戦では何故か、小サイコロが全体の60%は見えていたので、かなり大きめに答えが出てしまっていました。何故でしょう…午前中に行った競技なので、大中小のサイコロが混ざらずにバケツの中に入っていて（小サイコロが最下層）、大中のサイコロが転がった上に少サイコロがぱらぱらと降り注ぐことで飛び散る数が増えてしまったのかなとかも思いましたが、実際のところどうなのかは分かりません。あとやっぱ運要素はありますね。しょうがないね。

自動か？人力か？

twitterの#procon2012タグ等でだいぶ荒れていましたね。
自分は、途中で手動に切り替えたことを後悔していませんし、実際に決勝に進んだチームは6つ全て手動でしたから、妥当な判断だったと思っています。大会に参加している以上は勝ちを取りにいきたいので。もちろん出来れば全部自動でやりたいですが、やっぱりどうしても人間の大局観*4やパターン認識力*5には、少なくとも今の自分では勝てるプログラムを作るのは厳しいです。問題解決の一手段として、時には潔く一部の仕事を人が請け負ってもいいんじゃないかとは思います。

今回の久留米高専の方針は、その変化まで含めて大阪府立高専と近いものだったようです。もっとも府立が手動に切り替えたのは大会前日らしいので、そのタイミングはだいぶ違いますが…。画像処理だけで答えを出そうとした高専も幾つかあると思うんですが、例えば沖縄高専は目の大きさのヒストグラムと重さから大中小のサイコロの分布を自動で算出し、かなりの精度を出していたようです（あれ？どこかで聞いたような…）。

高専プロコン競技部門として

今年の問題は確かにルールとして少し耐え難いものがありました。曲がりなりにも「プログラミングコンテスト」な訳ですから、ちゃんと優秀なプログラムを作成したチームが勝てるようなルールにして頂きたいですね。こんな状況を続けていたら、多分見放されちゃうよ？。決勝進出チーム全てがが手動解法に頼っていたというのは、問題作成時点で想定されてなかったのでしょうか？閉会式の審査委員長の言葉でも競技はノータッチだったし…。

どんなルールになっても、勝ちは狙いに行きますけど。でも今年もアルゴリズム考えてSSE書いてOpenMP使ってIntel コンパイラ使ってガチガチに高速化して、俺つえーしたかったなあ。最後だったし。

所感

優勝は宇部高専の方々でした。おめでとうございます。宇部は去年、1日目の夜にうちの解法をコピーして翌日準優勝したという猛者です。宇部さんやばすぎでしょ。
今回の大会は会場が大牟田だったので久留米から近く、部活のOBや後輩が沢山来てくれました。先生や友達からもfacebook等で応援メッセージをたくさんもらいました。だからせめて1回は勝ちたかった、かっこいいとこ見せてやりたかった…。運要素の強い競技内容とはいえ流石に情けなくなります。先生なんて「最強の布陣*6」とまで仰って下さったのに。うぐぅ。
nikollsonとhetare09君はまだ来年もあるので、優勝旗を(ないけど)是非宇部から奪還していただきたいです。もちろん府立や沖縄にも負けない。あと自由・課題も、久留米今は弱いけど、頑張って欲しい。
来年の開催地は北の大地旭川、絶対見に行きます。

久留米黄金時代、また作ろーぜっ

*1:最尤推定は研究室のゼミでやっていたんだけどね！。

*2:副題は「みんなも数え上げお姉さんになろう！」。

*3:大阪府立高専からも貰いたかったけど彼ら競技終了後懇親会も出ずにすぐに帰って寝てたんだよねえ…。

*4:平成22年度競技部門、水瓶の恵み。

*5:今年の競技。

*6:今まで3人全員がJOI春合宿参加者だったことはないんだけど、今年は自分とnikollsonはJOI春合宿参加したし、hetare09君は春合宿参加相当の実力があった（人為的ミスで失敗）ためだと思う。

2011-12-28

高専プロコン競技部門の学校別受賞回数一覧

高専プロコン

高専プロコン競技部門の学校ごとの受賞回数一覧表を作ってみました。
こちら(Google スプレッドシート)に完全版をアップロードしています。より上位の賞の受賞回数が多い順にソートしています。

1度でも優勝したことのある学校だけ抜き出してみますと、以下のようになりました。

学校名	優勝	準優勝	第三位	特別賞
久留米	4	1	3
大阪府立	3
木更津	1	1		1
小山	1	1		1
宇部	1	1		1
石川	1	1
秋田	1	1
東京	1		2	1
呉	1		1	2
有明	1		1
神戸市立	1			1
仙台(名取) (旧宮城)	1
仙台(広瀬) (旧仙台電波)	1

優勝回数だけ見ると、久留米と大阪府立の2校が圧倒的に抜きん出ていますね。
それぞれ、久留米は第9回明石大会(1998年)、第16回米子大会(2005年)、第17回茨城大会(2006年)、第22回舞鶴大会(2011年)で、大阪府立は第14回東京大会(2003年)、第15回新居浜大会(2004年)、第20回木更津大会(2009年)で優勝を飾っています。
競技部門が始まったのは第5回の富山大会からなので、合計18回開かれています。そのうち久留米と府立の優勝回数だけで合計7回なので約4割はこの2校がかっさらってしまっています( ^ω^)

久留米は今回の舞鶴大会で勝って、なんとか府立に勝ち越しという感じですね・・・。
来年以降、府立強くなってくる感じがしますが、是非とも勝ち逃げしていきたいと思っている所存でございます。ｗ

目次

NAPROCK とは

競技ルール

開発環境

基本的なアプローチ

ジグソーパズル

スライドパズル

小さなサイズ用 (AI名: kurage)

評価関数

多様性の確保

大きなサイズ用 (AI名: dragon)

操作列の最適化

高速化

評価関数の差分計算

並列化と lock-free

解答復元

テンプレートと branch

速いマシン

システム

UI

通信・分散処理

readable, sustainable なコード

まとめ（現役生に言いたいこと）

役割分担を考える

*事前調査をしっかり行う

可読性，保守性の高いコードを書く*14

バージョン管理を行う

*高速化は順序付けて行う

前日はしっかり寝る

コーディングを楽しむ

メンバ関数を持たせたい

列挙体を諦める

Janken.h

Janken.cpp

constexpr にしたい

Janken.h

Janken.cpp

Janken.h

Janken.cpp

使用例

残る問題点

Day-1

Day-2

Day-3

おわりに

1. Introduction

2. Experiment

3. Result

12/01, Day1

12/02, Day2

12/03, Day3

12/04, Day4

12/05, Day5

12/06, Day6

12/07, Day7

12/08, Day8

12/09, Day9

12/10, Day10

12/11, Day11

12/12, Day12

12/13, Day13

12/14, Day14

12/15, Day15

12/16, Day16

12/17, Day17

12/18, Day18

12/19, Day19

12/20, Day20

4. Discussion

5. Conclusion

6. References

問題内容

取り組んだこと

4月

5月、6月

7月

8月

9月

10月

大会本番