B - Split? Editorial by rsk0315
split の判定をビット演算で行う方法を紹介します。
予め、「\(i\) 番目のレーンにピンがあれば \(i\)-bit 目が 1
、そうでなければ 0
」を表す整数を作っておきます。レーンのどちらを \(0\) 番目とするかはどちらでもよいですが、以下の例ではレーンの左側とビット表現の左側が対応するようにしています。
たとえば、サンプル 1 の例では以下のようになります。
# ピン(入力で与えられる)
0101110101
# レーン
x o x o
o o o
o x
x
# ビット表現(これを計算しておく)
0111011
このビット表現において、1
が連なる部分が 2 つ以上あれば Yes
、そうでなければ No
です(s[0]
については別で処理する)。
上記の整数を a
とおくと、a == 0
のとき No
なので、以下 a > 0
とします。
a
のうち最も右にある 1
のみからなる整数は a & -a
と表せることが知られています。たとえば、a
のビット表現が 0010110
のとき a & -a
のビット表現は 0000010
です。
そこで、a
にこの a & -a
を足すと、一番右にある連なる 1
たちが(繰り上がりによって)一つの 1
になります。a
が 0010110
のとき a + (a & -a)
は 0011000
、0111011
のとき 0111100
などです。
さて、この時点で 1
がちょうど一つであれば、元々の 1
の連なりがちょうど一つであったこと(元問題の Yes/No の条件)に相当するので、それを判定したいです。これは、2 の冪乗であることと同値です(a > 0
なので a + (a & -a) > 0
に注意)。
b = a + (a & -a)
とし、b
が 2 の冪乗かを判定します。これは、b & (b - 1)
が 0
かを判定すればよいです(C++ のような言語では、演算子の優先順位のせいで (b & (b - 1)) == 0
のように書く必要があります)。
なお、a == 0
のとき b == 0
であり、0 & (0 - 1) == 0
なので、a > 0
かどうかで分けなくても同じ値を得られます。よって、以下のように求められます。
初めて見た人は、以下が成り立つ理由を確認しておくとよいでしょう。
a > 0
のとき、
a & -a
は、a
のうち最も右の1
のみからなる整数となる。a & (a - 1)
は、a
が 2 の冪乗のとき、およびそのときに限り0
となる。
posted:
last update: