天下一プログラマーコンテスト本選　その1　〜本選概要〜

program

　8月1日、2日に 天下一プログラマーコンテスト 本選に参加してきました。本エントリはその1ということで本選の概要と、「プログラミングコンテストでどんな問題がよいのかの考察」についてちょっぴり書いてみます。

概要

　主催：KLab株式会社
　日時：8月1日、2日
　場所：六本木ヒルズ森タワー アカデミーヒルズ
　参加チーム：21チーム（どこが一番遠いか等、私は把握していませんが、日本全国からの参加だそうです）

1日目

　　3問出題。問題は順番に公開される（複数人チームが有利にならないようへの配慮らしい）。1時間以内に解くと1点獲得、1時間過ぎてからは0.5点。

2日目

　　1問出題。1日目の上位10チームが進出できる（1時間以内に解が投稿されない場合、他のチームも勝利の機会がある）。
　　「プレゼンテーションタイム」が設けられており、希望チームは予選・本選の問題で出題された問題を解く工夫点などを発表することができる。

問題概要

　本選で出題された問題について、概要のみ簡単に説明してみます。問題の公開については、若手エンジニアブログにて期待したいと思います:)

1日目

1. エイトクイーン
　エイトクイーンという、チェスの盤上にクイーンを置く問題の発展問題が出題されました。11x11のマスかつ、チェスの盤上にはクイーンが移動できないマスが幾つか用意されています。
　参考：エイト・クイーン - Wikipedia

2. ナンバークロスワード
　ナンバークロスワードと呼ばれるクロスワードを解く問題です。問題のクロスワードと、クロスワードの数字に当てはめるための英単語の辞書が与えられます。
　ナンバークロスワードパズル - Wikipedia

3. 処理系
　GNという、自然数を与えられると動作する処理系（インタプリタで、Brainf*ckのようなチューリングマシン）の作成と、与えられたGNプログラムの実行結果を求める問題でした。自然数をまず素因数分解するところから始まります（指数部分がプログラムの命令に対応）。

2日目

エレベータのスケジューリング問題でした。問題の詳細を覚えていないため省略します（プレゼンテーションタイムへと、1日目の解けなかった問題に挑戦していました）。

コンテストについて一考

　問題は予選*1と似た形式で、すべて探索問題でした。

　問題は時間をかければ多くの人が解けそうでしたが、1時間という制限時間が入ると慣れてない私には辛かったです。多くのチームの方が問題をばりばり解いているようで、非常に驚きました（むしろ、パズルが苦手なのに予選を突破できたのは少数派？）。

　コンテストは、インターネットに接続可能、あらかじめ用意してきたコードやライブラリの利用がOKというかなり緩い条件の下で開催されました。「問題に悩んだらウェブで検索したり知り合いに聞くこともできる（コンテストという枠に限定しすぎない）」という、一般的にプログラムを書く時と近い条件にしたそうです。また、こういった問題は解くことが慣れている人ほど有利であるため、不平等が生じないよう苦心されていたようです。

　しかし、プログラミングスキルとは、経験量に大きく依存しています。異なるアルゴリズムを自分で実装したり、多くのライブラリやフレームワーク・プログラミング言語を深くまで扱った経験は決して軽い物ではありません。そういうわけで、経験による不平等というのは、どうしても起こるんじゃないでしょうか*2。
　「プログラミング」で競技をするならば、「プログラミングで扱う要素をそれぞれ統合した問題」か、「特定の狭い分野」となるのではないでしょうか。そして誰かが有利になってしまうのも、各々鍛えてきたスキルが違うので得意・不得意が出ても当然で、問題をいかに「ばらけさせる（多くの問題を集約する）」「まとめるか（専門の1分野に集約するか）」だと思いました。

　プログラミングとは「ゼロから作り出す」だけではなく、「チューニング」とか「リファクタリング」とか保守にまつわるプログラミングもスキルの1つですよね。こんな意味でとらえると、「品質保証（QA）のテスト」とか「デバッグ」も重要な競技問題となり得るんじゃないかと思いました。

簡単にまとめ

  • 1時間という制限時間は私には辛く結果はぼろぼろでした。脈略ないですが、今まで苦手だった探索問題が少し好きになれました。
  • これもまた脈略ないですが、優勝した方（だったと思います）の「天下一探索マスター大会」という発言がツボに入りました。
  • プログラミングコンテストの問題を作るなら、「多くの問題を広く深く（とあるOS間であれこれしたいとか）を集約化」したり「専門（アルゴリズムだけとか）に絞ってみる」のはいかがでしょうか。
  • 「デバッグ」「チューニング」「保守」というのも問題のネタになると思います。
  • KLab株式会社関係者の皆様、参加者の皆様、ありがとうございました。コンテストに参加し、そして親睦会で参加者、スタッフの方々とお話しして何か得られた物があったと思います。

その他

　suztomoさんのエントリが写真つきで雰囲気がつかみやすいと思いますので、あわせて読んで見てはいかがでしょうか。
　天下一プログラマーコンテスト決勝 - suztomoの日記

次回

  • どういう経緯で参加したのか。そして、当日どんな心情で本選に挑んだ（そしてボロボロだった）のか、親睦会でお話ししたことや、得られたと思うことは次回に続きます。

*1:http://lab.klab.org/young/2009/07/web%E4%BA%88%E9%81%B8%E7%AC%AC%EF%BC%93%E5%9B%9E%E6%A6%82%E6%B3%81-%E7%AC%AC%EF%BC%93%E5%95%8F%E8%A7%A3%E8%AA%AC/

*2:負けるべくして負けた、、と言い訳するのも嫌な感じですが、私は他の参加者に負けない分野もあると思いますし、参加者の皆さんも他の人に負けない得意なことを持っている（持っていて欲しい）と思います。