別解です。公式解説の 85 点の解法を発展させます。

計 \(75\) 組のうち、両方の桁が生きているものの個数を \(T\) とします。Anna は \(T\) の値によって二つの戦略を使い分けます。

\(T \geq 38\) の場合

公式解説のように、両方の桁が生きている組に対し、\(\mathtt{01},\mathtt{10},\mathtt{11}\) の 3 種類を割り当てます。ただし、復号の都合上必ず \(\mathtt{11}\) が 1 つは含まれるようにします。\(10^{18} < 3^{38}-2^{38}\) より、このような制約を追加して困ることはありません。

\(T \leq 37\) の場合

両方の桁が死んでいる組が高々 \(2\) つしかないことに注目します。\(\mathtt{00}\) を 0 に、\(\mathtt{01}\) と \(\mathtt{10}\) を 1 に割り当てることにすると、結局次の問題に対処できれば良いことになります。

Anna は Bruno に \(X\) の値を伝えるため、長さ \(75\) の 01 列を送る。ただし、列のうち指定された \(2\) 箇所は必ず 0 にしなければならない。この \(2\) 箇所は Anna にのみ知らされる。

列を左から長さ \(7,7,61\) になるように分割します。長さ \(61\) の部分に \(X\) の二進法表現を埋め込みます。\(10^{18}<2^{61}\) より長さが足りなくなることはありません。このままだと 1 を書き込みたい箇所と指定された箇所が被ってしまうことがありますが、そのような場合は、どの桁も死んでいない長さ \(7\) の部分にそのインデックスの二進法表現を埋め込んでおけば良いです。

復号

送られてきた列に \(\mathtt{11}\) が存在すれば \(T \geq 38\) の方法で埋め込んだと、存在しなければ \(T \leq 37\) の方法で埋め込んだとわかるので、問題なく復号が行えます。