AtCoder Beginners SelectionにSubmitされていた面白い解法メモ
AtCoder Beginners Selectionでビット演算を使った面白い回答がSubmitされていたのでメモしておきます。 abs.contest.atcoder.jp
問題はABC081B - Shift onlyです。
以下に問題文を引用します。
黒板に N 個の正の整数 A1,…,AN が書かれています． すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます． 黒板に書かれている整数すべてを，2 で割ったものに置き換える． すぬけ君は最大で何回操作を行うことができるかを求めてください． 制約 * 1≤N≤200 * 1≤Ai≤109 入力 入力は以下の形式で標準入力から与えられる。 N A1 A2 ... AN 出力 すぬけ君は最大で何回操作を行うことができるかを出力せよ．
面白かったのは、prd_xxxさんのPython3での回答です。 Python3でACされた中では、この記事を書いている時点でソースコード長最短(66byte)かつ最速(17ms)となっています。
コードがこちらです。
input();N=eval(input().replace(' ','|'));print(len(bin((N&-N)))-3)
ループを回さずワンライナーで処理を完結させています。
この解法は、二進数に関する下記の性質を利用しています。
- 十進数での奇数は、二進数にすると最下位ビットが必ず1になる。
- 二進数において、2で除算することは1ビット右シフトすることと同じ。
- 二進数において、2の補数は1が出てくる最下桁までは元の数と同じビットで、それよりも上の桁はビットが反転する。
上記性質を踏まえてコードを見てみます。 まず、整数の個数Nについては不要なためinput()で捨てます。 次に、入力A1...ANについて空白を'|'(OR)に置き換え、式としてeval()で論理演算します。 入力例1で上記処理を実行すると、下記のようになります。
>>> eval('8 12 40'.replace(' ', '|'))
44
>>> bin(44)
'0b101100'
ここで、論理和について1が出てくる最下桁は3です。二進数の性質1, 2から、「2回のビットシフト=2回2で割る」が最大回数であることがわかります。 次に、性質3を使って2の補数と論理積を取り、1が出てくる最下桁から下位のビット列を取り出します。後はbin()で二進数表記の文字列に変換後、文字列長から先頭の'0b1'分の3を引くことで解が得られます。
>>> bin(44)
'0b101100'
>>> bin(44&-44)
'0b100'
>>> len('0b100')-3
2
コードを見た瞬間はなんだコレと思ったのですが、よく考えると二進数の性質を上手く利用したエレガントな解法であることがわかりました。
