こういう出題は許されるのか？⇒競プロで学ぶ統計学でした？

AtCoderではともかく、ほかのジャッジでは想定解の正当性の保証がされていない出題が行われることがあります。 想定解の正当性の保証が出来ていなくても、ジャッジが大量にケースを入れてちゃんと動いたからOK!という出題は可能なのか考えてみます。 例えば色々こだわると、次のような出題になると思います。

問題

長さ10000の数列が与えられる。各要素はそれぞれ1以上10000以下の整数である。次の条件を満たす部分列を探し、見つけたら出力せよ。

ジャッジ方法

あなたの提出は次のようにジャッジされる。

  • 以下を独立に100回行う。あなたのコードが少なくとも30ケースに対して正しい部分列を出力していた場合、ACとする。
    • ランダムケースを一様に$[1,10000]^{10000}$からジャッジが生成する。これは事前に作成されたものではなく、ジャッジごとに新たに作り直される。
    • このランダムケースをあなたのコードに入力し、部分列を出力した場合それが正当かを検証する

解説

解法コードについて、$[1, 10000]^{10000}$について正しい部分列を出力するケースの割合を $p$ とする。これはその解法コードのランダムケースに対して正しく動く確率である。

もし確率$p \geq 0.5$で正しい部分列を出力する解があれば、そのコードは<十分高い確率>でACする。

私たちジャッジは次のヒューリスティックを行う解答を用意しました。

そして、この解答に同様にランダムケースを5000ケース入力したら、4000ケースに対して正しい部分列を出力した。もしこの想定解法が正しく動く確率$p$が$p < 0.5$ならば、ランダムケースを5000ケース入れて4000ケースに対して正しく動く確率は<ハチャメチャ低い確率>である。よって、このジャッジ解は$p \geq 0.5$であると考えられる。

疑問

  • このような問題は許容されるのか？
  • 「よって、このジャッジ解は$p \geq 0.5$であると考えられる。」これはどういうことなの？
  • 許容される場合、ジャッジが事前に行うべきテストの量(今回でいうと4000/5000AC)は何らかの式で計算できるのか？

考察: 大嘘解法の可能性は消せない

例えば想定解が$p=0.01$であったとしても、確率$0.01^{5000}$で5000ケースに連続ACする。つまり、想定解が大嘘である可能性というのは0には出来ない。

一方で、宇宙線、突然writerの頭に隕石が、AtCoderがハッキングを食らう、など、そもそもコンテストが台無しになる可能性がそもそもそれなりにある。

典型ミス: 「想定解は(ハチャメチャ低い確率)でp < 0.5」 を言うには追加の仮定が必要

P(4000ケースAC | ($p \geq 0.5$))とP(($p \geq 0.5$) | 4000ケースAC)は違うという話。例えば、

  • こういう問題を作る
  • $p=0.01$の解法を作って5000ケース入れる
  • 4000ケースACしたら出題

これをとんでもない回数、例えば$100^{5000}$回行うと、このような問題が大量に出題され、そしてその全てが$p = 0.01$の大嘘解法となる。

もちろんこれは$100^{5000}$回の試行を要求している時点で非現実的である。全く効果のない薬をたくさん作ってテストし続けるとどれかは効果がありそうな結果が出てくる、というのと似た話。

  • 「4000/5000ケースACした」かつ「大量に試行していない」 => 「想定解は$p < 0.5$であると考えられる」
  • 「4000/5000ケースACした」かつ「$p$の事前分布が一様分布であると仮定する」 => 「想定解は(ハチャメチャ低い確率)で$p < 0.5$」

のように、追加で何らかの仮定が必要で、「4000/5000ケースACした」だけから「想定解は(ハチャメチャ低い確率)で$p < 0.5$」は数学的には言えない…ハズ

有意水準

$p$の事前分布はわからないだろうし、(今現在の)競プロ界隈のスタンス的に「writerが大量に試行していないから正しい」も広く受け入れられないと思う。なので$p$についてなにも言えなくて困る…と思いきや、こういう時のために有意水準というのがあるらしい(統計初心者)。つまり、 「$p < 0.5$なのに4000/5000ACするとんでもない確率を引いた」or「$p \geq 0.5$である」　ということならば言えるので、これで物事をやっていこうという話。

「確率 $q$ を引いた」or「X」が言えたとして、例えば $q$ が一生かけても引けないぐらいの確率(例: (1000年 / 試行にかかる時間) * q < 1)ならXは正しいと仮定して人生に問題はない？(例: 隕石は衝突しないと思い込んで行動しても人生に問題はない？)

薬の検定などと違い、テストケースをいくらでも簡単に増やせるのが強みで、それこそ$q \leq 2^{-256}$とかが達成できる問題も少なくないと思う。世の中は$2^{-256}$は起こらないということで回っているはず(例: 適当にEd25519の秘密鍵を当てられる確率が$2^{-256}$)なので、これなら大丈夫そう。

結論

  • 「$p < 0.5$なのに4000/5000ACするとんでもない確率を引いた」or「$p \geq 0.5$である」　ということならば言える。
  • こういう思想を(競プロで)許すか、許すとしてどのぐらいの確率からは個人次第。

自分の思想: とんでもない確率が$2^{-64}$とかならOK

思想についての余談

  • そもそも乱択に関する思想
    • 想定解の通る確率がケースごとに$p$以上が証明できていればOK派閥
    • 想定解の通る確率が全体で$p$以上が証明できていればOK派閥
      • ロリハ使うならケース数を公開しろ派閥がおそらくここ
    • 想定解は決定的(=確率1)アルゴリズムであるべき派閥
  • (1, 2番目の思想の場合)許せる確率$p$はいくつか
    • 全体で$\frac{1}{1000}$とか
    • 全体で$2^{-64}$とか(ハッシュの衝突など、世の中で0とされている確率ぐらい)
    • Full feedbackかにも依存しそう

自分の思想: ケースごとに$10^{-6}$ぐらいならええやろ派閥