reactive.html

<title>リアクティブ形式の問題についてのまとめ</title>

<h2 class="shadow">リアクティブ形式の問題とは</h2>
<p>
リアクティブ形式の問題は通常の問題と異なり、ジャッジ側のプログラムと対話的に実行する必要がある問題です。<br>
そのため、未知の情報について質問により推定を行ったり、相手とゲームで対戦して勝利する必要があったり、渡されるクエリをリアルタイムに処理したりする必要があります。<br>
</p>

<h2 class="shadow">コミュニケーション形式の問題とは</h2>
<p>
コミュニケーション形式の問題はリアクティブ形式の一種で、<b>同じプログラムが複数プロセスで動作</b>し、ジャッジを介して互いに通信する問題です。<br>
各プロセスには異なる入力が与えられ、協力して解を求める必要があります。<br>
</p>
<h3 class="shadow">コミュニケーション形式の特徴</h3>
<ul>
<li>同じソースコードが複数プロセスとして起動される</li>
<li>各プロセスには固有の入力が与えられる</li>
<li>プロセス間の直接通信はできず、ジャッジプログラムを介してやり取りする</li>
</ul>

<h3 class="shadow">リアクティブ・コミュニケーション形式における注意点</h3>
<p>
便宜上、提出したプログラムのことを回答プログラム、ジャッジ側のプログラムのことを応答プログラムと呼ぶことにします。
</p>
<p>
応答プログラムが入力を受け取ろうとしているときに回答プログラムも入力を受け取ろうとすることによってデッドロックが発生し不正解になってしまうことがよくあります。<br>
また、標準出力に書き込んだつもりが、実際には書き込まれておらずこのような状況に陥ることもあります。出力後は必ずflushするようにしましょう。<br>
同様に出力を受け取らなかったために、デッドロックが発生してしまい、不正解になってしまうこともあります。注意しましょう。
</p>
<p>
当然のことですが、正しいフォーマットで出力しなかった場合、不正解になってしまいます。こちらもよく確認しましょう。
</p>
<p>
    応答プログラムが終了しているのに、回答プログラムが出力をすると結果は不定になります。（多くの場合は<code>WA</code>になります。）<br>
    もちろん、回答プログラムが終わらない場合は<code>TLE</code>になります。<br>
    応答プログラムが終わっていたものに対して出力してもEPIPEにはならないので気をつけてください。<br>
    もし、そのケアをしなった場合、普段は起こらない出力関数で<code>RE</code>になり、見つけにくいバグになると考えるためのジャッジ側の仕様です。
    <br><br>
    その為、応答プログラムが終了する条件の場合は、回答プログラムも終了するようにしましょう。
</p>

<h3 class="shadow">問題例</h3>
<p>
リアクティブ・コミュニケーション問題に慣れましょう。コードを書いて、提出ページでコードを提出してみましょう。<br>
便宜上、未知の情報を推定するタイプの問題を推定型、ゲームを行うタイプの問題を対戦型、渡されるクエリをリアルタイムに処理するタイプの問題をリアルタイム処理型と呼ぶことにします。
</p>
<h4 class="shadow">推定型の問題</h4>
<p>
    <a href="https://yukicoder.me/problems/551">No.246 質問と回答（★★）</a><br>
</p>
<p>
    <a href="https://yukicoder.me/problems/687">No.253 ロウソクの長さ（★★★）</a><br>
</p>
<p>
    <a href="https://yukicoder.me/problems/721">No.282 おもりと天秤(2)（★★★）</a><br>
</p>

<h4 class="shadow">対戦型の問題</h4>
<p>
    <a href="https://yukicoder.me/problems/708">No.257 N言っちゃダメゲーム(3)（★★）</a><br>
</p>
<h4 class="shadow">リアルタイム処理型の問題</h4>
<p>
    まだありません。
</p>

<h2 class="shadow">回答時のよくある質問</h2>

