monolithic kernel

全国高等専門学校 第20回 プログラミングコンテストに参加

October 18, 2009

    今年もプロコンに参加してきました。選手のみなさん、お疲れさまでした。

    今回の競技は前回までとは打って変わって人間が介入する余地のほとんどない問題でした。ルールも割とわかりやすく、それでいて問題の難易度は高いのも理想的だったと思います。

    私の所属している豊田高専は、なんと1回戦を1位で突破することができました。準決勝は4位という結果に終わってしまったものの、3年目にして初の1回戦突破を果たせてとてもうれしいです。

    しかし、大阪府立と一関の強さは尋常じゃないですね……。アルゴリズムが気になります。

    ちなみにうちは深さ優先探索に評価関数を用いた探索順序のソーティングを加えたものを利用しています。加えて、単純な深さ優先探索では終わりが見えないので、思うように点数が伸びないと判断した場合には枝刈りを行っています。評価関数では以下の項目に基づいて評価値を計算しています。

    • 隣接するセル同士が同じ色になっているかどうか
    • それぞれの色について、セルがどの程度離れているか
    • 実際のスコア

    また、今回の競技は例年に比べてトラブルが少なかったように思います。予行演習の時点でプログラムが問題なく動作したのは今回が初めてでした。これにはやはり練習場の存在が大きいのではないかと思います。コルンさん、ありがとうございました。

    そして、安定したシステムとしっかりとした運営で競技を支えてくださった実行委員会と木更津高専のみなさんに感謝します。ありがとうございました。