筋トレ3日目: SRM569 Div1Easy "The Device"

■時間
18:45〜19:00
（昨日は早く出社しないといけなかったので出来なかった）

■問題 SRM569 Div1 Easy "The Device"

２つの固定長のビット列を入力に、同じ長さのビット列を一つ返す機械を持っている。

各ビットは入力ビットのAND, OR, XORのどれか。

（例えば３ビットの入力を受け付ける機械で、[XOR,OR,OR]という仕様ならば、入力ビット列110,010に対して110を返す）

何個かのビット列を持っており、それらの全組み合わせを入力させることで、機械の仕様を調べたい。

既にN個のビット列が与えられている時、あと何個あればどんな機械に対しても仕様を必ず確定できるか？

■試した解き方
あるビット位置のオペレーションを認識するために必要なビットの組み合わせを考える。
地道に、XORとANDを分けるために必要なビットの組み合わせ、XORとOR、ORとAND、のテーブルを作ると：
ANDとOR

　→(0,1)か(1,0)

ANDとXOR

　→(0,1)か(1,0)か(1,1)

ORとXOR

　→(1,1)

つまり、(0,1)か(1,0)と、(1,0)の組み合わせが作れれば、どの３種のオペレーションを分けられる。

これは、各ビット位置には0が1個以上、1が2個以上存在することが必要十分条件。

なので入力されたビット列から、このビット位置で既に存在する0と1の数を数え、足りてない数だけ余計にビット列が必要になることになる。

各ビット位置でこれを計算した最大値を計算すればいい。

■Editorial
同じ解き方。

■反省

一瞬問題を誤読（オペレーションがbit-wiseではなくビット列全てに適用されると誤解）していたため戸惑った。

また慎重になりすぎて時間食った。

これテーブル書かずに解くにはどうすればいいんだろう？

■筋トレ記録
勝率66% (2/3)