Hatena::ブログ(Diary)

虎塚 このページをアンテナに追加 RSSフィード Twitter

2014-05-12

プログラミングの問題を作る時に考えること

先日のオフラインリアルタイムどう書くで初めて問題を出したところ、解く側で参加する時には考えなかったことを色々と考えて面白かったので、せっかくなのでまとめておきます。

オフラインリアルタイムどう書くとは
皆で共通のお題を好きなプログラミング言語で解いて、結果を見せ合う会です。

これから書く内容は、どう書くで出題する問題を作る時を前提としています。どう書くには、次のような特徴があります。

  • 出題者と回答者が同じ空間にいる
  • 回答に好きなプログラミング言語を使ってよい
  • 回答の制限時間は1時間(撃墜タイムのようなものはない)
  • 解けても解けなくても回答者は発表する

問題の要件を一意に定義する(必須)

問題文は、一意に解釈できる必要があります。

どう書くでは出題者が会場にいるので、問題文の解釈に迷ったら質問して解決できます。しかし、その場にいない人や後から問題を解く人は、問題文を文意どおり解釈するしかありません。誰が読んでも同じ意味に取れる文章をこころがけます。

たとえば、次のことについて、忘れずに言及するとよさそうです。

  • 数値の上限と下限
  • 組み合わせの中での値の重複可否
  • 集合に属する値のソート条件
  • 提示条件の固定/可変の別
  • 回答が存在しない場合の出力値

できれば、出題前に問題文を誰かに読んでもらって、何か質問がないかを確認するとよいと思います。相手は、プログラミング経験のある人が望ましいです。

正確なテストデータを用意する(必須)

データの正確さ

テストデータに誤りがないように気をつけます。

どう書くには、1時間という回答の制限時間があります。テストが通って時間が余れば、回答者は実装を洗練させたり、他の実装を作ったりできます。しかし、テストデータの誤りのせいでテストが通らないと、本来ならしなくてよい確認に時間を取られてしまいます。テストデータの誤りのせいで、回答者の時間を奪うのは避けたいです。

テストデータを検証した自分の実装に完全な自信を持てない場合は、テストデータを手で検算し、検算が済んだテストデータだけを提示します。

データの数

必要なテストデータの数は、問題の仕様によります。どう書くの過去問題では、1問につき約40個のテストデータが提示されていますが、40個以下で済むこともあれば、40個以上必要なこともあります。

データの作成方法

鍋谷さんは、テストデータの半数程度は手で作成し、残りは機械的に自動生成されているそうです。今回はそのやり方を真似しました。

機械的にテストデータを作ることで、手間を軽減できるだけでなく、うっかり見落としたコーナーケースをカバーできる可能性があるかもしれないと思いました。(もちろん、仕様を"偶然"網羅できることを期待するのは間違いです。必要と考えるテストデータを作った上での話です)

f:id:torazuka:20140512214852j:image

入力値と出力値を適当なサイズに設定する(推奨)

入力値と出力値を大きいデータ(文字列として長いデータ)にすると、次のような問題があります。

  • テストデータの生成や検証に手間がかかる
  • 大きいデータを問題ページに掲載すると、ブラウザで表示した時に見づらい

しかし、データが小さければ小さいほど良いわけではありません。たとえば、組み合わせを出力データ(期待値)とする場合、値が小さ過ぎると、テストが偶然成功したケースを検出し損ねる可能性があります。その場合は、十分なバリエーションでカバーする必要があると思います。

どう書くの過去問題では、2進数の値を16進数の値に変換して扱っているものがあります。こうすることで、データの複雑さを維持しながら、サイズを小さくできます。

解き方が複数ある問題にする(推奨)

どう書くでは、書いたコードを皆の前で発表するので、さまざまな解き方が出た方が盛り上がります。

そのために、最低2つ、できれば3つ、自分で具体的なアプローチを考えつくような問題にします。「自分では思いつかないけれど、誰かが別の方法で解いてくれるかもしれない」などと勝手に期待することには意味がありません。

解法のパターンを思いつく術については、自分にはまだ詳しいところは分かりませんので、いつか分かったら書きたいと思います。計算量を減らす方針や、腕力で解く場合の方針などが、考えるきっかけになるかもしれません。

特定のプログラミング言語に配慮する(できれば)

配慮は、2方向に行います。親切を意識した配慮と、嫌がらせを意識した配慮です。

親切

特定の言語が苦手とする処理を強要しないように、問題を設計します。フェアネスと呼んだ方が適切かもしれません。

たとえば、鍋谷さんの問題では、splitが必要な文字列を定義する際に、特定のケタ数で分割できるように設定されるそうです(1ケタと2ケタの数字が混在するデータの場合には、0埋めを指定するなどですね)。これは、データのサイズが分からないと分割できないC言語への配慮だそうです。

様々な言語の特徴を把握していなければ、きめ細かい配慮をすることは難しいですが、あらかじめ知っていれば対応できる内容もあると思います。

ただし、親切方向の配慮を必ず取り入れなければならないわけではありません。その言語が得意な処理が有効に機能しうる問題であれば、苦手な処理をあえて嫌がらせとして残しておくこともありえます。

嫌がらせ

解く際に一手間かかる要素を、問題に積極的に混ぜておきます。

  • 配列インデックスが0オリジンの言語が多いので、値の組を1オリジンにする
  • 8の倍数は計算しやすいので、7か9の倍数にする
  • 2値で済みそうなところを3値にする

他にもいろいろありますが、やりすぎると手数を増やすだけになったり、解法の選択肢を狭めてしまったりするので、注意が必要です。実際に解いて、バランスを検討するのがよさそうです。

視覚的な演出になる図表を入れる(できれば)

問題ページにぱっと目を引く図表があると、回答者が問題に興味を持って、楽しんでくれるかもしれません。

どう書くで鍋谷さんが出題された過去問題を見ていただければ、言いたいことが伝わるのではないかと思います。「ビットボンバーマン」、「サイコロを転がす」、「不良セクタの隣」などがオススメです。

普段は必死で解いているのであまり考えませんが、改めて過去問題を見ると、この洗練はすごいなぁと思います。定性的な話ですが、どう書くの問題の性質として最も好きな部分なので、最後に挙げてみました。

現時点で気づいたことは、以上です。

いつか皆で問題を出し合うイベントをやってみると、面白いかもしれませんね。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証