はじめてのさくもん
この記事はCompetitive Programming (1) Advent Calendar 2019 18日目の記事です。
adventar.org
記事を開いてくださったみなさんこんにちは。
ぴーよです(*- -)(*_ _)ペコリ
はじめに
皆さんは作問作業をしたことがありますか？
ぼくは最近まで作問を一切したことがなく、若い頃は特に作問に対して興味があるわけでもありませんでした。
しかし、年を取ったせいか近年では作問に対する興味が年々増加してきていて、ありがたいことに先日writerとtesterの両方の初体験をさせていただく機会があったので、記録用と今後作問を始める人への参考(になるかはわかりませんが)としてこの記事を置いておきます。٩( 'ω' )و
既に作問を息を吸うようにこなしているwriterの方々は、作問初心者の独り言だと思って温かい目で読んでいただけると助かります。
writer編
きっかけ
最近発足して徐々に勢力を高めている競技プログラミング系紅茶団体Cafe Coderがコンテストのwriterを募集してたので軽い気持ちで申し込んでみたら本当にさせていただけることになりました。
現在はサイトリニューアルに向けて開発中らしいので頑張ってほしいです。
実際にやったこと
問題作成
とりあえず、問題が作れないと何もはじまらないのでまずは問題を作りました。
現状、自分で問題を作るときには
- 解法に使うアルゴリズムを固定してその解法が得られるような問題を作ってみる
- 問題のシチュエーションとか設定とかを先に決めて、できた問題を自分で実際に解いてみる 解けたら難しくなるように制約を強化していく
の二パターンを使って問題を錬金しています。(他の錬金術があったら勉強したいので教えてほしいです)
両方とも一応デメリットがあって、前者は作った後に既出の問題や全人類に解かれそうな見た目をしている問題になりやすく、後者はある程度自分が問題を解けないと普通に思いついた問題が解けなくて没になります。
ぼくは今のところ後者の方法が好きですが実力が伴っていないので、大量の没シチュエーションを抱えて生きています。
思いついた問題はとりあえずHackMDにまとめるようにしています。
HackMDは編集や共有が楽な上に数式とかも簡単にかけてとても便利です。
テストケース作成
問題文ができたらテストケースを作成します。
テストケースはいちいち手で作っていてはさすがに追いつかないので、基本的には制約に合うように乱数でたくさんテストケースを作ってランダムでは落とせないようなコーナーケースを手動で入力して追加するというように行いました。
作問未経験だったぼくはテストケースを生成するコードを一から書いていたのですが、実はこれは原始人のやり方であることが後日判明しました。
というのも、テストケース作成を一からちゃんとやるのは大変なので通常はRimeと呼ばれる便利ツールを使ってテストケースを作成するらしいです。もっと早く教えてよ・・・・.
Rimeの使い方に関してはbeetさんの記事に詳しくまとまっています。
beet-aizu.hatenablog.com
また、今回はやらなかったのですが構築問題みたいな複数の答えが正解になりうるような問題だと送られてきた解答が正解かどうかをジャッジ側で判定するプログラムを書くこともあるらしいです。
ジャッジ側も現実的な時間で判定できないとジャッジが終わらないという制約があるので、ジャッジ側のプログラムを書くのも競プロっぽくて面白いですね。
解説作成
今回は特に指定がなかったのでTeXで書きました。
問題文作成の時もそうでしたが、解説を作るにあたってさらに日本語力が求められます。
解説も下書きをHackMDなどに一度下書きした方がいいのかもしれません。
日本語力だいじ！！！！！
tester編
きっかけ
ぼくの所属する学科では競プロがかなり盛ん*2で、学科内の人だけでコンテストを開くという企画が計画されていました。
@i_am_karen_kujo (‥ )ﾝ?
— ぴーよ@競プロ (@ywmt_kpr) November 6, 2019
ぼくも作りたいヾ(⌒(ﾉｼ >ω<)ﾉｼ
— ぴーよ@競プロ (@ywmt_kpr) November 6, 2019
やるやるー
— ぴーよ@競プロ (@ywmt_kpr) November 6, 2019
駄々をこねてたらtesterをやらせてもらえることになりました。
実際にやったこと
引き受けたときは正直testerってなにするの？みたいなところがあったんですが、やってみてわかりました。
ざっくり言うと、testerの仕事は参加者の気持ちで問題を解いてその問題に不備がないかどうかをチェックっしてwriterをアシストすることです。
要するに他人の問題の粗探しをして、いちゃもんをつけまくれば優勝です。(怒られそう)
今回は経験者がいなかったのでとりあえず、
- 制約が間違ってないかをassertなどを使って調べる
- そもそもその問題がちゃんとACできるかをチェック
- 嘘解法がちゃんと落ちるかを調べる
- その問題の体感難易度(AtCoder～点相当など)をwriterに報告する
の四つをメインにやりました。
中でも楽しかったのは嘘解法チェックで、こういう粗探しみたいな作業はもともと好きなので思うままに嘘解法を投げまくってました。*3
結果的にコンテストを無事に開催することができ、コンテスト中は作問slackも盛り上がっていました。*4
おわりに
ここまで記事にお付き合いいただきありがとうございました。作問ストックはまだ何問かあるのでまた機会があれば何かのコンテストで出題したいと思っているのでその時にはぜひよろしくお願いします。(*`･ω･)ゞ
