対話protocolを守って情報を取得する

概要

対話protocolとquery設計

対話問題では、まだ届いていない入力が、自分の出力を待っている。何を質問するかに加え、いつ送信し、どの返答を読んでから次へ進むかを設計する。この送受信の約束を対話protocolと呼ぶ。

judge(ジャッジプログラム)から情報を得る質問応答型、質問集合を先にすべて送る型、相手と交互に手を指す型では、入力と出力の順序が違う。まず問題文の対話形式から、最初に読む情報・次に出す行・終了する条件を確認する。

考え方

一問ずつ返答を受けて候補を絞る

ABC269 E「Last Rook」では、縦横 NN マスの盤面に、行も列も重ならない N−1N-1 個のルークがある。空いている行と列を一つずつ見つければ、その交点に最後のルークを置ける。

行を調べるときは、質問する長方形の列範囲を全列にする。調べた行数と同じ個数が返れば、その中に空行はない。一つ少なければ、その中に空行がある。この違いで候補区間の半分を残せる。

空行がある候補区間を [L,R][L,R] とし、最初は [1,N][1,N] とする。L<RL<R の間、M=⌊(L+R)/2⌋M=\lfloor(L+R)/2\rfloor として ? L M 1 N の形で左半分を質問する。返答が M−LM-L なら R=MR=M、M−L+1M-L+1 なら L=M+1L=M+1 に更新する。どちらでも空行を含む側だけが残り、候補は必ず減る。L=RL=R になったら行が確定する。列も同様に、全行を覆う ? 1 N L M で求める。

次は N=4N=4、ルークが (1,2),(2,4),(4,1)(1,2),(2,4),(4,1) にある場合の、合法な対話の一例である。配置は説明用で、自分のプログラムには見えない。以下は非実行の会話例で、judge: は自分が読む行、自分: はjudgeへ出す行を表す。ラベルと括弧内の説明は送信しない。自分の各出力には改行を付け、その直後に必ずflushする。

judge: 4
自分: ? 1 2 1 4  (flush)
judge: 2
自分: ? 3 3 1 4  (flush)
judge: 0
自分: ? 1 4 1 2  (flush)
judge: 2
自分: ? 1 4 3 3  (flush)
judge: 0
自分: ! 3 3      (flushして終了)

最初の質問への返答は2で、1〜2行目はどちらも埋まっている。行候補を [3,4][3,4] に更新して3行目を質問すると0が返り、空行は3行目と確定する。続いて列候補を [1,4][1,4] から始め、1〜2列目への返答2で [3,4][3,4] へ更新する。3列目への返答0で空列も確定し、! 3 3 を出す。

ここで守る不変条件は「空行・空列が、それぞれ現在の候補区間に残っている」である。送信した質問と、それに対して読んだ返答を一組として扱い、その返答で候補を更新してから次の質問を作る。候補が一つになった座標は再質問しない。両方の座標が確定したら、質問ではなく最終回答を出す。

flushと受信待ちを区別する

標準出力へ書いた文字は、プログラム内のバッファに留まることがある。flushは、そのバッファの内容を送信する操作である。改行しただけで必ずflushされるとは限らない。質問が届く前に返答を読もうとすると、judgeも質問を待っているため、互いに待ったまま進まなくなる。

一方、flushは返答を受け取る操作ではない。ABC269 Eなら「質問を出す→改行・flush→整数を一つ読む→異常応答か確認→候補を更新」が一段になる。未読の返答を飛ばして次の質問を出すと、その返答を次の質問の答えと取り違えたり、古い候補から質問を作ったりする。入力全体を最初に読むことも、judgeが今は送らない入力を待つ原因になる。

質問集合を先に送り、結果を一括して読む

ABC337 E「Bad Juice」では、ジュースの本数を読んだ後、友人の人数と、各友人に飲ませる集合をすべて出力する。それから初めて、全員分の結果を一つの文字列として読む。各集合の直後に返答を読む手順では進まない。

4本に対して、友人1には2・4番、友人2には3・4番を飲ませるとする。次も非実行の会話例で、括弧内は説明である。自分の各出力には改行を付けてflushする。

judge: 4
自分: 2      (友人の人数。flush)
自分: 2 2 4  (友人1の集合。flush)
自分: 2 3 4  (友人2の集合。flush)
judge: 01    (ここで結果を一括受信)
自分: 3      (最終回答。flushして終了)

結果 01 は、友人1は無事で、友人2だけがお腹を壊したことを表す。友人1の集合に含まれず友人2の集合に含まれるのは3番だけなので、答えは3となる。この問題の最終回答には ! を付けない。集合をどう作れば最小人数で識別できるか、その下界と符号の構成は情報量下界・query符号設計で扱う。ここでは、結果を見てから次の集合を変更することはできない、という通信の段階を押さえる。

