コードが通る確率（上）

time(0)を使ってみる

time(0)を使ったコードを送信する場合、Acceptされる可能性について考えてみる。私の書いたコードを使いたいところなのだが、文字リテラルが図形文字でないので、説明には向いていない。というわけで、wajさんが昨日の日記にコメントしてくれたものを使わせていただく。

main(d){for(d=time()&1?'zMM':90;d*=.4;)puts(d&2?"no":"yes");}

このプログラムは、実行に0.020〜0.030ミリ秒程度かかる。また、テストではプログラムが2回実行されるが、例えばシェルスクリプトなどで連続して実行させると、2回目が実行されるまでにタイムラグがおよそ0.050ミリ秒ほどかかる。Acceptされるためには、time関数が返す値(秒)が、奇数から偶数に変わる瞬間と、1回目と2回目が実行される境でなければならず、そのタイミングは約0.075/2000*100=0.00375%と異常に低く、30000回に一回の計算になってしまう。しかしながら、この手のコードを何度も送信していると、大体100回前後で通ってしまうことが多く、1回目のテストが終了したところで、2回目に入る前になんらかの処理(1回目のテストがWAならその時点で終了するわけだから、最低そのあたりの判定プログラムは実行されるはず)が行われて実際には平均20ミリ秒程度のタイムラグがあると予想される。

しかし、これでも通すにはかなりの根性が要る。もう少し高確率で通す方法は無いのか。ということを考えていて、ひとつアイデアが浮かんだ。

つづく