physics0523's 精進ログ

主に競プロの面白い問題の解法をメモします

嘘解法のすゝめ AtCoderの仕様編

(案の定)指摘があったので最初に断っておきます。この記事はTLE解を投げまくるというかなり危険な手段の提案です。これはある程度通る可能性のある乱択を押し切る、といった手段の1つとしての提唱であり、無意味なTLEを投げ続けてジャッジを詰まらせることを助長するものではありません。https://twitter.com/akensho/status/1179087615745642496でも言及されているように、度を越えると垢BANを喰らう可能性もあるので、これを万一行うとしても節度をもってお願いします。(個人的には10提出してすべてTLEならもう絶望的なのでこの方針では諦める…といった尺度を推奨しておきます。)

前回のブログではPure(ABC142-F)を探索順乱択+枝刈りの嘘解法通すおはなしをしました。

嘘解法のすゝめ PURE(ABC142-F)編 - physics0523's 精進ログ

さて、今回は通った原因をもう一度精査してみてわかったことがあるので書きます。

 

まず、chokudai氏のこのツイートをご覧ください。

 もしこの時点からAtCoderの仕様に変更が生じていなければ、AtCoderではあるコードについてTLEが下されるまでに3度のチャンスがある、ということになります。

 

今回の僕の(同じコードなのにTLEと実行時間に余裕のあるACが混在する)嘘解法への仮説として、これを逆用した形になった可能性があるということを提唱します。

 

今回の僕のアルゴリズムには、ざっくり言うと、

「グラフから頂点を順に乱択して検証、条件を満たさなければその頂点を削除して続行」

という性質がありました。

「グラフから頂点を順に乱択して検証」という部分が仮に最悪指数オーダーでも、平均的な計算量がそう大きくならない可能性があるなら間に合ってしまいます。

さらに、頂点を削除して続行することによって、グラフの連結性が損なわれたりして部分問題となった問題のサイズが急速に(最善だとlogペース)落ちやすい、といった面でも乱択で当たりをツモれば計算量として優位になる可能性があったのでしょう。

 

決定的な決め手は、「乱択のチャンスが3度ある」ことです。

というのも、(上で説明した通り、)僕の解法は実行時間に大きなばらつき(乱数のシード依存)がありました。実際、同じコードでも64msのACから2000msを超えるTLEまでが混じっていました。

ここで、乱数のシードを現在時刻に設定すると、異なるシードを3つ試せることになります。もしそれが1つでも優位なシードであれば、そのテストケースは通過できてしまう、ということになります。

 

では、乱択による実行時間の大きなばらつきをどのように精査するか、それはAtCoderの[13/50]のような表示を睨んで、どこのケースで詰まる(かTLEが出る)かがある程度異なれば、シードへの依存性が高い、ということが推察できます。

 

結論としては、

  • AtCoderではTLE検証のためコード実行が3回ほど行われている(可能性が高い)
  • 実行時間がシードに大きく依存する場合、シードを3つ試せるような実装(時刻をシードに取る)をすることによって、間に合う確率を上げることができる
  • シードへの依存性は詰まるケースを見て判断できる可能性がある

といったところでしょうか。

もし、こういった性質を見かけたら、何度かTLE判定を喰らったとしても投げているうちにひょっとしたら間に合う…なんてことがありえるかもしれません。(実際、数ケース程TLEしたりしなかったりする…みたいなシチュエーションだと試す価値はあると思います。)

ちなみにこの仕様の場合なら、もしかすると計算時間を短くするために無理してWAな解を出力するよりおとなしくTLEした方がいいかもしれません。

それでは、皆さん、よい嘘解法乱択ライフを…