典型ランダムケースの生成

[kmyk]

「ほとんど同じ文字な文字列を生成する機能」「高度合成数や素冪を生成する機能」「ほとんどウニなグラフを生成する機能」などです。

やることもその価値も明らかなはず。
そういう機能をライブラリとして使えるように用意したい。実装の枠組みを整えれば、「列が与えられる問題のテストケースであって撃墜力が高いものをたくさん考えてください」とか「頂点数 N の木 (頂点にラベル付き) は全体で N^{N-1} 個あるが、この中から一様ランダムにひとつ作れ」とかをやることになるので、普通に競プロになる。手伝ってくれる人もわりといそう。

問題はどこにどう実装するか。言語は C++ でよいだろう。場所について、以下のような選択肢があるはず。

• Library-Checker に足させてもらう
  • common/random.h に典型ケースを生成する機能がほしい yosupo06/library-checker-problems#400
  • 利用先と開発者とがセットで揃ってるので発展が速いはず
• このリポジトリ内に持つ
  • 作りかけのものがある onlinejudge_random/__init__.py
  • 短期的にはもっとも楽だが、役割が違うものを混ぜることになるため、これを選ぶべきではない
• 外部にライブラリを作る
  • 私がやるなら online-judge-tools/random-cases みたいなのを作る
  • 誰かやる気のある人にまったく独自でやってもらってもよさそう

関連:

• 作問用機能 作問用機能 #35
• generator.py の C++ 版を書く generator.py の C++ 版を書く #5
• cc @monkukui