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

こんばんは！kagamizです.

2012/10/13 - 10/14の間に開催された, 高専プロコンの競技部門参加者としての参加記(主に参加するまでの過程)について記します.


1.今年度の課題について
具体的な内容は, こちら(7ページ目以降)から確認できます.

要約すると,

"大・中・小の３種類のサイコロがある. 2m程度はなれたテーブルの上にあるそれぞれのサイコロの数を求めよ."

というものです.



2.問題の考察
とりあえず、何もしない段階でも得られる情報は「総重量」の情報のみです.
したがって、 沖縄高専では何の情報があれば個数算出に役立つかを考えた結果、
表面に見えるサイコロの目の数から、サイコロを測定するということに決めました.
(といっても、中々うまくサイコロの目の数の情報を活かすことが出来ず、このアプローチが最終的に仕上がったのが現地に到着した日でした.)

この２つの情報から、沖縄高専では次のような2つのアルゴリズムを思案しました.
・(1) count(旧名forte)
countは、目視で確認できたそれぞれの大きさのサイコロの数の下界,
山の重量などの条件からそれぞれの大きさのサイコロの数の上界を決め,
重さの誤差が相対誤差で5%範囲内のものを解の候補として許容し,
それぞれの大きさの数の候補のなかで最も高いものを解とするアルゴリズムです.
(頻度が最も高いもの同士をとり、重さに矛盾が起きれば, プログラムで補正をかけられるようにしています.)

・(2)piano
pianoは, 表面に見えるそれぞれのサイコロの目の個数が,
山全体にある大・中・小の個数の比と一致するとして,
比を実数倍し、元々の重量に近づけるようにすることで解を出しています.
この解法であれば, 元々の重量にサイコロの個数を近づけているため, 重さに矛盾が起きることはありません.
これを, 3つの調査エリアから1枚ずつ写真をとり、平均を求め, それを答えとします.
平均を求める過程で重量と矛盾が起きれば, 重量に矛盾が起きないように小のサイコロの個数を調整します.
それぞれのサイコロの目は, 大の面積の閾値, 小の面積の閾値, ... などを決め, それぞれの面積で大・中・小にサイコロを振り分けました.

(2)のアルゴリズムで、サイコロの目の検出は、赤い目と黒い目の処理を別々に行なっており, それぞれ別の先輩が担当しました.

(2)のアルゴリズムを思いつくまでは, 目の個数をどう扱えば良いのかわからず,
先輩に目視をがんばってもらい, (1)を使う予定でした.
(上でも述べたように、(2)のアルゴリズムをまともに使えるようになったのは本選の前日でした. )

他にも、エッジ検出等の方法からも解を導こうとしましたが、僕がアルゴリズムを思いつけませんでした;

3.大会1日目
(2)のアルゴリズムを思いついてからは, 皆で協力して良い面積の閾値を求めるために奮闘していました.
沖縄で練習していた画像で, (1)のアルゴリズムを使っていた頃よりはるかに良い精度の解が出ました(実際の数＋3とかそれくらいでした).
その結果が出た時は委員長とハイタッチして喜んでいました.(たしか土曜日の4:30くらいでした!)
この数字を見てから, 沖縄高専では画像処理を用いる(2)のアルゴリズム1本で行こうという話になりました.

なんとかうまくいく状態で予行演習に望みましたが, そのときは4位でした.
あまりにも想定していた誤差より大きいので, 本当に焦りました.
...が、(2)のアルゴリズムの最新版を使っていなかった事が原因ということが分かりました＼(^o^)／

予行演習後, 急いで(2)のアルゴリズムを最新版に直し, また, 練習していた環境と本番の環境の違いを考察していました.
すると, オブジェクトが赤・黒の検出を少し邪魔していることと, 重量と理想重量(大会側が発表している重量)には3%程度の誤差があることが分かりました.
そこで, 検出が一番むずかしい(かつ、一番誤差が大きい)小のサイコロの個数を, 大会中の統計データを使い調整しようという作戦に出ました.

以上のことをやって, 午後には実際の試合に望みました.
(ここまでで, 委員長は32時間くらいぶっ通しで起きていました.)
舞台に上がる時は, 3人とも物凄く疲れていました.

フィールドAでの撮影では, 1枚目の画像が壊れていて, "メモリ不足です"と言われてとても焦りました.
しかし、他の画像はうまく取れており, フィールドAについての解を出すことが出来ました.
同様に, フィールドOについての解も出せました.

結果, 3位の所とサイコロ20個ほどの差を, 2位で1回戦を突破しました!
この時の喜びは物凄く大きかったです.
委員長とずっと叫んだりハイタッチしたりしましてました.w

その後は、先輩たちに赤と黒の検出の精度を高めてもらい, 次の日の試合に望みました.

4.大会2日目
2日目では, 1日目より明らかに他の高専の方が強くなっていました.
(敗者復活戦で津山高専が誤差35を出していたのにはびっくりしました.)

そして、2回戦の沖縄高専の番が来ました.
この時のオブジェクトはどちらも黒色で、黒検出に引っかからないかが心配でした.
しかし、どちらのオブジェクトも検出から外れていて、物凄く感動していました. (委員長すごいなーと思っていました.)
(2)のアルゴリズムの動作時間は早いので, 答えを出し終わったらPCを閉じて結果を待つのみでした.

実際の結果は, 2位と11個のサイコロの差で敗け, 4位でした.
不思議とこの時は, 皆できることをやったということで、清々しい気分でした.

競技が終わった後, システムを見てみると, 赤の検出の部分が古いバージョンのままになっていました.
もしかすると其れを直すともっと良い精度になったのかもしれませんが, どうあれ結果は結果なので, 皆で納得しました.

5.結果と感想
上にも書いたように、結果としては2回戦敗退でした.

やはり、結果としては悔しいです.
しかし, 先輩たちは物凄く頑張っていたので, アルゴリズムがあまりよくなかったのかなあと思うところがあります.
来年以降、またチャンスがあれば良いところを目指したいと思います!

今までは専ら競技プログラミングしかしていなかったので、新しいことがたくさん得れる貴重な体験をすることができました.
一緒に開発を進めてくれたチームのメンバーには、感謝することでいっぱいです！
ありがとうございました.

以上, 参加記でした.