高専プロコンとU-22プロコンに参加した話

2017年10月1日に開催された「U-22プロコン」と，10月8日～9日に開催された「高専プロコン（競技部門）」に参加しました．
もう3月なのでいまさら感がありますが，まだ年度は変わってないのでセーフ．

U-22は最終審査会に十数組（チーム・個人）しか呼ばれず，よく知らない人が多そうなので，どんな手順を踏んだかを中心に書きます．
高専プロコンは本選参加者が多く，どんなコンテストか説明する必要もなさそうなので，開発の話を中心に書きます．

高専プロコン（競技部門）編
競技の内容はこれ↓

みたいなパズルをMDFで作って用意するから，解く速度を競いましょうね．ピースの形状情報や配置情報が配布されるので，使いたかったら使ってもいいよ．（ただし減点）
みたいな感じ．
詳しくは公式の募集要項を読んでください．
第28回大島大会(2017)

4月
問題が公開されたので考察を始める．
部活でメンバーを募集する．が，集まらない．

5月
メンバーが集まるより先に応募書類が書けてしまう．
見かねた先生が部員に声掛けをしてくれた．
下旬にメンバーがそろって初MTG．
とても優秀なR氏がいるので心強い．
形状情報から解を出すソルバを書いて，余裕があれば画像処理で形状情報を推定しましょう．という方針になった．

6～7月
1週間単位で「実装→実験→考察→MTG」を繰り返すことにした．
R氏はQRコードの認識とかハッシュクラスとかをコツコツやってくれ，他のメンバーは画像処理や本番用ツールの準備をしてくれていた．
僕は1週間ごとに次のようなことをしていました．

• 簡易問題エディタ兼ビューワの作成
  • 実験するのに必須なので，多角形の形状・配置データを編集できるGUIツールを作りました．メンバーの開発環境がバラバラなため，ブラウザさえあれば動くようにJavaScriptで書いています．

• 多角形クラスの実装
  • 多角形の当たり判定，回転，同一判定等が必須なので，多角形クラスを作りました．凹凸多角形の内外判定はMirrorLabyrinth | Aizu Online Judgeの解説スライドを参考にしました．

• 貪欲ソルバの実装
  • 問題ファイルを読み込み，枠の中に置けそうなピースを置いて解答ファイルを書き出すだけのソルバを書きました．

• 横に並べていくソルバの実装
  • 横方向に並べていけばそのうち完全解が出るし，どこまで探索が進んだか分かりやすい．

• 同形ピースの順序付け
  • 全く同じ形状のピースが複数ある時，組み合わせの数がドエライことになるので事前に同一判定をして，使用順序を決めてやりました．

• ハッシュ関数
  • 同じピースを使って全く同じ形状を表現できる配置パターンが何通りもあるとドエライことになるので，ハッシュ化して同一視することにしました．
  • ハッシュテーブルは，グリッド座標上で2点A，Cを選んだ時に線分AC上に乗る任意のBに対して，常にhash(A，C)=hash(A，B) xor hash(B，C)が成り立つようにしました．（R氏がやってくれました．）
  • 枠にピースを置く度に「置いたピースの全ての辺の位置に対応するハッシュ値をxorし，ピースのidに応じたハッシュ値をxorする」ことでハッシュ値を更新できます．1ピース最大16辺なので早い．
  • このあたりで50ピースくらいの問題が解けるようになりましたが，ケースによっては数十分かかっていたので探索の効率を高めていくことにしました．

• 縦に並べていくソルバの実装
  • 横に並べるソルバでは，行の端に到達するまでに大量の探索を行っており，これを縦向きに変えることで数分程度に改善されました．（横100グリッドに対して縦は64グリッド)

• 探索木の出力機能
  • より詳しく実験するために，探索木ファイルと探索した全てのノードを出力できるようにしました．

• 組み合わせの少ない角に置く
  • 探索木を確認すると，「将来的に完成しないが探索がどんどん広がる」という良くない状況が見つかりました．
  • そこで，盤面内の180度未満の角を全て調べ，埋められる組み合わせの最も少ない角から探索させることにしました．探索木が広がらないように探索するため，効率がよくなります．とはいえ毎回残りのピースで検討していては大変なので，任意の角を埋められるピースの組み合わせを事前に列挙し，その値を用いました．
  • これにより，50ピースの問題を数十秒程度で解けるようになりました．

