library-checker-problems
library-checker-problems copied to clipboard
yosupo06
部分点システム
#77 のように、計算量によって実装量が数倍変わるような問題が存在する、こういうのをどうするか？
- このジャッジの思想としては、大きいほうをベリファイできるべき
- 小さいほうの実装がベリファイできないというのは避けたい
- ICPC等実装量が短い方を選択するシチュエーションはある
- そもそも大きいほうを書くためには大体小さいほうを書くはずで、そこでベリファイできると精神が安定する
よってこのジャッジとしては大きいほうと小さいほう両方をチェックできる仕組みを導入したい
そこで現状考えているのは2つで、
- 問題を2種類作る
- general_matching_small / general_matching など
- 問題に部分点を導入する
- AC(oox) みたいに表示する
問題を2種類作る Pros:
- 追加の実装が要らない
Cons:
- 例えばN=1000が限界だと信じてた問題が後年N=100,000で解けることが分かったりしたら、どうするか？
- テストケースの追加をどうするか(2つの問題に両方追加？)
問題に部分点を導入する Pros:
- 変更に対して強靭
- わかりやすい
Cons:
- どうやって部分点のファイルを指定するのか？採点はどうするのか？など様々な設計の問題が発生
ドラフト(随時更新)
変数名とか深く考えていません
要件リスト
- 色んな制約の部分問題を後から追加できるようにしたい(より小さい制約, より大きい制約, はたまたMODが素数とか…)
- task.mdやverify.cppを部分点の個数用意するのはやめたい(problems)
- (問題の種類, 制約)のタプルについて一意なIDを振りたい(N=2000に提出した問題が後日N=200,000でリジャッジされる、とかは避けたい)
- CIから回すときは(AC / それ以外)の2値以外は扱いたくない(だろう)
満たしたい条件が多すぎる(素朴)
library-checker-problems
部分点っぽいものを導入
info.tomlに
[[subtasks]]
name = "default"
case = ['example_00.in', 'small_*.in']
[[subtasks]]
name = "big"
case = ['example_*.in', 'small_*.in', 'random_*.in']
みたいになんらかのケースの集合を指定する。subtaskには順序関係を定義するのが自然(=dictではなくarray)で、基本的には制約のサイズ順とする(=defaultが一番上とは限らない, 上に追加したり下に追加したりする)
judge.yosupo.jp
- 部分点ごとに提出を分けることはしない
- とりあえずは提出すると全ケース走る(もし仮にジャッジキューのつまりが気になるほど使用者数が増えたら、その時にノックダウンなどを検討する)
- 現状はsubmissionごとにstatus(=AC, WA, ...)を持っていたが、これを(submission, 部分点)ごとに持つようにする(submissionの中に問題IDは入っている)
- submissionの中に部分点の情報は入れたくない あくまでsubmissionは問題と紐づいている
(問題, 部分点)ごとに一意なURLか何かを与えないと不都合が生まれないか？
少なくとも
- 色んな制約の部分問題を後から追加できるようにしたい(より小さい制約, より大きい制約, はたまたMODが素数とか…)
これは満たすようにするので、現状制約をどうするかで悩んでいる問題は一番自然な制約で作ってしまうことにします
部分点ごとに一意な URL はかなりほしいです。library-checker-problems を競プロライブラリの CI から利用することを考えたとき、どの部分点のものを使うのかの指定が簡単だとうれしいので
部分点の表示の仕方として、
- 「xxxを求めてください ~~~ (制約1) N <= 1000 (制約2) N <= 100,000」 (JOI, IOI形式)
- 「xxxを求めてください N <= 1000」「この問題はyyyと制約のみが異なります。 xxxを求めてください N <= 100,000」(CF形式)
の2種類があると思っています。で、今のところ前者で行きたいと思ってます。全体的に「問題を2種類作る」より「問題に部分点を導入する」の方向性で進めたいと思っているからです。
部分点ごとに一意な URL はかなりほしいです。library-checker-problems を競プロライブラリの CI から利用することを考えたとき、どの部分点のものを使うのかの指定が簡単だとうれしいので
これが問題で、前者の形式を採用すると部分点ごとにURLを与えにくいです。
なので現状の案としては
問題概要
aplusbを求めてください
制約(default)
- 0 <= A, B <= 1e9
- oj用タグ: https://judge.yosupo.jp/problems/aplusb#default (押すと←がクリップボードにコピーされるボタン)
制約(small)
- 0 <= A, B <= 100
- oj用タグ: [https://judge.yosupo.jp/problems/aplusb#small] (同上)
のようにURLアンカー(正式名称知らず)や、aplusb?subtask=smallのように(特に何にも使わない)GETパラメーターなどで区別することを考えています。