これはインタラクティブな問題です。
怠け者の Sam と勤勉な Sarah は、アルファベット $\{H, T\}$ 上の長さ $n$ の文字列全体の集合上の興味深い確率分布を2つ考案するという課題を与えられました。怠け者の Sam は単にコインを $n$ 回投げ(各面が出る確率は $\frac{1}{2}$ であり、すべてのコイン投げは独立です)、表が出たら "H"、裏が出たら "T" と書き留めます。あなたは勤勉な Sarah を手伝って、怠け者の Sam に一泡吹かせたいと思っています。整数 $t$ が与えられます。一様分布に $t$-近い分布を Sarah が考案するのを手伝い、同時に長さ $t$ のオラクルアクセスを用いて怠け者の Sam の分布と勤勉な Sarah の分布を識別できることをインタラクティブに証明してください。
形式的には、ある整数 $n$ に対して、2つの文字 "H" と "T" からなるアルファベット上の長さ $n$ のすべての可能な文字列からなるサイズ $2^n$ の集合 $S = \{H, T\}^n$ を考えます。集合 $S$ 上の分布とは、$S$ の要素で添字付けられた長さ $2^n$ の非負実数の配列 $\{a_s\}_{s \in S}$ であって、その総和が $1$ に等しいものとして定義されます。最も単純な分布の1つは一様分布であり、すべての $a_s$ が $2^{-n}$ に等しくなります。
2つの数 $\varepsilon \in [0; +\infty)$ と $k \in \{0, 1, \dots, n\}$ の組に対して、任意の $k$ 個のインデックスの選択 $1 \le i_1 < i_2 < \dots < i_k \le n$ およびアルファベット $\{H, T\}$ 上の長さ $k$ の文字列の任意の部分集合 $T \subseteq \{H, T\}^k$ について次が成り立つとき、$\{a_s\}_{s \in S}$ は $(\varepsilon, k)$-独立な分布であると言います:部分列 $s[i_1]s[i_2]\dots s[i_k]$ が $T$ に属するような $2^{n-k}|T|$ 個の文字列 $s$ にわたる $a_s$ の和と $\frac{|T|}{2^k}$ との差が高々 $\varepsilon$ である。確率論の言葉では、これは次のように表せます:
$$\forall 1 \le i_1 < i_2 < \dots < i_k \le n \quad \forall T \subseteq \{H, T\}^k \quad \frac{|T|}{2^k} - \varepsilon \le \mathbb{P}_{s \leftarrow \{a_s\}_{s \in S}} \{s[i_1]s[i_2]\dots s[i_k] \in T\} \le \frac{|T|}{2^k} + \varepsilon.$$
直感的には、これはこの分布を一様分布と区別するには、差が $\varepsilon$ を超えない確率を区別するか、分布によって生成された文字列の $k$ ビットより多くを見る必要があることを意味します。
分布 $\{a_s\}_{s \in S}$ が $(2^{-t}t, t)$-独立であるとき、一様分布に $t$-近いと呼ばれます。
$(\varepsilon, k)$-独立性の定義では、最初に $k$ 個のインデックスを選び、その後で初めてその $k$ 個のインデックス上の確率分布を調べることが暗に仮定されていました。長さ $k$ のオラクルアクセスモデルでは、すべてが異なります。長さ $n$ のランダムな文字列が生成され、その後、次の形式のラウンドが $k$ 回行われます:あなたが整数 $i \in \{1, 2, \dots, n\}$ を指定すると、その応答として $s[i]$ が教えられます。あなたはそれまでに行ったすべての質問とその回答を考慮して、次にどのインデックスを指定するかを決定できます。
怠け者の Sam と勤勉な Sarah の分布を識別できることを証明するために、彼らの分布からサンプリングされた長さ $n$ の $m$ 個の文字列(それぞれ独立かつ一様に、怠け者の Sam の分布または勤勉な Sarah の分布のいずれかから生成される)に対して長さ $t$ のオラクルアクセスを行い、それぞれについてどちらの分布から得られたものかを結論付け、少なくとも $0.75m - 2\sqrt{m}$ 回正しく当てる必要があります。
入出力の方法
最初の行には、一様分布への要求される近さおよびオラクルアクセスの長さを表す整数 $t$($1 \le t \le 5$)が含まれます。
これに応答して、分布と識別可能性のインタラクティブな証明を提供する文字列の長さを表す単一の整数 $n$($t \le n \le 20$)を1行に出力してください。
次の行に、あなたの分布を定義する $2^n$ 個の整数 $b_s$ を1行に出力してください($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$)。このデータに基づき、ジャッジは規則 $a_s = b_s / \sum_{s \in S} b_s$ に従って分布 $\{a_s\}_{s \in S}$ を決定します。$b_s$ の値は文字列 $s$ の辞書順に並べなければなりません。例えば $n = 3$ の場合、数値は次の順序で出力する必要があります:$b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$。
次に、インタラクティブな検査の回数を表す整数 $m$($1 \le m \le 10^4$)を読み込んでください。これに続いて $m$ 回の検査が提示されるので、1つずつ順番に完了させる必要があります。
各検査の開始時に、ジャッジはまず確率 $\frac{1}{2}$ で怠け者の Sam または勤勉な Sarah のいずれかの分布 $\{a_s\}_{s \in S}$ を選びます。その後、ジャッジはランダムな文字列 $s \sim \{a_s\}_{s \in S}$ をサンプリングします。どの文字列 $s$ も確率 $a_s$ で得られます。次にジャッジは、文字列 $s$ の文字について高々 $t$ 回の質問をする機会をあなたに与えます。質問をするには、調べたい文字のインデックスを表す整数 $q \in \{1, 2, \dots, n\}$ を1行に出力してください。その後、クエリに対する回答である文字 "H" または "T" を読み込んでください。$0$ 回から $t$ 回の質問を行った後、$s$ が怠け者の Sam の分布から得られたと考える場合は "Sam"、$s$ が勤勉な Sarah の分布から得られたと考える場合は "Sarah" という名前を1行に出力してください。その後、ただちに次の検査に進み、全 $m$ 回の検査が完了するまで繰り返してください。
文字列は大文字・小文字を問わず出力できます。
各行を出力した後は、出力バッファをフラッシュすることを忘れないでください。
入出力例
入力例 1
2 3 T T T T T
出力例 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH