自分が得た学び
- 一律にフラグのオンオフを管理するときは, リスト管理よりもビット管理の方がいいことがある
- 例えば, 二つのオブジェクトのフラグ状況を見て出力が変化する場合など
記事の執筆経緯
この問題を解いていました。
（問題ページはこちら >>> ABC270 A問題 1-2-4 Test)
3 問の問題からなる試験があり、それぞれの問題の配点は 1 点、2 点、4 点でした。高橋君、青木君、すぬけ君の 3 人がこの試験を受け、 高橋君は A 点、青木君は B 点を取りました。すぬけ君は、高橋君と青木君のうち少なくとも一方が解けた問題は解け、 2 人とも解けなかった問題は解けませんでした。すぬけ君の点数を求めてください。ただし、この問題の制約下で、すぬけ君の点数は一意に定まる事が証明できます。
お恥ずかしいことにずっと前の自分なら場合分けをして、A君とB君の正解状況をリストで管理していました。恥ずかしい…(けど解けていたからヨシ！)
最近になって、状況をビット列で管理するという手法を知り、今回実践してみた次第です。
環境
Python(3.8.2)
どう考える？
- 二人の状況で出力点数が変化する ⇒ ってことはビット管理の方がいい？
- なおかつ、問題の状況ってor演算になっているのでは？
方針
- Aの点数、Bの点数を2進数化しビット列にする
- あとはor演算を取るだけなんじゃない?
ACコード
A, B = map(int, input().split())
C = A | B
print(C)
# print(bin(A)) >>> A=5のとき, 0b101
# print(bin(B)) >>> B=3のとき, 0b11
# print(bin(C)) >>> 以上のとき, 0b111
ビット演算種類
# bit列に対して, シフト演算, or/and/xor/not演算をかけることができる
# int型の変数にそのままbit演算をかけることができる
2つ右シフト : A >> 2
3つ左シフト : B << 3
or : A | B
and : A & B
xor : A ^ B
not : ~A
メモ : ビット演算はint型変数にそのまま使う
ビット演算をかじった上でここにちょっとひっかかりました。
当初のイメージでは、ビット列に変換してから使う（bin()に入れてから使う）と思ってたけど、実際は違う。
int型の変数にそのまま適用することで使えてしまうらしい。
A = 10
B = 12
# A, Bのint型変数に対してそのままビット演算を適用
print(bin(A)) >>> 0b1010
print(bin(B)) >>> 0b1100
print(bin(A | B)) >>> 0b1110
print(bin(A & B)) >>> 0b1000
print(bin(A ^ B)) >>> 0b110
print(bin(~A)) >>> -0b1011 # 2の補数表現になっていることに注意
print(bin(A>>2)) >>> 0b10
print(bin(B<<3)) >>> 0b1100000
ただし、bin()で変換した値はstr型になるため、ビット演算を適用することはできない
A = 10
B = 12
# ここで一度bit列(str型)への変換を挟みます
A_bit = bin(A)
B_bit = bin(B)
print(A_bit & B_bit)
>>> Traceback (most recent call last):
File "./Main.py", line 5, in <module>
print(A_bit & B_bit)
TypeError: unsupported operand type(s) for &: 'str' and 'str'
# やっぱりbin()使うと, str型になるからダメだって
でも、ビット列にしないとなんだか状況が分かりづらい…
そんなときは、0bXXXの表記で値を入れればOK
（これだとstr型にならない、というか結局は2進数表記で整数値を入れただけにすぎないので何の問題も起こらない）
A_bit = 0b1010
B_bit = 0b1100
print(bin(A_bit & B_bit)) >>> 0b1000
これでもうビット列で状況を管理できそうです。
終わりに
自分用のメモとして記事を作成しましたので、非常に読みづらく、かつミスが多いかと思われます。ミスを発見した際にはスルーしていただくか、お手柔らかにご指摘していただけると嬉しいです。