128 bit 解 (11 点)

Alice は 64 回かけて \(A\) を Bob に送信し，Bob は 64 回かけて \(B\) を Alice に送信すれば良いです．

81 bit 解 (66 点)

平方分割をしてみましょう．64 bit 整数を 8 bit のブロック 8 個に分割し，上位 bit のブロックから順に共有することを考えます．

• \(2^{56}\) の位から \(2^{63}\) の位までのブロックを ブロック \(1\)
• \(2^{48}\) の位から \(2^{55}\) の位までのブロックを ブロック \(2\)
• \(\vdots\)
• \(2^0\) の位から \(2^{7}\) の位までのブロックを ブロック \(8\)

と呼ぶことにします．

あるブロックの情報を Alice から Bob に送信したとき，その値が \(A\) と \(B\) で異なるならば，\(A\) と \(B\) のどちらが小さいかが確定します．そこで，Bob は Alice に「値が異なる」ことを送り，値の小さい方から大きい方に残りのデータを送信すれば，answer() までを効率的に行うことができます．
ブロックの値が \(A\) と \(B\) で同じである場合は，Bob は Alice に「値が同じ」ことを送れば，ブロックごとに 1 bit の追加で値を共有することができます．

send() の回数は，

• 各 bit の共有に \(64\) 回
• 値が異なるかどうかの返答に \(8\) 回
• 値が異なる場合，どちらが小さいかの共有に \(1\) 回
• 値が異なる場合，そのブロックを再度送信するのに \(8\) 回

で合計 \(81\) 回となります．

80 bit 解 (70 点)

\(A < B\) のとき，「値が異なる」ことを送った後でも情報の送信方向が変化しないことに無駄があります．

Bob は「値が異なる」かどうかではなく，「ここまでで \(A ≤ B\) なのでそのまま継続する」か「ここまでで \(A > B\) なので，残りを Bob から送って終了する」の \(1\) bit を返すことにします．最後まで \(A ≤ B\) だったときに Alice は \(B\) が分かりませんが，出力すべきなのは \(A\) なので問題ありません．途中で \(A > B\) となった場合は，それより前のブロックまでは \(A = B\) であったということなので，Alice は \(B\) の値を特定することができます．

send() の回数は，

• 各 bit の共有に \(64\) 回
• \(A > B\) かどうかの返答に \(8\) 回
• \(A > B\) である場合，そのブロックを Bob が送信するのに \(8\) 回

で合計 \(80\) 回となります．

76 bit 解 (100 点)

平均的な send() の回数は何回でしょうか？

• \(A > B\) かどうかの返答に \(8\) 回

とありますが，途中のブロックで \(A > B\) であると判明した場合はこの返答がなくなり，多くのケースでは \(80\) 回よりも早く終わってしまうことに無駄があります．

send() の回数を詳しく見ると，

• 各 bit の共有に \(64\) 回
• \(A > B\) かどうかの返答に (ここまでのブロックの個数) 回
• \(A > B\) である場合，そのブロックを再度送信するのに (このブロックの大きさ) 回

であることが分かります．
したがって，send() の回数を均すためには，後に送るブロックほど長さを短くすべき なのです！

• \(2^{53}\) の位から \(2^{63}\) の位までの \(11\) bit のブロックを ブロック \(1\)
• \(2^{43}\) の位から \(2^{52}\) の位までの \(10\) bit のブロックを ブロック \(2\)
• \(2^{34}\) の位から \(2^{42}\) の位までの \(9\) bit のブロックを ブロック \(3\)
• \(\vdots\)
• \(2^1\) の位から \(2^3\) の位までの \(3\) bit のブロックを ブロック \(9\)
• \(2^0\) の位を ブロック \(10\)

のようにすると，(ここまでのブロックの個数) \(+\) (このブロックの大きさ)\({}≤12\) であるので，send() の回数は合計 \(76\) 回となります．

実装例 (Python)