競プロ作問を支える技術

Transcript

1. 競プロ作問を支える技術
   @tsutaj
   

   View Slide

2. 自己紹介
   ● 各種コンテストに tsutaj という名前で出ています
   ○ 最近は長期マラソン型コンテストによく出てます
   ● これまで、競プロの作問準備にしばしば関わってきました
   ○ 学生のとき：北海道大学の有志セット
   ○ 現在：ICPC OB/OG 会で提供する模擬国内予選・模擬地区予選
   ● 今回は作問作業で使われている技術の話をします
   

   View Slide

3. 競技プログラミングの問題に必要なもの
   ● 問題文
   ● データセット（入力ファイル・想定解法の出力ファイル）
   ● ジャッジ用プログラム（問題によっては必要）
   ● 解説
   問題文を読む 参加者が実装 ジャッジに提出
   

   View Slide

4. よくあるミス 1
   ● 想定解法にミスがあり、正しい解法が通らない
   ○ コーナーケースを見落としていた、間違ったものを想定解としてセットし
   てしまったなど、原因は様々
   ○ 最もしてはいけない部類のミスで、レートが変動するコンテストの場合は
   Unrated になりがち
   問題文を読む 参加者が実装 ジャッジに提出
   何をしても WA になるなぁ
   想定解法が
   間違ってました...
   

   View Slide

5. よくあるミス 2
   ● 問題文に書いてある制約と、データセットの制約が異なる
   ○ たとえば、想定よりも大きい入力が来ると、意図しない TLE や配列
   外参照のおそれがある
   問題文を読む 参加者が実装 ジャッジに提出
   　　　　 だよ！
   　　　　　　のケースも
   ありました...
   int A[100010]; …
   よし！提出したろ！
   

   View Slide

6. 競技プログラミングの問題に必要なもの
   ● 齟齬がなく、内容が正確な問題文
   ● 問題文の制約通りのデータセット
   ● ジャッジ上で正確かつ高速に動くジャッジ用プログラム
   ● 解説
   問題文を読む 参加者が実装 ジャッジに提出
   

   View Slide

7. 競技プログラミングの問題に必要なもの
   ● 齟齬がなく、内容が正確な問題文
   ● 問題文の制約通りのデータセット
   ● ジャッジ上で正確かつ高速に動くジャッジ用プログラム
   ● 解説
   問題文を読む 参加者が実装 ジャッジに提出
   コンテストを壊さないためには、
   問題文・データセット・ジャッジプログラムに
   正確性や再現性が求められる！
   

   View Slide

8. 主な作問支援ツール
   ● Rime
   ○ データセット作成支援
   ○ 想定解法・想定誤解法のチェック
   ■ ジャッジプログラムを含んだ問題のチェックもできる
   ○ ICPC OB/OG 会の有志が開発中
   ● statements-manager
   ○ 問題文作成支援
   ■ 問題制約を正確に書くために使用
   ○ tsutaj が開発中！
   

   View Slide

9. Rime
   ● できること
   ○ データセット作成を自動で回す
   ○ データセット確認を自動で回す
   ■ データセットは制約を満たしているか？
   ○ 解法プログラムを自動で回す
   ■ 想定解が通って、想定誤解法が通らない状態か？
   ■ 解法は複数存在するのが望ましい
   

   View Slide

10. testlib
    ● データセット確認には testlib というライブラリがよく使われる
    ○ 空白・改行が意図通り入っているか
    ○ データの値が制約通りか
    整数読み込み
    改行読み込み
    制約チェック
    整数読み込み
    （値の上限・下限あり）
    空白読み込み
    改行読み込み
    

    View Slide

11. testlib の注意点
    ● ランダム入力を作る機能もありますが、オススメしません！
    ○ 線形合同法が使われているが、乱数の周期が短い
    ○ より周期の長いもの（最低限 XorShift）を使いましょう
    ● 余談：C++ の distribution も環境依存なので使うべきでない
    ○ 誰がプログラムを回しても同じデータが出ることが理想
    

    View Slide

12. statements-manager
    ● できること
    ○ 問題文に書かれる制約と、データセット作成に使われる制
    約を合わせられる
    ■ 問題文には　　　　　と書いてあるのに、データセットが
    　　　　　　 を満たしているとヤバい
    ■ statements-manager で制約をまとめると、制約の情報を問題
    文でもデータセット作成でも使える
    ○ サンプルデータセットも同様に合わせられる
    

    View Slide

13. statements-manager
    問題文
    (Markdown)
    設定ファイル
    (toml)
    制約が自動で
    置換される
    サンプルが自動で
    埋め込まれる
    

    View Slide

14. さいごに
    ● コンテストをミスなく準備するのはかなり大変
    ○ 今回のスコープ外ですが、問題文を齟齬なく書くのも大変
    ● 何らかの理由で Unrated になっても、次のコンテストを楽し
    みにして、また参加しましょう！
    ● 興味のあるかたは作問にも挑戦してみてください
    ○ yukicoder では有志コンテストがよく行われています
    

    View Slide