先後を宣言してから交互に手を指す

ABC398 E「Tree Game」では、最初に木を読み、First または Second を出して改行・flushする。これは先後の宣言であり、辺を追加する一手には数えない。その直後の処理は、選んだ側で異なる。

  • First の直後は自分の手番なので、合法な頂点対を出力して改行・flushする。その後に相手の手を読む。
  • Second の直後は相手の手番なので、まず頂点対を読む。終了信号でなければ相手の辺を追加し、次に自分の手を出す。

例えば4頂点の道では、次の非実行の会話ができる。自分の各出力には改行を付ける。

judge: 4
judge: 1 2
judge: 2 3
judge: 3 4
自分: First  (宣言をflush)
自分: 1 4    (自分の一手をflush)
judge: -1 -1 (勝利。何も出力せず終了)

辺 (1,4)(1,4) の追加でできる閉路は長さ4で、奇閉路ではない。追加後は合法手がなく、相手の手番で勝利の信号が来る。境界例として2頂点の木なら、最初から追加できる辺がないため Second を選び、直後に -1 -1 を読んで終了する。終了信号を受け取った後に、自分の手を出してはいけない。

通常の頂点対を受信したら、その辺を自分が持つ局面にも反映してから次の手を選ぶ。例えば頂点を1→2→3→4→5の順に結んだ道では、追加できる辺は (1,4),(2,5)(1,4),(2,5) の二つである。Second を宣言して相手の 1 4 を読んだら、その辺を候補から消して 2 5 を出し、改行・flushする。続く受信で -1 -1 を読んだら終了する。

自分の出した辺も反映し、「保存した局面が、双方の実際の手をすべて含む」を保つ。勝敗や先後の選び方は偶奇不変量からゲームの勝敗を決めるへ進む。

成立条件と計算量

終了を通常の返答より先に判定する

対話の記号と終了条件は問題ごとに確認する。上の3問でも意味が違う。

  • ABC269 E: 質問への返答 -1 は、不正な質問や20回超過を表す。候補更新に使わず、何も追加出力せず終了する。正常に答えが求まったら ! X Y を出して改行・flushし、正誤の返答を待たずに終了する。
  • ABC337 E: 最終回答はジュース番号だけを出して改行・flushし、終了する。公式仕様には -1 の返答は定義されていない。
  • ABC398 E: 相手からの -1 -1 は自分の勝利を表す。頂点番号として使わず、何も追加出力せず終了する。

異常応答・終了信号を候補数や配列の添字として処理しないために、受信した直後に終了条件を判定する。必要な入力を読み取れなかった場合も、値を推測して処理を続けず終了する。デバッグ用の文字を標準出力へ混ぜると通信形式が壊れるので、診断は標準エラー出力へ分ける。

質問回数と手元の計算量を別々に数える

ABC269 Eでは、行と列でそれぞれ候補区間を半減する。質問回数は合計で高々 2⌈log⁡2N⌉2\lceil\log_2 N\rceil 回となり、制約 2≤N≤10002\leq N\leq 1000 では20回以内に収まる。上の N=4N=4 の会話は4回であり、最初のサイズ入力と最後の ! 3 3 は質問に含めない。

この手順では盤面を保存・走査する必要がなく、各返答からの区間更新は定数時間である。整数の入出力を定数時間と数えると、初期化から最終回答までの手元の計算時間は O(log⁡N)O(\log N)、保持する候補区間などの空間は O(1)O(1) になる。judgeからの返答を待つ時間とは区別した評価である。

一般には、質問が少なくても、その準備で全候補を列挙すれば時間がかかる。例えばABC337 Eでは、返答の受信は一度でも、友人ごとの集合を作って出力する処理が必要になる。質問数・送受信するデータ量・前処理を含む手元の時間と空間をそれぞれ確認する。未知問では「今はどちらが何を待っているか」と「次の一手で候補や局面がどう変わるか」を一緒に追うと、通信手順とアルゴリズムを接続できる。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。入出力手順・flush・問い合わせ上限を守り、単純な識別手順を実装する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-interactive-protocol

習得する技能

  • judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

問い合わせ形式・回数上限・応答依存性・交互手番・合法な応答・flushを明示し、アルゴリズムをjudgeとの対話列として安全に実行する。

このUnitでは扱わないもの

  • 入力を最初からすべて読める通常問題、および問い合わせ上限やflushを持たない模擬入出力。

根拠