パソコン甲子園2011 本戦
2日間ボランティアとして働いてきました。選手・スタッフの皆さん、お疲れさまでした。
さて、プログラミング部門の第 6 問が物議を醸しています。
- http://d.hatena.ne.jp/semiexp/20111105/1320495854
- http://topcoder.g.hatena.ne.jp/JAPLJ/20111106/1320588994
が、今回取り上げるのは第 5 問の方です。Twitter 等ではこの問題に対する参加者のコメントはあまり見受けられませんが、この問題もまた不備な点が指摘されています。
この問題の題意は、「ロボットアームの回転命令が入力されたとき、回転後のアームの先端の座標を出力せよ」というものです。アームの挙動や回転命令の他に、出力すべき座標の計算方法も問題文に与えられていて、選手は要求の通りに計算するプログラムを書くことが要求されます。(問題文はまだ公開されていませんが、選手の他、会場でも若干の配布があったようです。残念ながら今私の手元にはないので、このような説明でご容赦ください)
この問題の不備な点は、文中に「行列 A と 位置ベクトル b の積を計算する」というような記述があり、A と b そのものは明確に定義されていますが、行列とベクトルの積とは何なのかという説明が一切無い点です。高校数学では行列は 数学C で扱うはずですが、選手の中にはまだ 数学C を履修していない者もいます。実際に何人かの選手と話しましたが、まさにこの点が理解できず、この問題を解くことを諦めたという声が複数人から聞かれました。
全ての選手が行列を知っているわけではないことは明らかですから、その定義については問題文中で厳密に説明すべきだったでしょう。
反論
これについて、次のような反論が考えられます。「例えばダイクストラ法なども高校教育の範囲ではない。要求する知識を高校一年生の水準に限ることは作題の上で非常に大きな制約になり、現実的にコンテストを開くことが不可能になる。従って、選手が受けている教育のレベルを越える出題も許容されるべきだ。」しかしながら、この主張は的を射ていません。以下にさらなる反論を述べます。
ダイクストラ法を使わないと解けない問題は、ダイクストラ法を知らないと絶対に解けないのでしょうか？そんなことはありません。ダイクストラ法と同じアルゴリズムを一から組み立て、正当性を証明すればよいのです。ハンガリアンマッチング、Suffix Array、どんな難しい既知のアルゴリズムやデータ構造を使う問題であっても、また選手がそれを知らなくても、十分に賢ければ、自力でそれを再発明して解くことができます。それが現実的かどうかはともかく、解くチャンスは与えられています。
一方で、この問題における行列とベクトルの積は「定義」です。行列を知らない選手が、行列のベクトルの積としてどのような解釈を考えたとしても、その解釈がどれほど合理的であっても、その解釈が正しいと確信する手段はありません。手当たり次第にプログラムを書いてみて、運良く正しい解釈に沿ったプログラムを書けていれば正解、というギャンブルを強いられます。教科書や参考書を見ればすぐに分かることではあり、実際に書籍の持ち込みは許可されていますが、不運にも持ち込んでいなければお手上げです。インターネットの利用は許可されていないのです。
問題を解くにあたって、高校の範囲を越えた知識を要求することは構わないでしょう。しかしこの問題では、題意を理解するにあたって、多くの選手が持っていない知識を要求しています。これは問題の不備であり、ミスジャッジと呼ぶべきです。題意を理解するまでの段階において、選手間の大きな不公平は存在すべきではありません。問題文は、中学卒業程度の学力と、基本的なプログラミングの知識があれば理解できる程度に詳しく書くべきです。
第 6 問は問題文が曖昧でしたが、これは全ての選手に等しく不利益を与えるものでした。一方この問題は一部の選手に著しい不利益を与えるものであり、競技の公正性という観点からは、第 6 問よりもむしろ性質が悪いと捉えることも出来ます。
さらに反論
この主張をメールで送ったとして、いかにも作題委員の返答しそうな主張を先回りして潰しておきます。
- 主張: 問題の解釈も競技の一部である。選手は問題文の解釈に困らないように、あらかじめ十分勉強すればよいだけのことだ。
- 反論: それはパソコン甲子園の趣旨に合致するのか。逆にプログラミング能力を競い合うことを妨げていないか。
全国の高校生及び高等専門学校生などが、情報処理技術における優れたアイディアと表現力、プログラミング能力等を競い合うことにより、生徒自身のスキルアップを図るとともに、情報化社会を支える人材の裾野を広げることを目的として開催します。
パソコン甲子園2011 - 概要 - 趣旨
- 主張: 行列やベクトルを利用した座標の計算方法は、問題の定義そのものではなくヒントにすぎない。アームの挙動や回転命令までが定義であるので、座標の計算方法は、選手が十分に賢ければヒントを無視して再発明することができたはずだ。
- 手元に問題文が無いので精査できないのですが、問題文は「ロボットアームを作りたい太郎君が書いたメモを参考に、座標を計算せよ」のようなストーリーになっていました。「参考にせよ」とは言いましたが、「メモの通りに計算せよ」とまでは言ってなかったかもしれません。仮に「指定された式を使わなければならない」という題意でないのなら、その式が全員にとって理解できるものでなくてもミスジャッジとまでは言えないでしょう。
- しかしながら、それでは選手が考えるべきアルゴリズムに対して、ヒントの割合が極めて大きいように思います。一部の選手に著しいヒントを与えるものは、ミスジャッジではないにせよ、回避されるべき問題でしょう。
雑記
とにかく今年の件で分かったが、ぼくがパソコン甲子園に3年間出場して学んだ唯一のことは「パソコン甲子園で問題を解いているときに詰まって、何が悪いのかわからないという状況に陥ったとき、間違っているのはぼくらではなく必ずパソコン甲子園側だ」ということだった。
PCKと同じく高校生以下対象のSuperConや情報オリンピックに比べ、PCKはより初心者を対象としている点で初心者がこういう大会に参加するきっかけを作るには素晴らしいものであるし、そもそも競技人口が少ない中で同年代の同じことに興味を持つ人達と交流できる貴重な機会としてたいへん価値のあるものだと思っている。
そんな素晴らしい機会にぼくが学んだことがあんなことだというのが残念でならないし、同じように思う人が今後は絶対に現れてほしくないと思う。
パソコン甲子園2011本戦 プログラミング部門 - Wrong Answer -- japlj - TopCoder部
今年でパソコン甲子園は9年目だが、私が何らかの形で関わりだしてからは8年目になる。2004, 05 はプログラミング部門の選手として参加し、会津大学に入ってからはボランティアとして運営に携わってきた(一度だけボランティア募集の告知をうっかり見落として、ただの観客として参加した年があったが)。
ボランティアとして参加して、初めて見えてくることもある。パソコン甲子園のスタッフは、皆素晴らしい人ばかりだ。
ここにパソコン甲子園の支援機関の一覧がある。協賛・支援機関はざっと 50 ほどだろうか。これはICPC福岡大会のWebサイトにある企業ロゴの数のざっと3倍だ。このご時世だ、賞金や賞品にも見られるように、予算は年々厳しくなっているのだろう。一社でも多くのスポンサーの理解と協力を得たいという事情は想像に難くない。
多くの人が絡めば絡むほど、多くの人の思惑がもつれていく。会津大学は、プログラミングやコンテンツの創作に秀でた高校生の獲得に繋げたいことだろう。協賛企業は、せっかく協賛金や賞品・懸賞品を提供しているのだから、自社の宣伝をしたいに違いない。市や県などは、情報教育に力を入れていることを市民に広くアピールしたいはずだ。運営側は、何重もの板挟みの中で、誰からも不満が出ないように調整しなければならない。会津大学のPRのために、選手は大学見学に案内される。今年は協賛企業の2社が自社の紹介をする場が設けられた。より多くの市民に会場まで脚を運んでもらうために、著名人に審査や講演を依頼し、駅前や街中でビラ配りまでしている。
人が集まれば集まるほど、無事にイベントを運営するのは難しくなる。ICPC に参加するのは選手とコーチとスポンサーぐらいなものだろう。参加も見学もしたことはないが、情報オリンピック、SuperCon、Epochまつやまなども同様ではないだろうか。一方パソコン甲子園には子供から老人まで、一般の観客が観戦に来るのだ。コンピュータに詳しくない一般の観客にも、楽しんで帰ってもらわなければならない。事故なんてもっての外だ。ボランティアやスタッフには一人一部運営マニュアルが手渡される。その量は数百ページに及び、全てのスタッフとボランティアのスケジュールが記述され、各人の仕事内容から緊急時の対応、例えば落し物の管理・迷子や傷病者の応対などにも配慮が行き届いている。
傍から見ているだけでも、大変な労力であることはわかる。運営本部は深夜12時頃まで明かりが付いていることも珍しくないし、あるスタッフの女性などは「私ここ2週間4時間睡眠ですよ」とのことだった。
スタッフの方々の本来の仕事は、会津大学の職員である。パソコン甲子園の運営は彼らの仕事の一つにすぎないし、彼らはプログラミングやデジタルコンテンツ、モバイルの専門家ではない。だからどの部門の審査にも彼らは携わらず、それぞれ独立した審査チームがいるのだ。
誰だったかよく覚えていないが、デジタルコンテンツ部門の選手と思われる高校生が、「審査環境を Internet Explorer に限ることを止めるべきだ」と主張しているのを最近目にした。そんなに声高に叫ぶ必要はない。喧嘩腰になる必要もない。ブラウザに明るくない人でも問題点を理解できるようにまとめ、ただ代表宛てにメールを送れば良い。私はどのスタッフがそのメールに応対することになっているか知っている。彼らは信頼できる人たちだ。彼らが問題点を認識できれば、適切な判断を下せる人、上役ないし審査チームに届けてくれるはずだ。そうなれば、来年からは改善されるだろう。
審査チームが適切に対応すれば、だ。プログラミング部門で今起きているのは、そういうことなのだと思う。
ここ数年のプログラミング部門審査チームは、あまりにも問題を起こし過ぎ、またその対応を誤り過ぎている。題意の不明瞭な問題は増加する一方だ。ジャッジデータの改行コードが LF であるべきところ CR + LF になっていて、 std::cin を使った選手のコードは正しく入力を読み込まなかったこともあった。驚くべきことに、これは選手からの指摘によって公知となった。ジャッジデータは非公開である。彼はたった3時間のコンテストの間に、間違いと判定された自分のプログラムがやはり正しいと確信し、ジャッジデータに CR が入っているのではと疑い、実際にそれを証明してみせた*1 *2。彼は即座に修正を求めてメールを送ったが、対応は拒否された。ひどい話だ。彼は scanf に書き換えてこの問題に正解したそうだが、これを知らずに不正解とされたまま終わった選手がどれだけいただろうか。
別の例を挙げると、今年度の予選は台風で多くの高校生が参加できず、彼らのために再予選が行われたが、その問題は過去のパソコン甲子園の問題そのままであった。過去問は Aizu Online Judge にて誰でも読み放題解き放題になっているにもかかわらず、だ。
私にはミスジャッジを責める資格はない。私自身、数多くのミスジャッジを犯してきている。よりによってこのパソコン甲子園の翌日に、OB会の模擬地区予選でやらかしたばかりだ(この問題は私の担当であり、文責は私にある。iwiwiさんの指摘はまったくもってその通りで、この場を借りてお詫びします)。
作題経験者ならば理解できることだが、ミスジャッジを完全になくすのは到底不可能なことである。しかし、パソコン甲子園のような頻度は度を越している。私にとって許せないのは、ミスジャッジそのものではなく、審査チームがどうやらミスジャッジを犯しやすい態勢にあるらしく、しかも一向にそれが改善される気配を見せないことだ。
会津大学には ICPC Programming Club という団体があり、顧問をしていらっしゃる教員は Aizu Online Judge を開発・管理しているその人だ。メンバーには数百問から千問以上を解いた人も少なくないし、そういった人たちは何千問もの問題を読んできている。読みやすい問題とはどんな問題かをよく分かっていて、また UAPC などのコンテストの開催経験、作題経験もある。私たち (私もメンバーの一人だ) に助言を求めていれば、前もって第 5 問のような指摘はできたはずだ。機密保持等の観点で学生にそのような仕事を任せられないというのなら、顧問の先生に頼めば良いだろう。彼もかつての ICPC 上位入賞者で、作題経験もあるのだ。
ちなみに先生は、パンフレットの審査チーム紹介のページに名前と顔写真が載っている。が、「審査チーム」と称する枠の外側に彼はいて、いったいこれはどういう意味なのだろうか？本人にお聞きしたが、彼は確かに審査チームの一員ではないということだった。ならば何故彼が載っているのだろうか？
JAPLJさんから上のような意見が聞かれたのはとても悲しいことだ。運営スタッフは、パソコン甲子園を成功させるために毎年血の滲むような努力を、睡眠や食事さえも削っての作業を続けている。審査チームの行為は、その努力を一手でひっくり返すことに他ならない。スタッフがJAPLJさんのエントリを見たら、何を思うだろうか？私はこのエントリに対して、何ら反論の言葉を持たない。スタッフの心中を察する度に、やりきれない思いになる。
審査チームは猛省しなければならない。そして、今の審査チームにコンテストを開催する力量があるのかは極めて疑わしい。根本的な対策がなされる必要がある。