• 組み合わせの遅延評価
  • 実験していると角の組み合わせの事前列挙に時間がかかっており，そのほとんどが参照されることなく探索を終えていることが分かりました．そこで，組み合わせの数を初めて参照したときにリストを作成するようにしました．（これを遅延評価と表現するのかはよく分かりません．）
  • これで50ピースの問題が1秒くらいで解けるようになりました．

8月
前半は学会で消えた．
U-22に出る気になり，後半も消える．

9月
U-22との平行作業になって大変．
実際に答えを見ながら枠にピースを埋めると，ピースを探す作業が大変なことが分かった．（僕は配布されたパズルには慣れ切っていたので，無関係な同級生に解かせて検証した．）そこでR氏に「ピース群を撮影し，解答データと照らし合わせてピースを探すツール」の実装をお願いし，自分はスキャン画像からピースの形状を推定するツールの実装を始めました．
いろいろやった結果，人間が1ピース数秒ずつかけて確認すればだいたい形状推定が行えるようになりました．
が，

• 50ピースを確認するのに5分，並べるのに5分かかるとすると10分(+α)かかってしまい，最短試合時間の10分で間に合わない．
• ピースの1辺が最短20mmで最大誤差が2mmらしく，加工誤差が大きいと形状推定に大きな影響が出る．前回大会ではパズルが仕様通りに加工されていないという抗議があった気する．
• スキャン後に形状情報利用にシフトすると，スキャン時間分不利．

これらを踏まえて，形状推定は諦めました．（諦めたと言っても形状推定をしてくるのは1チームだけだろうから，ソルバの速度でそれなりに戦えるだろうという考え．）

10月
U-22終了後，ピース配置補助ツールの開発に合流．ピースを撮影すると，解答データと形状マッチングしてくれるツールを完成させる．
↓ツールのイメージ．裏向きになっていたらそれも表示してくれる．

前日
現地入り．
調整してホテルで練習をする．

本選1日目

• 練習
  • 机が木目調で，板の認識に悪影響．前回大会では机に白い紙が貼ってあったので，今年もそうだと思いこんでいた（確認を怠っていた）．
• お昼休み
  • 机を白くしなければ補助ツールが使えないので，コンビニにコピー用紙を買いに行く．
  • R氏は布地を扱ってそうな店まで行っていた．
• 一回戦
  • コピー用紙を机に敷き詰め，その上に板を置いたらうまくいったので一安心．
• 試合後
  • ホテルに戻って動画配信を見直し，他のチームの様子を探ると2人くらいでピースを埋めていることが分かる．うちは1人で埋めていたので，ここを改善すれば入賞では？と話し合う．
  • 解答画面でピースを選ぶ際にマウスを使っており，そのままでは2人で操作できないため実行機をタブレットPCに変えて解答画面をタッチできるように仕様変更．
  • 本当は3人よって阿修羅の腕になりたかったけれど，3人よるには空間が狭すぎるので断念．

本選2日目

• 準決勝
  • タブレットPCの操作感を確かめる．
  • 慎重にやってもいいタイムが出る．使いやすくていい．
• 決勝
  • youtu.be
  • 練習時間を削って仕様変更をしたためか操作ミスが発生し，それなりに時間を失ってしまう．負けを察し，緊張がとける．リラックスしてモリモリ進む．残り数ピースになっても拍手が聞こえてこないので「もしかしてワンチャンあるのでは？」とか考えてしまい，再び緊張する．が，なんとかなった．
  • 他のチームを見守る．

結果は準優勝で，およそ予想通りなので満足です．
問題設定も各チームが実力に応じたゴールを選べていい感じ．

振り返ってみると「検証して部分的に改善」を繰り返していて，あまりアルゴリズムしてないですね．競技部門ではアルゴリズムに特化するより，総合的に能力を高めたほうがよい（？）

U-22プロコン編
U-22プロコンは22歳以下の個人またはチームで応募できるプロコンで，ジャンルは問いません．ユルすぎない？

8月中旬
学会も終わったし，応募してみるか．と思って温めていたネタを書き始める．

8月24日
締め切り当日なことに気づく．（26日が締め切りだと勘違いしていました．）
2分までの動画を添える必要があるのに，時間がなくて40秒くらいの動画しか撮れなかった．
必要書類だけでなく追加資料も提出できるようなので，手法について書いた論文を添付した．（作品に対するパンフレットとかが想定されているのだろうか？）

