リアクティブ形式の問題についてのまとめ
Latest Author
yuki2006
/Date 2024-12-02 11:38:55 / Views 8110リアクティブ形式の問題とは
リアクティブ形式の問題は通常の問題と異なり、ジャッジ側のプログラムと対話的に実行する必要がある問題です。
そのため、未知の情報について質問により推定を行ったり、相手とゲームで対戦して勝利する必要があったり、渡されるクエリをリアルタイムに処理したりする必要があります。
リアクティブ形式の問題における注意点
便宜上、提出したプログラムのことを回答プログラム、ジャッジ側のプログラムのことを応答プログラムと呼ぶことにします。
応答プログラムが入力を受け取ろうとしているときに回答プログラムも入力を受け取ろうとすることによってデッドロックが発生し不正解になってしまうことがよくあります。
また、標準出力に書き込んだつもりが、実際には書き込まれておらずこのような状況に陥ることもあります。出力後は必ずflushするようにしましょう。
同様に出力を受け取らなかったために、デッドロックが発生してしまい、不正解になってしまうこともあります。注意しましょう。
当然のことですが、正しいフォーマットで出力しなかった場合、不正解になってしまいます。こちらもよく確認しましょう。
応答プログラムが終了しているのに、回答プログラムが出力をすると結果は不定になります。（多くの場合はREになります。）
その為、応答プログラムが終了する条件の場合は、回答プログラムも終了するようにしましょう。
問題例
リアクティブ問題に慣れましょう。コードを書いて、提出ページでコードを提出してみましょう。
便宜上、未知の情報を推定するタイプの問題を推定型、ゲームを行うタイプの問題を対戦型、渡されるクエリをリアルタイムに処理するタイプの問題をリアルタイム処理型と呼ぶことにします。
推定型の問題
対戦型の問題
リアルタイム処理型の問題
まだありません。
回答時のよくある質問
C++のendlを使って改行したコードはACなのに、printf の"\n"を使ったコードはTLEになるのはなぜか？
まず前提知識として、リアクティブ問題はflushをする必要があります。一般的に出力関数はすぐに出力されるのではなくパフォーマンスの問題で、バッファリングされるためです。
std::endlは改行されるだけでなくflushもされるという効果があります。https://cpprefjp.github.io/reference/ostream/endl.html
printfの"\n" などはflushされる効果はありません。逆に言うとprintfの後に自分でflushすれば大丈夫です。
「printfでも手元のターミナルで実行したらすぐに反応がある」のはなぜか？
https://linuxjm.osdn.jp/html/LDP_man-pages/man3/setbuf.3.htmlもし ストリームが (通常、 stdout がそうであるように) ターミナルを参照する場合には、ファイルは line buffered となる。標準エラー出力 stderr はデフォルトでは常に unbuffered である。により、ターミナルに対しては「line buffered」なのですぐに反応がある。
リアクティブジャッジではターミナル扱いではないらしく、block bufferedになっておりブロックサイズのデータの書き込みで始めて出力される模様
（ブロックサイズはディスクフォーマットによって決められている値の模様 https://www.techscore.com/blog/2016/12/04/veryfy-write-buffer-4kb-8kb/）
よって手元のターミナルでは動くのにジャッジでは
TLEになることがありうる。また、
setvbuf関数などでmodeを変更しておく方法も可能。（この方法でのパフォーマンスに関しては、測定していないので不明）
作問時の注意点
リアクティブ問題は通常の問題と異なり、入出力にかかる時間、より正確には書き込みを行うのにかかる時間が非常に大きいです。だいたい10000回程度のやりとりで数秒かかるものと考えるのが良いでしょう。
リアルタイム処理型の問題を作る場合はこちらに十分注意しましょう。
また、通常の問題に比べてデバッグが困難になる傾向が多いです。サンプル等は詳細に書いた方が良いでしょう。
No.257 N言っちゃダメゲーム (3)のように、問題によっては途中から応答に答えなくても解を求めることが可能なものもあります。
その場合、回答プログラムが先に終了し、応答プログラムが出力してしまうと結果的にWAになる場合があります。
これを回避するには SIGPIPEをignoreし、writeやprintした結果を見るようにするプログラムにしてください。
参考: No.3013 Trigger EPIPE のジャッジコード
コンテスタント側が「応答プログラムが終了する条件の場合は、回答プログラムも終了するようにしましょう。」をなるべく行えるようにしましょう。 例えばコンテスタント側が不正な値出力をしたとき、ジャッジプログラムが直ちに終了してしまうとコンテスタント側は返しの入力を待っているかもしれません。 「コンテスタントが何か変なことをしたらジャッジは -1 を出力して終了する」のような仕様にしておくとよい場合があります。