高専プロコンの「団長」が魅せたアルゴリズムと涙高専プロコンリポート(2/3 ページ)

» 2007年10月31日 06時45分 公開
[湯浅優香,ITmedia]

基本的な戦略

 核となるアルゴリズムの部分については、Microsoft Visual Studio 2005を用い、それほど苦労することなくCとC++でコードを書けてしまいました。アルゴリズムと書くと、そこで拒否反応を示される方もおられるかもしれませんが、やるべきことさえ決まれば実はそう難しいものではありません。

 本大会では、大会前に、石の形(ピースの形)と石垣の形(枠の形)の情報が公開されていたため、その情報を基に、次のように考えました。

 まず、石垣(枠)を横がx軸,縦がy軸の座標と設定します。次に、石垣の左上(x=0,y=max)にAという形の石を入れてみます。Aの石が入らなかったらBの石、Bの石が入らなかったらCの石……。石が入ったら1マス下(x=0,y=max-1)にズレてまた同じ作業を繰り返します。石垣の左下(x=0,y=0)まで到達した場合は、右(x=1,y=max)にズレてまた繰り返し……。これをひたすら繰り返していきます。

 書いてしまうと何ということはない作業ですが、計算量は非常に膨大です。このため、プログラムが出力する大量の答えの中から、最も優れた物(空いたマスが少ない物、かつ石垣の上部が空いていないもの)を選び出すプログラムも一緒に作りました。

 ここまでの作業で、完成予定の石垣がプリントアウトできるため、後はそれに合わせていかに石を落札するかが勝負の分かれ目となります。つまり、「欲しい石は何としてでも落札しなさい! どんな大金を払っても構わないわ! !団長命令よっ!」――戦略はまさにこの一言でした。

決戦の土曜日

 こうして万全の体制で望んだはずの競技部門でしたが、初戦では最初の石の入札の時に、第1希望の石が落札できず、いきなり大ピンチに遭遇しました。案の定、結果は4位。優勝するには敗者復活戦で勝ちあがらなければならない状況へと陥ってしまったのです。その夜、ホテルの一室では、「今度こそ絶対に欲しい石は入札するわ!」と闘志を燃やす団長の姿がありました。

 そして2日目の敗者復活戦。わたしたちはここでもピンチに見舞われました。なんと、試合が始まる約20分前に、試合で組み立てる予定だった石垣データの中に、裏と表が反転、つまり鏡に映したかのように左右が反転してしまっている石があることに気がつきました。左右対称である石であれば特に問題ないのですが、左右非対称な石は反転させてしまうと配置が大きく変わります。いとしいプログラムが犯したちょっとしたミスでしたが、大会のルール上、反転させて使うことは許されていません。絶対絶命です。

 しかし、これはコロンブスの卵的発想で簡単に解決しました。幸いだったのは、石垣(枠)も左右対称だったこと。石垣が左右対称なのであれば、反転させても同じ形のままです。つまり、石垣データが印字された紙を裏側から見れば、左右非対称な石も含めて元通りになるわけです(下図参照)。これに気づいた自分を褒めてあげたい気持ちでいっぱいでしたが、まずは大あわてで、石垣データの描いてある紙を表裏を裏返し、後ろから透けて見える石データを後ろに描き移しました。絶体絶命のピンチを切り抜けたわたしたちに敵はなく、2位で準決勝に進むことができました。

コロンブスの卵 団長がひらめいたコロンブスの卵的発想

Copyright © ITmedia, Inc. All Rights Reserved.

注目のテーマ