Upgrade to Pro — share decks privately, control downloads, hide ads and more …

競プロ作問を支える技術

 競プロ作問を支える技術

2023/05/30 社内 LT 会の発表資料を加筆修正したもの

Rime: https://github.com/icpc-jag/rime
testlib: https://github.com/MikeMirzayanov/testlib
statements-manager: https://github.com/tsutaj/statements-manager

tsutaj

May 30, 2023
Tweet

More Decks by tsutaj

Other Decks in Technology

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