ジャッジでは、下記の10通りの固定入力だけが使用されます。プログラムは各入力に対して個別に実行されます。
作成したプロトコルの正しさ、プライバシー、得点は、出力チェッカーで確認できます。
各固定入力には盤面が1個含まれます。盤面は # と . からなる正方形のマス目であり、# は花火筒があるマス、. は何もないマスを表します。それぞれの盤面について、以下の条件を満たすプロトコルを構成してください。
各ケースの盤面の大きさを \(N\times N\) とします。行と列には \(0,1,\ldots,N-1\) の番号が付いています。
Alice は整数 \(x\ (0\le x<2^N)\) を秘密に持ちます。\(x\) の下位から \(i\) 番目のビットを \(x_i\) とし、\(x_i=1\) のとき、Alice は行 \(i\) の横導火線を選んでいるものとします。
同様に、Bob は整数 \(y\ (0\le y<2^N)\) を秘密に持ちます。\(y\) の下位から \(j\) 番目のビットを \(y_j\) とし、\(y_j=1\) のとき、Bob は列 \(j\) の縦導火線を選んでいるものとします。
# のマス \((i,j)\) にある花火筒は、Alice が行 \(i\) を選び、かつ Bob が列 \(j\) を選んだ場合に発火します。Carol が求める値は、発火した花火筒の個数の偶奇です。個数が偶数なら0、奇数なら1です。
盤面を0/1行列 \(A\) で表し、# なら \(A_{ij}=1\)、. なら \(A_{ij}=0\) とすると、知らせたい値は
\[f_A(x,y)=\bigoplus_{i=0}^{N-1}\bigoplus_{j=0}^{N-1} A_{ij}x_i y_j\]
です。\(\oplus\) は XOR を表します。
Alice と Bob は、実行前に同じ共有乱数 \(\rho\) を受け取れます。\(\rho\) は \(0,1,\ldots,R-1\) のいずれかであり、各値を同じ確率 \(1/R\) で取ります。
プロトコルの実行中、Alice と Bob は互いに通信できません。それぞれが Carol に整数を1つ送った後、Carol が答えを決定します。
提出するのは、整数 \(P,Q,R\) と、3つの表 \(E_A,E_B,D\) です。
すべての \(x,y\in\{0,1,\ldots,2^N-1\}\) と、すべての \(\rho\in\{0,1,\ldots,R-1\}\) について、
\[D\bigl[E_A[x][\rho]\bigr]\bigl[E_B[y][\rho]\bigr]=f_A(x,y)\]
でなければなりません。共有乱数の大部分で正しいだけでは不十分です。すべての \(\rho\) で正しくなければなりません。
Carol が見る通信記録は、Alice と Bob のメッセージの組
\[\left(E_A[x][\rho],E_B[y][\rho]\right)\]
だけです。この通信記録の確率分布は、答え \(f_A(x,y)\) だけに依存しなければなりません。
厳密には、\(f_A(x,y)=f_A(x',y')\) を満たす任意の2組 \((x,y),(x',y')\) と、任意のメッセージ組 \((p,q)\) について、
\[\#\left\{\rho:\left(E_A[x][\rho],E_B[y][\rho]\right)=(p,q)\right\} =\#\left\{\rho:\left(E_A[x'][\rho],E_B[y'][\rho]\right)=(p,q)\right\}\]
が成立しなければなりません。ここで \(\#\) は、条件を満たす \(\rho\) の個数を表します。近似的に同じ分布ではなく、個数が完全に一致する必要があります。
したがって Carol は、通信記録から答えを必ず復元できますが、同じ答えになる入力同士を区別できません。答えが異なる2組の入力について、通信記録の分布が同じである必要はありません。
入力は以下の形式で標準入力から与えられます。
| \(K\) | |
| \(N\) | |
| \(A_0\) | |
| \(A_1\) | |
| \(\vdots\) | |
| \(A_{N-1}\) |
入力の先頭にはケース番号 \(K\) が与えられます。続いて盤面の大きさ \(N\) と、\(N\) 行の盤面 \(A_0,A_1,\ldots,A_{N-1}\) が与えられます。
ケース1
1 1 #
ケース2
2 4 #### .... .... ....
ケース3
3 4 ##.. ##.. .... ....
ケース4
4 4 #..# .... .... #..#
ケース5
5 4 ###. .#.. .... ....
ケース6
6 4 ##.. .##. .... ....
ケース7
7 4 #... .#.. ##.. ....
ケース8
8 4 ##.. .#.. ..#. ....
ケース9
9 4 #... .#.. ..#. ...#
ケース10
10 4 ..#. #... ...# .#..
与えられた1ケースに対するプロトコルを出力してください。
ケースを解く場合、次の形式で出力してください。
| \(P~Q~R\) | |
| \(E_A[0][0]~E_A[0][1]~\ldots~E_A[0][R-1]\) | |
| \(E_A[1][0]~E_A[1][1]~\ldots~E_A[1][R-1]\) | |
| \(\vdots\) | |
| \(E_A[2^N-1][0]~E_A[2^N-1][1]~\ldots~E_A[2^N-1][R-1]\) | |
| \(E_B[0][0]~E_B[0][1]~\ldots~E_B[0][R-1]\) | |
| \(E_B[1][0]~E_B[1][1]~\ldots~E_B[1][R-1]\) | |
| \(\vdots\) | |
| \(E_B[2^N-1][0]~E_B[2^N-1][1]~\ldots~E_B[2^N-1][R-1]\) | |
| \(D[0][0]~D[0][1]~\ldots~D[0][Q-1]\) | |
| \(D[1][0]~D[1][1]~\ldots~D[1][Q-1]\) | |
| \(\vdots\) | |
| \(D[P-1][0]~D[P-1][1]~\ldots~D[P-1][Q-1]\) |
値は次の範囲でなければなりません。
\[1\le P\le256,\qquad 1\le Q\le256,\qquad 1\le R\le32768\]
続いて、以下の順番で3つの表を出力してください。
\(E_A\) の各要素は \(0\) 以上 \(P-1\) 以下、\(E_B\) の各要素は \(0\) 以上 \(Q-1\) 以下、\(D\) の各要素は0または1でなければなりません。
ケースを解かない場合、そのケースについては次の1行だけを出力してください。そのケースの得点は0点です。
| \(0~0~0\) |
範囲外の \(P,Q,R\)、要素数の不足や過剰、範囲外の表要素など、出力形式に違反した提出は Wrong Answer になります。
ケース \(i\) の盤面にある # の個数を \(m_i\) とします。
ケース \(i\) の先頭行に出力した \(P,Q\) を、それぞれ \(P_i,Q_i\) と書き、
\[B_i=4m_i,\qquad C_i=\log_2 P_i+\log_2 Q_i\]
と定義します。下のヒントのとおりに実装した構成では、\(P_i=Q_i=2^{2m_i}\) となるため、\(C_i=4m_i=B_i\) です。
正しさとプライバシーをともに満たすケースの得点は、
\[S_i=\left\lceil 100\cdot\max\left(0,2-\left(\frac{C_i}{B_i}\right)^3\right)\right\rceil\]
です。ここで \(\lceil\cdot\rceil\) は小数点以下の切り上げを表します。各ケースの得点は最大200点です。
ケースをスキップした場合、そのケースの得点は0点です。プロトコルが正しさまたはプライバシーを満たさない場合は Wrong Answer になります。各固定入力は独立に採点され、総合スコアは10ケースの得点の単純平均です。したがって、すべてのケースで下のヒントのとおりに実装した構成を用いた場合の総合スコアは100点、総合スコアの満点は200点です。
最初に読むヒント：1ビット AND の完成品
ケース1は、花火筒が1個だけです。次のプロトコルをそのまま使えます。以下の計算はすべて0/1に対して行い、\(\oplus\) は XOR、積は AND を表します。
共有乱数 \(r,s,t\in\{0,1\}\) を独立かつ一様に選びます。Alice は
\[p=x\oplus r,\qquad a=xs\oplus t\]
を、Bob は
\[q=y\oplus s,\qquad b=ry\oplus rs\oplus t\]
を計算します。Alice は整数 \(p+2a\) を、Bob は整数 \(q+2b\) を送ります。Carol は
\[pq\oplus a\oplus b\]
を答えます。式を展開すると、\(xy\) 以外の項は2回ずつ現れて消えます。
\(\rho=r+2s+4t\) の順に8通りの共有乱数を並べると、ケース1の完全な出力は次のとおりです。最初の2行が \(E_A\)、次の2行が \(E_B\)、最後の4行が \(D\) です。
4 4 8 0 1 0 1 2 3 2 3 1 0 3 2 3 2 1 0 0 0 1 3 2 2 3 1 1 3 0 0 3 1 2 2 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1
複数の花火筒に関するヒント
花火筒を1個ずつ処理するとき、各花火筒の発火結果をそのまま Carol に見せると、最終的な偶奇以外の情報が漏れてしまいます。
各花火筒の発火結果を \(h_1,h_2,\ldots,h_m\) とします。共有乱数として、次を満たすビット列 \((z_1,z_2,\ldots,z_m)\) を、そのような \(2^{m-1}\) 通りから一様に選ぶことを考えます。
\[z_1\oplus z_2\oplus\cdots\oplus z_m=0\]
Carol に各 \(h_i\oplus z_i\) だけを復元させられれば、それらすべての XOR は求める偶奇と一致します。さらに、マスクされたビット列 \((h_1\oplus z_1,\ldots,h_m\oplus z_m)\) は、その XOR が同じである \(2^{m-1}\) 通りを一様に取ります。したがって、その分布は個々の \(h_i\) ではなく、最終的な偶奇だけに依存します。
1ビット AND のプロトコル中のマスクを調整し、Carol が各 \(h_i\) そのものではなく \(h_i\oplus z_i\) を得るようにできないか考えてみてください。