テストケースハッシュ化

概要

テストケースの入力を適当な方法でハッシュ化し、実行時間を調整することでハッシュ値を特定します。

例えば出力が Yes/No の問題であれば、ハッシュ値だけを見て Yes/No を決めることで AC できます。

例題

解法

出力が Yes/No のマルチテストケースでない問題です。

試しに text で Yes と提出してみると、30 AC、23 WA でした。

テストケースが少ないので本手法による AC が狙えます。

まずは入力をハッシュ化します。

雑に線形合同法っぽくしておけばいいでしょう：

code:hash.cpp

mint hash = n;

rep(i, (n - 1) * 4) {

int a;

cin >> a;

hash *= 12345;

hash += a;

}

実行時間のブレが W = 5ms 未満だと仮定します。

TL が 6000ms なので、1 回の提出で 6000 / 5 - 1 = 1199 通りを区別できます。

そこで hash の代わりに hash.val() を 1199 で割った余り H を特定することにします。

次のようなコードを書いて (H+1)*W msec だけ空ループを回し、実行時間を調整します：

code:sleep.cpp

ll lim = (H + 1) * W;

while (1) {

auto now = chrono::system_clock::now();

auto msec = chrono::duration_cast<chrono::milliseconds>(now - start).count();

if (msec >= lim) break;

}

これで提出してみると、実行時間は 5796 ms でした。

そこで、次の提出では H = 5796 / W - 1 のときだけ空ループを回す代わりに Yes を出力して即終了します。

これで AC が 1 増えれば H = 5796 / W - 1 のときは Yes が正解、AC が増えなければ No が正解と特定できます。

同様の手順をテストケース数 + 1 回分繰り返せば、i 回目の提出では降順 i 番目の大きさをもつ H と、降順 i - 1 番目の大きさをもつ H に対する正しい出力を特定できます。

ハッシュが衝突した場合は、代わりに H = hash.val() / 1199 % 1199 を使うなどすれば対処可能です。

提出

他の使用例

入力が少ないパターンです。

この場合はハッシュ化せず、例えば 499 進表示するなどしてテストケースを完全に特定できます。

後は手元で TLE コードを実行して答えを計算し、埋め込んで提出すれば AC できます。

マルチテストケースの問題なので一見邪道テクには強そうです。

さて、嘘解法 A を提出してみたところ惜しくも 2 WA でした。

そこで落ちた 2 ケースのハッシュ値を特定し、その 2 ケースだけ別の嘘解法 B に切り替えてみます。

なんと AC することができました。

（当時は問題毎のステータスや実行時間が表示される仕様だったのでもっと楽でした。）

元ポスト