コミュニケーションの問題（COCI 2022 COI Mensza）

出典

COCI 2022 COI 問2 Mensza
https://codeforces.com/blog/entry/103280
IOI系 ではコミュニケーションと呼ばれる独特な形式の問題が出題されることがある。

問題

4人の人物がいる

  • Mr. Malnar マルナー先生
  • Alojzije アロイジエ
  • Benjamin ベンジャミン
  • Cecilija セシリア

次の試験を行う。

  1. マルナー先生が異なる正整数 A, B を決める（1 ≦ A, B ≦ 500000）
  2. マルナー先生は A をアロイジエに伝える。A を見たアロイジエは長さ 20 以下の数列 X を作ってマルナー先生に渡す
  3. マルナー先生は B をベンジャミンに伝える。B を見たベンジャミンは長さ 20 以下の数列 Y を作ってマルナー先生に渡す
  4. マルナー先生は数列 X, Y を連結して数の出現回数を数える。出現回数の列を昇順に並べた数列 Z を作る
  5. マルナー先生はセシリアに Z を渡す。Z を見たセシリアは A, B のどちらが大きいと思うか宣言する。正しい宣言をすれば試験は成功である

例えば X = [10, 30, 50], Y = [25, 30, 30, 46, 50] の場合、出現回数は { 10 → 1, 25 → 1, 30 → 3, 46 → 1, 50 → 2}、よって Z = [1, 1, 1, 2, 3] がセシリアに渡される。
アロイジエ、ベンジャミン、セシリアの3人は協力してこの試験に成功したい。あなたは試験が確実に成功するような3人分のプログラムを作りなさい。

補足

数列は長さと順番に並んだ要素で構成され、文字列にして送信される。例えば数列 [10, 30, 50] はスペース区切りの1行の文字列 "3 10 30 50" としてやり取りされる。
数列の要素は 1 以上 10^9 以下でなければならない。
アロイジエ、ベンジャミン、セシリア、は上記の方法以外で情報をやり取りできない。
実際はマルナー先生がどんな順番でアロイジエ、ベンジャミン、セシリアと会話するかわからない。アロイジエ、ベンジャミンにいろいろな数を聞いた後でセシリアに聞いて試験するかもしれない。
問題の制約は満点の場合を基準にしている。

解答

アロイジエは A だけを知っている。ベンジャミンは B だけを知っている。セシリアは A も B も知らない、復元もできないがどちらが大きいかだけは知っている。という数学パズル。
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

考察1

まず、XとYを連結した数列の長さは40以下であるのでセシリアの受け取る数列は 40 以下の分割数のパターンしかない。これは A と B の組み合わせのパターンより少ないのでセシリアは A, B を同時に復元することはできない。
アロイジエとベンジャミンは A,B の一方の値しか知らないのでどちらの値が大きいかを数列 X, Y に書き込むことはできない。
アロイジエとベンジャミンが完全に同じアルゴリズムであると、A と B が入れ替わった時に Z が全く同じ数列になり、セシリアは区別できない。そのためアロイジエとベンジャミンは異なるアルゴリズムのはずである。

考察2

0 ≦ A, B ≦ 1 の場合を考える。

  • アロイジエ：A=0ならば空列、1ならば [1] を作る
  • ベンジャミン：B=0ならば [1]、1ならば空列を作る

すると (A, B) 4通りについて、

  • (0, 0) : Z = [1]
  • (1, 0) : Z = [2]
  • (0, 1) : Z = 空列
  • (1, 1) : Z = [1]

となり、(1, 0) と (0, 1) は区別することができ、必要のない (0, 0) と (1, 1) が同じ数列になって効率よくまとめられている。

解答

A, B を2進数で表記したときに初めて異なる上位ビットを見つけることができればそれが大小関係になる

A = 0b00101011
B = 0b00100110
          ^

このビットより下位ビットは 0 に上書きし、B の 0 を 1 にフリップすれば A と B が一致する。

A → 0b00101000
B → 0b00101000
          ^

この方法で「上位ビットから見て初めて異なるビットが A は 1、B は 0」 の場合のみ値が等しくなる、つまり、Z に 2 が含まれる。A, B は20ビットで表現できるため、数列の長さも 20 以下で条件を満たす。

よって、

  1. アロイジエ：A を2進数で表して、あるビットが 1 ならばそれより下位のビットを0にしてXにpush
  2. ベンジャミン：B を2進数で表して、あるビットが 0 ならばそのビットを1にして、それより下位のビットを0にしてYにpush
  3. セシリア：数列Zに 2 が含まれていれば A>B、そうでなければ A < B

IOI ではこの3つのプログラムを別のファイルに書いて提出するはずだが、COI では一つのファイルに書くことになっていた。