Python 3.10 が登場しましたね。パターンマッチの追加などより大きく便利な変更も多くありますが、地味な更新点として、int#bit_countメソッドが追加されました。
これは POPCNT などとも呼ばれ、二進数表記した際の 1 の数を返すような関数です。たとえば、十進数の 5 は二進数では 101 となりますので、
assert (5).bit_count() == 2
となります。
これまでもn.bit_count()の代わりにbin(n).count("1")とすることで同様の値を取ることができましたが、おそらく専用のメソッドを用意することで速度の改善が見込めると思われます。実際最近の CPU では POPCNT の専用命令を用意されていたりもするので、おそらくそちらを利用するものと思われます。専用命令がなかった場合でもより高速に求めるアルゴリズムが知られているので、高速化できるでしょう。
ちなみに Python のint型は多倍長整数を使っているため、負の整数に対してint#bit_countを使用するとどうなるか気になるところですが、これは
assert n.bit_count() == abs(n).bit_count()
となるようです。おそらくbin(n).count("1")の結果に合わせるようにしているのだと思われます。bin(-5) == "-0b101"のように表示されるので。
今回はint#bit_countの追加を記念(?)して AtCoder の過去問精選 10 問より POPCNT を使用することでスマートに解ける Shift Only を解いてみようと思います。ただし AtCoder で利用できるのは Python3.8 と PyPy7.3 (Python3.6 相当) なので実際に使用するのはbin(n).count("1")の方です。
記述は競プロで初めて Python 触ったくらいの Python 初学者向けになっており、普段から Python を触っている人にはややくどい説明になっていると思いますがご了承ください。
\def\bin#1{{#1}_2}
問題概要
まずは問題を見てみましょう。
問題文
黒板に $N$ 個の正の整数 $A_1, \ldots, A_N$ が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
- 黒板に書かれている整数すべてを，$2$ で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．
制約
- $1 \le N \le 200$
- $1 \le A_i \le 10^9$
入力
入力は以下の形式で標準入力から与えられる。
N A1 A2 ... AN
出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ．
シミュレーション
やるべきことは明確ですし、計算量も大したことはないので、これをそのままコードに落とし込むことで解くことができそうです。これをシミュレーションと言います。
まずは入力を受け取ります。
_ = input()
a = [int(n) for n in input().split()]
input関数は入力を 1 行分文字列str型で得ます。1 行目は要素数 $N$ を受け取っていますが、Python で解く場合この値は不要なので明示的に_に代入することで、これをそれ以降使用しないことを示します。
2 行目は少々ややこしいことをしています。これは「内包表記」です。
[A for B in C]
という内包表記は、
- C のそれぞれの要素を
- B という名前で受け取り
- A の式で評価したものを集めたリスト
を作ります。
input().split()は、入力された文字列をスペースで分けた文字列のリストlist[str]を得ます。たとえば8 12 40と入力されたとき、input()は"8 12 40"という文字列を返します。これをstr#split()メソッドが["8", "12", "40"]という文字列のリストに変換します。
このそれぞれの要素をnという名前で受け取り、int(n)という式によって評価します。つまり、各要素が整数int型に変換していますので、最終的にaには[8, 12, 40]という整数のリストlist[int]が代入されることになります。
入力が済んだのでシミュレーションをしていきます。まず、「すべて偶数であるとき」を調べるための関数を定義しておきましょう。
def is_all_even(l):
for e in l:
if e % 2 == 1:
return False
return True
これは「引数lの要素eを順に取り出し、eが奇数(2で割ったあまりが1)だったら中断してFalseを返す、最後まで行った(全部偶数だった)らTrueを返す」という動作をそのまま書き下しています。
そして「全部偶数だったら」動作を続けられるので、これは while 文を使って次のように書けるでしょう。
count = 0
while is_all_even(a):
a = [ai // 2 for ai in a]
count += 1
再び内包表記が出てきました。やっていることは「aの要素すべてを2で割ってaを置き換える」だけです。なお、割り算の演算子として/ではなく//を使用していますが、これは解がint型になるよう、切り捨てを行う除算の演算子です。
そして、繰り返しの前にcount変数を0で初期化し、繰り返しのたびに1増やしています。こうすることで何回 $2$ で割ったかを記録します。
最後にcount変数を出力して終了です。
print(count)
シミュレーション(改善)
上記の解法で問題なく AC を取ることができますが、もう少し改善できるところがあります。
たとえば、今回「すべて偶数か調べる」関数を定義しましたが、python組み込みの関数としてallがあります。これは、引数がすべてTrueであったときだけTrueを返し、一つでもFalseがあればFalseとなる関数です。
つまり、リストの各要素が偶数か調べた配列を内包表記で作って渡せば、自前で関数を用意する必要はなくなります。
count = 0
while all([ai % 2 == 0 for ai in a]):
a = [ai // 2 for ai in a]
count += 1
これをさらに改善できます。内包表記[A for B in C]ですが、これはリストに変換することを示す角カッコ[]とジェネレータ式(A for B in C)の組み合わせになっています(ジェネレータ式の丸カッコは、それが唯一の引数の場合省略できます。[A for B in C]はlist(A for B in C)のシンタックスシュガーであり、これはlist((A for B in C))の省略でもあるわけです)。
そして、関数allは引数としてリストに限らず、イテラブルなオブジェクトを取ることができます。イテラブルなオブジェクトとは、簡単に言うとひとつひとつ要素を取り出すことができるようなもので、for文に対応するオブジェクトと言い換えることができます。リストの他にはタプルやセットがあります。辞書もイテラブルなオブジェクトですが、取り出せるのはキーだけです。
ここまで書けばピンとくる人もいるかと思いますが、ジェネレータ式もイテラブルなオブジェクトのひとつです。ゆえに、以下のように書き換えることができます。
count = 0
while all(ai % 2 == 0 for ai in a):
a = [ai // 2 for ai in a]
count += 1
リストの内包表記ではなくジェネレータ式を直接書くことの利点は文字数を節約できるだけではありません。内包表記でリストを作るとき、各要素を実際に計算してリストを作るのに対し、ジェネレータ式はいわば「計算するためのルール」そのものを取り扱うことができます。
つまり、all関数にリストの内包表記を渡すと、内包表記によって実際にすべての要素が計算され、その後で中にFalseがあるかどうかを調べることになりますが、ジェネレータ式ではひとつひとつを計算していき、途中でFalseが出てきたら即中断することができるため、時間が節約できるのです。
NTZを直接求めて最小を探す
ここまでの説明ではいつまで経ってもint#bit_countが出てきませんでした。実は、シミュレーションするよりもスマートに解く方法が存在するのです。それを考えつくのは少々難しいですが、難しいのはアイデアまでで、計算の内容はさほどでもありません。
突然ですが、$120$ という数字を $10$ で割るとどうなるでしょう。答えは当然 $12$ であり、みなさんもすぐ分かると思います。
では、どのようにして $12$ という数字を思いついたでしょうか。まさか愚直に割り算の筆算などをしたわけではないと思います。
我々が無意識に使っている十進数では、$10$ を一つのまとまりとして扱っています。たとえば $120$ なら $100 = 10^2$ が $1$ 個、$10 = 10^1$ が $2$ 個、$1 = 10^0$ が $0$ 個という風にです。それを $10$ で割るのですから、当然 $10 = 10^1$ が $1$ 個、$1 = 10^0$ が $2$ 個となり、すなわち $12$ となるわけです。これは見た目上 $120 \to 12$ という風に、右にひとつずらしたようになります。
二進数でも同じことで、たとえば $6$ を $2$ で割ると $3$ になりますが、これも二進数で表せば $\bin{110} \to \bin{11}$ となり、右にひとつずらしていることになります。これをコンピュータの世界では「(右)シフト」といい、これこそが問題のタイトル“Shift Only”の由来でしょう。
さて、もう一度十進数の例に戻りましょう。$120$ は $10$ で $1$ 回割れます。$3700$ は $2$ 回割れます。これは当然、右シフトするのですから $1$ の位から連続する $0$ の数を数えるのと一緒です。
二進数でも同じことで、$6$ は $2$ で $1$ 回割ることができ、$56$ は $3$ 回割れますが、二進数で表せばそれぞれ $\bin{110}$、$\bin{111000}$ となりますから一目瞭然です。
すなわち、今回の問題は「二進数で表記した際、 $1$ の位から連続する $0$ の数を求め、その最小を答えよ」と置き換えることができるのです。ここで求めたい値を NTZ: Number of Trailing Zero とよび、わりと頻出する概念でもあります。
では、それをどのように求めるかです。これにはビット演算のマジックが必要になります。
まず、いままで見てきた $\bin{110}$ のような二進数は、$\bin{\cdots000110}$ というように、上の桁が無限に $0$ で埋められているものとみなすことができます。
では反対に、すべての桁が $1$ で埋められている、$\bin{\cdots111}$ という架空の数を考えてみてください。これは十進数でいうと $\cdots999$ みたいな感じです。
これに $1$ を足すとどうなるでしょう。無限に繰り上がりしつづけますから、逆説的にすべての桁が $0$ で埋められる(納得できない方は、「$0$ にならない桁がない」とお考えください。有限ならどこかで繰り上がりが止まりますが、無限なので止まらないのです)と考えることができます。$\bin{\cdots000}$ は、明らかに $0$ です。
$1$ を足して $0$ になる数は、普通 $-1$ ですから、この架空の数は $-1$ として扱うことにしましょう。実際、コンピュータでマイナスの数を表現する場合、このような考え方がでてきます。コンピュータの場合桁数は有限ですが、溢れた分は無視するのです。これを「二の補数」といいます。
さて、ここである数 $x$ に対し、それを二進数で表現した時の $0$ と $1$ をすべての桁でひっくり返す $\lnot x$ というものを考えます。例えば $\lnot 6 = \lnot \bin{110} = \bin{\cdots111001}$ というような感じです。
ここで $x + \lnot x$ を考えると、当然すべての桁が互い違いのため、繰り上がりすることなくすべて $1$ になりますから、常に $x + \lnot x = \bin{\cdots111} = -1$ が成り立つことがわかります。
この式を変形すると、$-x = \lnot x + 1$ という式が得られます。では、こうして得られた $-x$ は、もとの $x$ に対してどのような性質をもつでしょうか。
具体例として $x = 101100_2$ という数を当てはめてみます。 $\lnot x = \cdots111010011_2$ です。これに $1$ を足すと、もともと $0$ が連続していた部分が繰り上がり続け、もともと初めて $1$ が登場した部分 で繰り上がりが止まります。それより上の桁は$\lnot x$ のままですから、もともとの数の桁の反転です。よって、$-x = \bin{\cdots 111010100}$ となります。
さて、$-x$ の性質についてまとめます。
- 下から数えてもともと $0$ が連続していた部分 → $0$ のまま
- 下から数えてもともと初めて $1$ が登場した桁 → $1$ のまま
- それより上の桁 → もとの反転
ここで、特殊な演算 $\cap$ を用意します。 $x \cap y$ は、$x$ と $y$ をそれぞれ二進数で表記したとき、両方が $1$ になる桁のみ $1$ となり、それ以外は $0$ になるような二進数表記の数字を返す演算です。たとえば、 $9 \cap 10 = \bin{1001} \cap \bin{1010} = \bin{1000} = 8$ のような感じです。
これを使って $x \cap -x$ を計算するとどうなるでしょう。
- 下から数えてもともと $0$ が連続していた部分 → $0$ のまま → 両方 $0$ なので $0$
- 下から数えてもともと初めて $1$ が登場した桁 → $1$ のまま → 両方 $1$ なので $1$
- それより上の桁 → もとの反転 → 互い違いなので $0$
となりますから、$x$ を二進数表記したとき、下から数えて初めて $1$ が登場した桁以外を $0$ に置き換えた数が得られます。つまり、$\bin{101100}$ を $\bin{000100}$ のように変換できました。
さて、我々が最初に求めたかったのはなんだったでしょう。$1$ の位から連続する $0$ の個数でしたね。では、$\bin{000100}$ から $1$ を引いてください。繰り下がりによって $\bin{000011}$ となりました。
もうおわかりですね。この $1$ の数を数えればいいのです。そして、それはint#bit_countによって実現できます!
では Python で書き下していきましょう。 $x \cap y$ は Python ではx & yと書けます。最小値は組み込みのmin関数で求めることができ、これもジェネレータ式を入れることができます。
_ = input()
a = [int(n) for n in input().split()]
#count = min(((ai & -ai) - 1).bit_count() for ai in a) ## Python 3.10
count = min(bin((ai & -ai) - 1).count("1") for ai in a)
print(count)
偶数判定も繰り返しも使うことなく答えを求めることができました。
ひとつの数にまとめてから NTZ を求める
上でも十分なのですが、もうすこし別解があります。
$x \cap y$ と対をなす $x \cup y$ という演算があります。これは、両方が $0$ になる桁のみ $0$ となり、それ以外は $1$ になるというもので、双対関係にあります。Python ではx | yと書けます。
この演算を使って $b = A_1 \cup A_2 \cup \ldots \cup A_N$ というように $A$ をすべてまとめてしまうとどうなるでしょう。すべて $0$ である桁のみが $0$ となるわけなので、$b$ の NTZ は $A$ の各要素の NTZ の最小に一致します。
_ = input()
a = [int(n) for n in input().split()]
b = 0
for ai in a:
b |= ai
#count = ((b & -b) - 1).bit_count() ## Python 3.10
count = bin((b & -b) - 1).count("1")
print(count)
これでも答えを得ることができます。
for 文を使わず 1 行で $b$ を求めることもできます。これは組み込みの関数では実現できませんが、標準ライブラリにあるfunctools.reduceを使うことで実現できます。
from functools import reduce
これはどんな関数かというと、要素をひとつずつ取り出してなんらかの関数でまとめていき、最終的にひとつの値を得るものです。要素すべての合計を得るsumという組み込み関数がありますが、
assert reduce(lambda x, y: x + y, l) == sum(l)
のように、それをより一般化した関数です。
reduce関数の記法は以下の感じです。
reduce(function, iterable, initializer)
funtionは引数をふたつ取る関数、iterableはイテラブルなオブジェクト、initializerは初期値(省略可能)です。functionに与える関数を 1 行で書くにはラムダ式を使います。たとえば、
def hogehoge(x, y):
return some_expression
というような関数を、
lambda x, y: some_expression
と書くことができます。
これによって
b = reduce(lambda x, y: x | y, a)
と一行で求めることができました。
余談ですが、自分でラムダ式を使って定義する代わりに、operatorという標準ライブラリにある「関数形式の標準演算子」を使う方法もあります。+はadd、|はor_という名前で定義されています。
from operator import add, or_
assert reduce(add, l) == sum(l)
b = reduce(or_, a)
解けた!
というわけで、最終的な私の提出は以下のコードです。
from functools import reduce
from operator import or_
_ = input()
a = [int(n) for n in input().split()]
b = reduce(or_, a)
# count = ((b & -b) - 1).bit_count() ## Python 3.10
count = bin((b & -b) - 1).count("1")
print(count)
