[機能案] library checker の双対

[MiSawa]

Library checker の双対、すなわち「問題とそれに対する実装が与えられるので、なるべく実行時間(もしくは適切にカウントしたコスト)のかかるテストケースを作れ」が出来ると、ある程度有用で面白いと思います。 例えば https://judge.yosupo.jp/problem/associative_array に対する Treap の実装が与えられているので、辿るときに訪れた頂点数の和がなるべく大きくなるような入力を作れとか。Library checker のテストケースの補強に役立つだけでなく、他のコンテストで問題の準備をしている人の参考になるかもしれません。ただ、これに面白みを感じて参加する人がどれだけ居るかは未知数です。

• 提出されたケースを primal な方の問題のテストケースとして追加できるよう、提出時にライセンスに同意してもらう必要がありそうです。
• (primal な方で複数テストケースあるのと同様に) 複数個の実装に同時に提出するほうがよいような気がします。
• 実装として、ふつうに作ったやつと、適当にランダム化したやつは両方欲しそうです。例えばフローで入力の辺をシャッフルするとか、イテレート時にランダムな順で辺を見るとかいうやつ。よりロバスト(従って有用)なテストケースが要求され、deterministic なアルゴリズムに対する入力を作るより当然難しいです。
• "解法の一覧/絞り込み" に値する機能で必要なものがだいぶ違いそうです。例えば、「この解法に対する悪いケースが見たい」とか。また、"最悪ケースでの実行時間" に値する部分で表示したいものが何になるのかちょっとわかりません。

[maspypy]

テストケースが強化されることになるならば歓迎すべき話ではあります。が、かなり難しいと思います。 そもそも簡単な問題の作問作業や、具体的な提案のあるテストケース追加作業をしてくれる人もほとんど居ない状況なので、hack ケース作成大会に熱心な人は出てこないと思っています。 コスト 0 で運営できるならまだしも、コスパはかなり悪いように個人的には感じます。

[maspypy]

十分な開発リソースがあると仮定するならば、 https://github.com/yosupo06/library-checker-problems/issues/533 の方が優先度が高い気がします。