<h3 class="shadow"> C++のendlを使って改行したコードは<code>AC</code>なのに、printf の"\n"を使ったコードは<code>TLE</code>になるのはなぜか？</h3>
<p>
   まず前提知識として、リアクティブ問題はflushをする必要があります。一般的に出力関数はすぐに出力されるのではなくパフォーマンスの問題で、バッファリングされるためです。<br>
   <br>
   <code>std::endl</code>は改行されるだけでなくflushもされるという効果があります。<a href="https://cpprefjp.github.io/reference/ostream/endl.html">https://cpprefjp.github.io/reference/ostream/endl.html</a>  <br><br>

   printfの"\n" などはflushされる効果はありません。逆に言うとprintfの後に自分でflushすれば大丈夫です。<br><br>

   <h4 class="shadow">「printfでも手元のターミナルで実行したらすぐに反応がある」のはなぜか？</h4>

   <a href="https://linuxjm.osdn.jp/html/LDP_man-pages/man3/setbuf.3.html">https://linuxjm.osdn.jp/html/LDP_man-pages/man3/setbuf.3.html</a>
   <pre>もし ストリームが (通常、 stdout がそうであるように) ターミナルを参照する場合には、ファイルは line buffered となる。標準エラー出力 stderr はデフォルトでは常に unbuffered である。
   </pre>
    により、ターミナルに対しては「line buffered」なのですぐに反応がある。<br>
    リアクティブジャッジではターミナル扱いではないらしく、block bufferedになっておりブロックサイズのデータの書き込みで始めて出力される模様<br>
    （ブロックサイズはディスクフォーマットによって決められている値の模様 <a href="https://www.techscore.com/blog/2016/12/04/veryfy-write-buffer-4kb-8kb/">https://www.techscore.com/blog/2016/12/04/veryfy-write-buffer-4kb-8kb/</a>）<br><br>

    よって手元のターミナルでは動くのにジャッジでは<code>TLE</code>になることがありうる。<br><br>

    また、<code>setvbuf</code>関数などでmodeを変更しておく方法も可能。（この方法でのパフォーマンスに関しては、測定していないので不明）

</p>

<h2 class="shadow">作問時の注意点</h2>
<p>
リアクティブ・コミュニケーション問題は通常の問題と異なり、入出力にかかる時間、より正確には書き込みを行うのにかかる時間が非常に大きいです。だいたい10000回程度のやりとりで数秒かかるものと考えるのが良いでしょう。<br>
リアルタイム処理型の問題を作る場合はこちらに十分注意しましょう。
</p>
<p>
また、通常の問題に比べてデバッグが困難になる傾向が多いです。サンプル等は詳細に書いた方が良いでしょう。
</p>
<p>
    <a href="https://yukicoder.me/problems/no/257">No.257 N言っちゃダメゲーム (3)</a>のように、問題によっては途中から応答に答えなくても解を求めることが可能なものもあります。<br>
    その場合、回答プログラムが先に終了し、応答プログラムが出力してしまうと結果的に<code>WA</code>になる場合があります。<br>
    これを回避するには <code>SIGPIPE</code>をignoreし、writeやprintした結果を見るようにするプログラムにしてください。

    参考: <a href="https://yukicoder.me/problems/no/3013/code">No.3013 Trigger EPIPE のジャッジコード</a>
</p>
<p>
コンテスタント側が「応答プログラムが終了する条件の場合は、回答プログラムも終了するようにしましょう。」をなるべく行えるようにしましょう。
例えばコンテスタント側が不正な値出力をしたとき、ジャッジプログラムが直ちに終了してしまうとコンテスタント側は返しの入力を待っているかもしれません。
「コンテスタントが何か変なことをしたらジャッジは -1 を出力して終了する」のような仕様にしておくとよい場合があります。
</p>

<h3 class="shadow">コミュニケーション形式の作問時の追加注意点</h3>
<p>
コミュニケーション問題では、同じプログラムが複数プロセスで動作するため、以下の追加点にも注意してください。
</p>
<ul>
<li><b>終了条件の明確化</b>: 全プロセスが正しく終了できるよう、終了条件を明確にする（例: <code>END</code> メッセージの送信）</li>
<li><b>不正出力への対応</b>: 1つのプロセスが不正な出力をした場合、他のプロセスがデッドロックしないよう配慮する</li>
<li><b>時間制限</b>: 複数プロセス分の通信オーバーヘッドを考慮して時間制限を設定する</li>
</ul>