天下一プログラマーコンテスト本選　その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:負けるべくして負けた、、と言い訳するのも嫌な感じですが、私は他の参加者に負けない分野もあると思いますし、参加者の皆さんも他の人に負けない得意なことを持っている（持っていて欲しい）と思います。

Wizard Bible vol. 47

etc

　Wizard Bible vol. 47 リリースされました。今回は久しぶりに私も原稿を書かせていただきました。

○第1章: マニアックJavaプログラミング第11回:
〜 しぶといアプリに仕上げよう 〜 金床 著
○第2章: 難読化ツールを作ろう 前編：VC++のプロジェクト変更の自動化 suma 著
○第3章: ハニーポットを作ろう vol.0 〜ハニーポットってなぁに？〜 黒崎ゆうき 著
○第4章: 浮気のススメ 理事長 著
○第5章: 基礎暗号学講座・第22回 〜ガウスの和と平方剰余の相互法則〜 IPUSIRON 著

http://wizardbible.org/47/47.txt

　忘れないようにすぐこのブログでもリンクしておこうと思っていたんですが、やっぱり忘れていました...。

Android 端末のHT-03Aを買ってみた

etc

　本日HT-03Aを購入＆新規契約してきました。AndroidというOSを搭載した携帯端末で、10日にdocomoから発売された以下の機種です。

　http://www.nttdocomo.co.jp/product/foma/pro/ht03a/
　Androidケータイ「HT-03A」発売──購入サポートでバリュー一括3万円弱 - ITmedia Mobile
　iPhoneユーザーから見たAndroidケータイ「HT-03A」（前編） - ITmedia Mobile
　HT-03A - HT-03A ドコモ HTC - Windowsケータイ

　店頭でキャンペーンをやっていたため、私の場合は結構安い値段で購入できました。
　まだあまりさわれていませんが、気に入った点、気づいた点を書いてみます。

気に入った点

・端末が小さく、画面も小さいものの、軽くて片手で持ちやすい。
・アプリケーションが多く公開されている（アンドロイドマーケットでアプリケーションがダウンロードできる）。
・Google Mapはキャッシュしてるっぽい（iPhoneでもキャッシュしてるんだっけ）。
・Android SDKが公開されている（何か自分もアプリケーションを作りたいと思っています）

気になるところ（気づいたところ）

・バッテリーの消耗早い
　晩ご飯を食べに行って、帰ってきたら30%ほど消費していました。 ちなみにバッテリーは2個付属しています。ケースが付いているため、1個を予備で持ち歩くことができます。
・タッチパネルでの文字入力しにくい
　ソフトウェアキーボード（タッチパネル）での入力です。慣れとか指の太さも関係ありそうです。 iPhoneみたいな入力（フリック入力）が欲しい場合は、simejiというアプリがよいらしい。
・USBのミニしかポートがない
　音楽を聴きたいときは変換ケーブルを使います（ケーブル付属してます。スピーカでの再生もできます） 。
・GMailの最初の同期が長い
　メールマガジンの未読が3000件近いのが原因かもしれません。同期が完了していないため、まだ私は端末経由でGMailを使えていません。

2009-07-12 追記

・GMailの同期はできるようになりました。
　WiFi（無線LAN）を接続しなおし、自動同期を無効だったのを有効にしたらできました。ちょっと謎いです。
・インストールしたアプリケーション
　NetSentry：アプリケーションをインストールしてからの通信料（WiFi，2G/3G）が確認できる。
　TaskManager ：マルチタスクでバックグラウンドで起動しているアプリケーションの切り替えや終了ができる
　Toggle Settings：端末の設定ユーティリティで、特定の機能のオン・オフや設定ページへの移動が簡単にできる
　twidroid：twitterクライアントで、バックグラウンドに常駐させて更新をチェックができる