とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

2012年JAG夏合宿Day2の作問について

この記事について

この記事はhttp://partake.in/events/3fcea6d7-0bab-4597-82db-86439aadb1b9
Competitive Programming Advent Calendar Div2012の12/18の記事です。

コンテストの概要

9/15(土)(11:00-16:00)の http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=JAGSummerCamp12Day2
shioshiota , not , kawatea さんと自分で出題をしました。

作問の機会を与えてくれたeomoleさんに感謝です。

この記事の目的

作問の経験をふまえて、よいコンテストにするにはこう準備すれば上手くいくのではないかなあというポイントについて書いていきます。
3-4人程度での作問を想定しています。

なお、このページに日時などが書いていますが、このようなスケジュールでよく準備ができることは保証できません。多分全体的にもう一週間くらいみておくと余裕を持って作業ができると思います。

もくじ
  • A : いろんな案を出そう
    • A1 : wikiで積極的に書き込む
    • A2 : 問題ドリブンと解法ドリブン
    • A3 : 問題の案が増えれば選択肢も増える
    • A4 : できるだけオフラインで集まろう
  • B : スケジュールは大事
    • B1.ネタを出す時間を作って、最後はオフラインで問題を選ぼう
    • B2.準備するコードは結構多い
    • B3. 問題文を作る時間を計算に入れよう
    • B4.スライドを作る時間も考えよう

A.いろんな案を出そう

今回のコンテストでよかったと思うのは、複数人の相互作用でできあがった問題がいくつかあったことだと思います。

A1.wikiで積極的に書き込む

問題案をたくさん出すという意味でも大事ですが、それに突っ込みを入れるのも相手の考えとのギャップを埋めるのによいと思います。
shioshiotaさんが積極的にやっていた覚えがあります。

A2.問題文ドリブンと解法ドリブン

今回のコンテストの準備では両方のアプローチがあって、7-8割は解法ドリブン、もしくは原案そのままという感じだったように思っていて、残りは問題文ドリブンで出来上がったように思います。

問題文ドリブンで作られた問題はDと、Bの一部分だったように思います。

どちらも問題として出来上がるまでの流れが面白く、作問側としては記憶に残るものでした。
ただ、どちらも最初想定していたよりもだいぶ難しくなってしまったのでコンテスタント側からすれば困った問題だったかもしれません。

A3.問題の案が増えれば選択肢も増える

問題を出しても無駄になってしまうのは惜しいという気持ちはあるが、そこまでケチケチしないほうがよいです。

というのは、今回はICPCの地区予選の練習ということで、バランスや問題の特色(複雑な設定とか重い実装)を似せるほうがよいため、そういう意味で制約が多いものになります。少ない案しか出ていないと問題採択の選択肢が減ってしまっていたと思うので、そのあたりはよかったと思いました。

初回の会合までに完成度の高い問題からそうでないものまで17の案が出されており、自分はこれくらいあれば楽勝だと思っていました...が、実際にはそうはいかずに未決定のものを残しつつ完成した問題から作業を進めることになりました。

A4.できるだけオフラインで集まろう

作問の作業というのはオンラインで作業できることがだいたいですが、それでもオフラインで集まった方が作業が捗ります。
さらに、問題の微調整もしやすいので効率的だと思います。

実際、問題の細部の調整はみんなが集まっているときにできたものがいくつかあります
(例えば、Bの全探索お姉さんの座標系、動き方のルールなど

B.スケジュールは大事

今回のコンテストだと日程はほぼ確定しているのでどのくらいのことをどれくらいにするか逆算しないといけません。
このときには、唯一の経験者だったshioshiotaさんにスケジュールなどの助言をお願いしました。

B1.ネタを出す時間を作って、最後はオフラインで問題を選ぼう

A3の理由で、ネタはたくさんあった方がよいのと、問題採択のときに全員が共通の認識を持てて、問題の修正も容易にできます。

チームが結成されたのは8月上旬(だったはず)で、初めて集まったのは8/24でした。
その日は7問(本番ではA,C,F,G,H,I,J)が修正されつつ選ばれ、2問(本番ではB,D)をもう少し考えよう、という形にしました。

B2.準備するコードは結構多い

それまではあまり意識していなかったのですが、準備するべきコードはたくさんあります。ですので、スケジュールを考えるときにはこれも意識するようにしましょう

hama_duさんの記事http://hama-du.hatenablog.com/entry/2012/12/10/231757 でも触れていますが、入力ジェネレーター、入力チェッカーのほかに、問題によっては出力チェッカーもいります。
問題を解くプログラムだけでも、想定解法(作問者+テスターのふたつ) , 想定誤解法 , 想定TLE解法といった具合に、たくさんコードを書く必要があります。(そうでないと、コンテスト直前に条件を変更するときに柔軟な対応をとれなくなってしまいます。

そのため、自分で作った問題でコードもすぐにかける、という問題でも思っていたよりも時間がかかってしまうと思います。

今回の作問ではこれらのコードの管理はnya3さんのrime(https://github.com/nya3jp/rime/)が使われました。

B3. 問題文を作る時間を計算に入れよう

最初、この作業を「日本語だし楽勝だろう」と自分は完全になめていました。shioshiotaさんに大変だといわれて意外に思っていましたが実際大変でした。

大変なのは具体的には以下の通りです

  • ICPCに似せるとすると問題文が長いこと
  • ICPCの問題は入力変数も多く、その分説明が増えること。
  • 書き方が悪いとcontestantが誤読をしてしまう可能性があるので細心の注意を払う必要がある

誤字どうこうではなく、表現のレベルまで見直さないといけないので結構大変です。
最終チェックはオフラインでやる形になりました。このときに、一斉に読んでみて「この表現はこうした方がよいのでは」などの話をして次の問題へ…という風にやっているとかなりの時間が経過していた覚えがあります。

B4.スライドを作る時間も考えよう

あまり作っていなかったのでいろいろ痛い目を見ました。
特に自分はよいスライドの作り方を心得ていなかったこともあり、
解説当日のスライドはなかなか悲惨だったと思います…。
ちゃんとレビューしてもらうべきでした…。


余談

  • D問題はもとは僕が題名だけつけた問題で、その後notさんを中心に問題が深められていきましたが、コンテスト一週間前に想定解法が誤解法だということがわかって冷や汗をかいたりして、思い出が多いです
  • qnighyさんにAdventCalendarの記事の相談をしたところunion-findの計算量解析を提案してくれましたが、結局やりませんでした。春休みの宿題にさせてください
  • 今年の序盤くらいにはDPの記事を書いてやるーと意気込んでいたりしましたが、いろいろと書いているうちに自分でも収拾がつかなくなってしまい、結局お蔵入りになってしまいました。