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 かどうかで分けなくても同じ値を得られます。よって、以下のように求められます。

• 提出 #34585798, Rust
• 提出 #34585697, C++

初めて見た人は、以下が成り立つ理由を確認しておくとよいでしょう。

a > 0 のとき、

• a & -a は、a のうち最も右の 1 のみからなる整数となる。
• a & (a - 1) は、a が 2 の冪乗のとき、およびそのときに限り 0 となる。