9月上旬
「お前のプログラム，動画通りに動かないぞ．」みたいなメールが来る．
（大量の応募作品全部確認しているのか・・・．）
動画が説明不足だったことを謝罪し，使用方法に関するメールを送る．

9月上旬
一次審査に進んだ作品一覧に名前が載っている．
高専プロコンの方も忙しかったので，ヤバイのでは？みたいな気持ちになりつつ喜ぶ．

9月中旬
一次審査の結果がweb公開より数日早くメールで来た．うわー！
よく考えると20日に書類締め切りなので，19日のweb公開より早く連絡するわな．
資料が多くて大変．
資料には秋葉原までの交通費を出します．近くのホテルを用意します．みたいなことが書いてあって，U-22最高！大好き！となった．
スライド発表をする必要があって「イケイケスライド書いたことない・・・」となり，慌てて図書館で「スライドの書き方」みたいな本を借りてくる．
資料にプレゼンは評価に含まれないとあったので，白背景・アニメーションなしのスライドを作ることにした．
（ただ，あまりに出来が悪かったので例のR氏に手伝ってもらいました．）

9月下旬
リハーサル受付が9時らしく，それはしんどいから前泊できませんか？とメールしたらokが出て最高！！大好き！！

9月30日
東京に向けて出発．田舎者なので人の多さに慣れない．
ホテルに着いて，支払いがどうなっているか聞いたら既に払われていてやったー！（新幹線は各自で払って後で支給されるシステムだったため，同じかと思っていた）会場を確認しに行くと歩いて5分みたいな場所にあって感動&感動．秋葉原を歩くと3m間隔くらいでメイドさんが立っていて，これがアキバか・・・，となる．手ぶらで帰るわけにもいかないので，艦これの加賀のフィギュアを買う．
発表内容を唱えながら就寝．

10月1日
発表内容を唱えながら起床．
会場に行くとスタッフさんに誘導される．スタッフさんは大勢いらっしゃるだけでなく，イヤホンマイクで連携を取り合っていて大変頼もしい．控室には席とお弁当と飲み物が用意されていて，嬉しい．（が，体調不良のためほとんど食べられなくて悲しい．）
リハーサルではスライド，実機，カメラの切り替えタイミング，マイク，レーザーポインタ，ベルのタイミングなどを相談できた．とても真摯に対応してくれて，最高か～？となる．ただ，ベルのタイミングだけは，「後でお伝えします」だったので残念．

発表は3部構成になっており間に休憩がある．ので，休憩中に直前の部の発表者に質問をしに行く．（発表中は審査員が質問するため他の参加者はこのタイミングしかない．）どの発表者も視点が面白く，勉強になった．

ところで僕の発表ですが，ピンマイクの使い方が下手だったり，レーザーポインタが見つからなくて焦ったりして本当にダメ．プレゼンが評価に入らなくて本当に助かった．質問は専門家が攻めてくるようなことはなく，聞かれたことに答えるだけだった．これは幅広いジャンルを募集しており，審査員の専門が広く浅くなっているためだと思う．（悪い意味ではない．）

全員のプレゼンが終わった後は特別講演を聞いたり，近くにいた専門学校の教員の方?とお話ししたりした．こちらが1人だから話しかけやすかったのかも？（グループや保護者付だと各自で盛り上がっちゃうため．）

結果発表．1つくらい賞が貰えたらいいなと思っていたら4つも貰ってしまって思わず笑ってしまう．先ほどの教員の方?と喜びあう．ニコ生の視聴者投票で選ばれたのは驚き．副賞も嬉しいですね．

懇親会では審査員の方や企業の方，聴講の方にお声かけいただいた．論文を添付した人は今までいなかったとか，大臣賞とスポンサー賞は同時に貰えないみたいな噂話をされた．

10月2日
午前はサイボウズ社の見学会．他の参加者の方とプログラミングの話をしてみると皆さん優秀．青野さんと話せて嬉しかった．（初めて出たプロコンもサイボウズがスポンサーだった？ため．）
午後は情報化月間の式典．
解散して帰路につき，高専プロコンまで1週間ないことを思い出して絶望する．

U-22プロコンはサポートが手厚く（交通・宿泊だけでなく開発環境も提供されるらしい），素晴らしい．
挑戦していると評価されやすいのかな？と思いましたがよくわかりません．
ただ時期が高専プロコンと近いので，両方に出るのはオススメしません．（僕は体調を崩しダメになりました．）
1人でも出られるので，バシバシ応募してほしいですね．