CODE VS 2.1予選問題は悪問ではないか

プログラム系のサイトを巡回している人ならばうざいぐらいにバナー広告が出てきていて、当然ご存知だとは思うのだけども、いまCODE VS 2.1というプログラマ世界一決定戦というプログラミング競技が開催されている。

CODE VS 2.1公式
http://codevswc.jp/jpn/

予選は2013年6月27日まで。予選ランキングの上位8名が決勝に進め、決勝は1位の賞金が50万円、2位が30万円、3位が20万円である。

問題をパッと見た限り、私なら予選通過は余裕なので、時間があればやろうと思っていたのだけど、問題の作りがいまひとつよろしくない。これについては長くなるので後述する。

そもそも決勝に進出しても私には3位に100%入る自信はない。まあ、たぶん問題の性質から言って3位ぐらいなら入れるとは思うが、1日勝負だとその日の閃きとか体調にも左右されるので過信は禁物である。3位に入れなければ交通費と宿泊代とマシン代で大赤字である。そもそも優勝賞金少な過ぎない？どう見ても広告費のほうがお金かかってるよね。せめて決勝に進んだら交通費と宿泊代ぐらい出して欲しい。

Short Coding ~職人達の技法~

そんなことを思っていたら、ショートコーディング本のOzyさんがチャレンジ開始。(今月の5日ごろの話)

Ozy「いま私の使っている最高性能のPCが、Let's noteなのでもっと速いマシンを買いたいんですが、XeonとCorei7ならXeon買ったほうがいいですか？」
私「Xeonはdualに出来るのが特長で、singleで使うならそれと同じアーキテクチャのCore i7シリーズとほぼ同等の性能しか出ません。並列度の高いプログラムを動かすのであれば、Core i7搭載のPCを2台用意するほうがコスパに優れています。」

Ozy「そうですか、じゃあCore i7-3970Xにしときます。」
私「えっ。いまならHaswell搭載PC×2のほうがコスパ(電気代も含めて)が良かったりしませんか…」

Ozy「もうポチっちゃいました^^;」
私「…」

その3,4日後にそのマシンが到着したようで、Ozyさんが予選ランキング1位に！(現在3位)

これくらいで1位になれるなら私も挑戦しようかと思ったのだが(Ozyさんのプログラムについて詳しくは知らないが、XXXとかXXXとかをやっていないということはわかっている)、どうせならGPGPUで並列化したい。だけど、Tesla K20X、まだ90万円ぐらいするんだよね。もう少し下がったら買おうと思っていたのだが…。

富士通 GPUコンピューティングカード(NVIDIA Tesla K20X) PY-GP205Z1

CUDA 5.5になってからDynamic Parallelismという機能が搭載された。この機能自体、あまり取り沙汰されていなくて知らない人がほとんどだと思うけど、この機能、ホント凄くて、従来、GPUでの計算結果をCPU側にいったん戻していたような処理が、GPUからGPUのスレッドを直接実行できることが出来るようになって、CPU側に処理を戻さなくて済む(場合がある)。

今回の問題のような探索処理をGPUで処理しようとするとき、このDynamic Parallelismが驚異的な威力を発揮する(と私は思う)わけだが…手元に実験できる環境がないので知らん。だもんで、この件は、話半分に聞いておいて欲しい。

まあ、いまTesla K20Xを買ってまでチャレンジしたくはないという私の個人的な事情はさておき、今回の問題が悪問だと言う根拠は、以下の通り。(他の解答者へのヒントになるといけないのでアルゴリズムに関する部分はぼかして書く)

・ブロック(パック)の配置も左2升が空白のときにx=-2とかに置けるだとか、プログラムをいたずらに複雑化するだけなのでないほうがいい。

・ブロックのサイズも1×2固定とかにして回転をなくし、かつサイズを固定しても競技性は変わらなかったと思う。

・ブロックが消える条件が結構ややこしい。縦横斜方向の2升の合計とかで良かったのではないか。

・点数計算がややこしすぎる。お邪魔ブロックとか、発火数カウントとか要らない。単にチェイン数だけの勝負でも競技性は変わらなかったと思う。

・フィールドが3種類も要らない。1種類だけで十分。

・1回の制限時間が長すぎる。フィールドsmallのみで、15分ぐらいで十分。3時間かけて生成された解答に対抗するにはこちらも(同じ程度のプログラムであれば)3時間PCをフル稼働させないといけない。

・アルゴリズムにも工夫の余地がほとんどない。(まだ競技が終わっていないので詳しいことは書かないが)

・公平性を期すなら、他の競技プログラミングのようにサーバーサイドでユーザーのプログラムをコンパイルして実行してくれるほうが望ましい

など、競技性を損なわない形でもう少しとっつきやすく、かつ、公平な形に出来たんじゃないのかなぁというのが正直な感想。

予選スコアを見ると上15人ぐらいだけが本気で、あとの人は形にすらなってない感がある。まともなスコアをサブミットしている参加人数も30人ぐらいしか居ないし、仕様が複雑すぎて手をつける気にもならないのが現状ではなかろうか。

もう少しとっつきやすくして、参加者を増やさないと競技にならない。いまの仕様なら自動ぷよぷよのほうがまだとっつきやすいだろう。

逆に言えば、まだ参加者は少ないので明日・明後日で頑張れば予選突破ぐらいは出来るんじゃないだろうか。みんな、いまからがんがれ！すごくがんがれ！