OnlineExam 参戦記録

Codeforcesで開催されていたマラソンマッチに参加してました。

codeforces.com

問題文

オンラインの試験があります。問題は全部で5000問あり、各問題は「YES」または「NO」で解答を行います。採点については各問題ごとに正解不正解を判別し不正解の数が2000に達するまで採点が行われます。最終的な点数は採点が終了した時点の問題番号となります（正解数ではないので注意）。試験には最大100回までチャレンジできます、その間に問題の解答が変化することはありません。なるべく多くの点数を取れるように頑張ってください。

戦略

まず、大きな手がかりとして「採点したスコアの問題番号は不正解」というのがあります。例えば問題数が10で1問でも間違ったら採点終了の場合において、スコアが7だった場合は8問目は不正解ということになります。

まずこれで最大100問は不正解を正解に直すことが出来ます。

特定の範囲を指定して解答をひっくり返す

5000個の問題の中から一部を抜粋して、その部分の解答を反転させてそのスコアの増減を確認してました。

一部を抜き出して

解答を反転させる

初期の頃はこれを範囲40ぐらいで行って68000点ぐらいでした。

変化が少ない部分は分割して再調査

分割して調査していくと、特定の個所ではスコアの変動がかなり少ないところがあります。これは正解数と不正解数がその区間ではほぼ同一なことを示しているのですが、実際には図のように片方に正解が偏って、もう片方に不正解が偏っている場合があります。

その場合にはその区間を再度分割し片方の解答を反転させて再度スコアを計算します。

分割して

片方を反転させて再計算

図ではスコアが上昇したのでもう片方の領域については何も行いませんが、もし、スコアが低下した場合はもう片方の領域を反転させます。（その場合は正確なスコアの取得は行わず予測スコアを計算します

感想

シンプルな問題でしたが色々考察しがいのある問題でした。問題の環境としてtesterがもうちょっと充実していると良かったです。あと、提出間隔に制限が無いのはいいですね。