【プロコン】競技部門「何色? サッと見 発見伝」の結果発表の様子【動画】
今回の内容はプロコンらしい競技部門でした。通信でデータを受け取って、ノートPCに黙々と計算させ、
結果をプロジェクタで投影してグラフィカルに表示する。
試合中は人の手から作業が離れ、最強・最速のプログラムを決める試合となりました。
10分間の試合時間の間に与えられたパズルの解き方を計算します。
同時に3つのパズルを解く必要があります。
それぞれ「10x10 4色」「12x12 5色」「14x14 6色」というように難易度が異なります。
決勝では色数が増え、パネルの数も最大の「20x20 6色」となりました。
3つのうち、どれから取り掛かっても、同時に計算を始めても良いのですが、
単純に総当りを考えると時間的にも総パターン数的にも無理な話で、
何らかの方法で無駄な探索を行わない⇒探索を刈り取るという作業が必要なようです。
最終的にはそれぞれの色が繋がっていれば良いわけで、
最終解は無数に存在し、探索に極端な分岐は存在しませんが、
探索中の解法がどれだけ良いものかを判断する、
「評価関数」の作り方が難しいということになっているそうです。
回答はテキストファイルにしてサーバに送信する形式で、
試合時間中であれば何度でも送りなおすことができます。
回答までの時間も評価対象ですが、優先度は下から2番目でした。
なので色を全て繋げる⇒クラスター化を最大にして、
そこに至るまでの手数で勝負が分かれました。
3つのパズルでの順位を合計してスコアと呼びますが、
これが同点になる試合が数回ありました。
この場合一番簡単な「10x10 4色」の順位で勝負が分かれています。
結果は全て異なる形になっていましたので、解き方は各校でそれぞれ異なるみたいでした。
…といっても複数のやり方で解いていたり、それを混ぜて扱っているみたいでしたが…。
大きく分けると「一色ずつ順番に固めていく」やり方(⇒キレイ)と、
「色が線のように繋がっていく」やり方(⇒あまりキレイではない)があるようです。
見た目のキレイな一色ずつ固めるやり方も、
「地層のように端から順番に色が並ぶ」パターンや、
「四隅にそれぞれ色を集めて中央で仕切る」パターン、
「外周に沿うように色を並べる」パターンなどがありました。
共通して言えるのは四隅、外周の色が決まるのは比較的早い段階みたいでした。
勝ったのは「大阪府立」でした。結果発表の手順を追っていく画面で、
気付いたら色が纏まっていたというくらいに素早い手数でした。
2位の「一関」は若干及びませんでしたが、
パネル数が多い⇒難しいほど強いというプログラムは自慢げでした。
■全国高等専門学校プログラミングコンテスト
■【第20回】プログラミングコンテスト2009【木更津】
■【木更津】「第20回プログラミングコンテスト」に行ってきました【写真】
