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
View Slide
自己紹介● 各種コンテストに tsutaj という名前で出ています○ 最近は長期マラソン型コンテストによく出てます● これまで、競プロの作問準備にしばしば関わってきました○ 学生のとき:北海道大学の有志セット○ 現在:ICPC OB/OG 会で提供する模擬国内予選・模擬地区予選● 今回は作問作業で使われている技術の話をします
競技プログラミングの問題に必要なもの● 問題文● データセット(入力ファイル・想定解法の出力ファイル)● ジャッジ用プログラム(問題によっては必要)● 解説問題文を読む 参加者が実装 ジャッジに提出
よくあるミス 1● 想定解法にミスがあり、正しい解法が通らない○ コーナーケースを見落としていた、間違ったものを想定解としてセットしてしまったなど、原因は様々○ 最もしてはいけない部類のミスで、レートが変動するコンテストの場合はUnrated になりがち問題文を読む 参加者が実装 ジャッジに提出何をしても WA になるなぁ想定解法が間違ってました...
よくあるミス 2● 問題文に書いてある制約と、データセットの制約が異なる○ たとえば、想定よりも大きい入力が来ると、意図しない TLE や配列外参照のおそれがある問題文を読む 参加者が実装 ジャッジに提出 だよ! のケースもありました...int A[100010]; …よし!提出したろ!
競技プログラミングの問題に必要なもの● 齟齬がなく、内容が正確な問題文● 問題文の制約通りのデータセット● ジャッジ上で正確かつ高速に動くジャッジ用プログラム● 解説問題文を読む 参加者が実装 ジャッジに提出
競技プログラミングの問題に必要なもの● 齟齬がなく、内容が正確な問題文● 問題文の制約通りのデータセット● ジャッジ上で正確かつ高速に動くジャッジ用プログラム● 解説問題文を読む 参加者が実装 ジャッジに提出コンテストを壊さないためには、問題文・データセット・ジャッジプログラムに正確性や再現性が求められる!
主な作問支援ツール● Rime○ データセット作成支援○ 想定解法・想定誤解法のチェック■ ジャッジプログラムを含んだ問題のチェックもできる○ ICPC OB/OG 会の有志が開発中● statements-manager○ 問題文作成支援■ 問題制約を正確に書くために使用○ tsutaj が開発中!
Rime● できること○ データセット作成を自動で回す○ データセット確認を自動で回す■ データセットは制約を満たしているか?○ 解法プログラムを自動で回す■ 想定解が通って、想定誤解法が通らない状態か?■ 解法は複数存在するのが望ましい
testlib● データセット確認には testlib というライブラリがよく使われる○ 空白・改行が意図通り入っているか○ データの値が制約通りか整数読み込み改行読み込み制約チェック整数読み込み(値の上限・下限あり)空白読み込み改行読み込み
testlib の注意点● ランダム入力を作る機能もありますが、オススメしません!○ 線形合同法が使われているが、乱数の周期が短い○ より周期の長いもの(最低限 XorShift)を使いましょう● 余談:C++ の distribution も環境依存なので使うべきでない○ 誰がプログラムを回しても同じデータが出ることが理想
statements-manager● できること○ 問題文に書かれる制約と、データセット作成に使われる制約を合わせられる■ 問題文には と書いてあるのに、データセットが を満たしているとヤバい■ statements-manager で制約をまとめると、制約の情報を問題文でもデータセット作成でも使える○ サンプルデータセットも同様に合わせられる
statements-manager問題文(Markdown)設定ファイル(toml)制約が自動で置換されるサンプルが自動で埋め込まれる
さいごに● コンテストをミスなく準備するのはかなり大変○ 今回のスコープ外ですが、問題文を齟齬なく書くのも大変● 何らかの理由で Unrated になっても、次のコンテストを楽しみにして、また参加しましょう!● 興味のあるかたは作問にも挑戦してみてください○ yukicoder では有志コンテストがよく行われています