対話protocolを守って情報を取得する
概要
対話protocolとquery設計
対話問題では、まだ届いていない入力が、自分の出力を待っている。何を質問するかに加え、いつ送信し、どの返答を読んでから次へ進むかを設計する。この送受信の約束を対話protocolと呼ぶ。
judge(ジャッジプログラム)から情報を得る質問応答型、質問集合を先にすべて送る型、相手と交互に手を指す型では、入力と出力の順序が違う。まず問題文の対話形式から、最初に読む情報・次に出す行・終了する条件を確認する。
考え方
一問ずつ返答を受けて候補を絞る
ABC269 E「Last Rook」では、縦横 マスの盤面に、行も列も重ならない 個のルークがある。空いている行と列を一つずつ見つければ、その交点に最後のルークを置ける。
行を調べるときは、質問する長方形の列範囲を全列にする。調べた行数と同じ個数が返れば、その中に空行はない。一つ少なければ、その中に空行がある。この違いで候補区間の半分を残せる。
空行がある候補区間を とし、最初は とする。 の間、 として ? L M 1 N の形で左半分を質問する。返答が なら 、 なら に更新する。どちらでも空行を含む側だけが残り、候補は必ず減る。 になったら行が確定する。列も同様に、全行を覆う ? 1 N L M で求める。
次は 、ルークが にある場合の、合法な対話の一例である。配置は説明用で、自分のプログラムには見えない。以下は非実行の会話例で、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行目を質問すると0が返り、空行は3行目と確定する。続いて列候補を から始め、1〜2列目への返答2で へ更新する。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 (勝利。何も出力せず終了)
辺 の追加でできる閉路は長さ4で、奇閉路ではない。追加後は合法手がなく、相手の手番で勝利の信号が来る。境界例として2頂点の木なら、最初から追加できる辺がないため Second を選び、直後に -1 -1 を読んで終了する。終了信号を受け取った後に、自分の手を出してはいけない。
通常の頂点対を受信したら、その辺を自分が持つ局面にも反映してから次の手を選ぶ。例えば頂点を1→2→3→4→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では、行と列でそれぞれ候補区間を半減する。質問回数は合計で高々 回となり、制約 では20回以内に収まる。上の の会話は4回であり、最初のサイズ入力と最後の ! 3 3 は質問に含めない。
この手順では盤面を保存・走査する必要がなく、各返答からの区間更新は定数時間である。整数の入出力を定数時間と数えると、初期化から最終回答までの手元の計算時間は 、保持する候補区間などの空間は になる。judgeからの返答を待つ時間とは区別した評価である。
一般には、質問が少なくても、その準備で全候補を列挙すれば時間がかかる。例えばABC337 Eでは、返答の受信は一度でも、友人ごとの集合を作って出力する処理が必要になる。質問数・送受信するデータ量・前処理を含む手元の時間と空間をそれぞれ確認する。未知問では「今はどちらが何を待っているか」と「次の一手で候補や局面がどう変わるか」を一緒に追うと、通信手順とアルゴリズムを接続できる。
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC269 E「Last Rook」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 単調境界探索 / 補助タグ: 対話protocolとquery設計
- ABC278 G「Generalized Subtraction Game」 公式問題主題: ゲーム状態の勝敗とGrundy数
技能・出典
主題: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: game状態・Grundy DP / 補助タグ: 対話protocolとquery設計、状態・配置の正規化
- ABC282 F「Union of Two Sets」 公式問題
技能・出典
主題: 冪等演算のoverlap range query・Sparse Table(冪等な演算なら重なりを許す二つの2冪区間で任意rangeを覆えることを使い、静的queryをO(1)で答える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 冪等演算のoverlap range query・Sparse Table / 補助タグ: 対話protocolとquery設計
- ABC286 F「Guess The Number 2」 公式問題
技能・出典
主題: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。追加で学ぶ技能: 剰余周期と指数法則を利用する(剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 一次合同・CRT、剰余周期・指数法則 / 補助タグ: 対話protocolとquery設計
- ABC305 F「Dungeon Explore」 公式問題主題: 状態グラフのモデリングと探索
技能・出典
主題: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。追加で学ぶ技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。主タグ: 対話protocolとquery設計、状態グラフのモデリングと探索 / 補助タグ: 単調進行による償却解析
- ABC337 E「Bad Juice」 公式問題主題: 情報量下界・query符号設計
技能・出典
主題: 情報量下界・query符号設計(応答列の総数からquery数の下界を証明し、それに一致するcodeword割当と復号を構成できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 情報量下界・query符号設計 / 補助タグ: 対話protocolとquery設計
- ABC355 E「Guess the Sum」 公式問題主題: 状態グラフのモデリングと探索
技能・出典
主題: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。追加で学ぶ技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。既習技能: 最短路を証明する木・経路の復元(距離等式を満たす親辺を選び、最短路の木または経路を復元できる。)。主タグ: 対話protocolとquery設計、状態グラフのモデリングと探索 / 補助タグ: 最短路を証明する木・経路の復元
- ABC398 E「Tree Game」 公式問題
技能・出典
主題: 偶奇不変量からゲームの勝敗を決める(合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。)。追加で学ぶ技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 二部グラフの彩色と成分構造、偶奇不変量によるゲーム戦略 / 補助タグ: 対話protocolとquery設計
前提・学習成果・出典
習得対象の目安: 緑色(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を持たない模擬入出力。