Pythonでバイナリ文字列を「1」の数が等しい3つに分割する方法の数を求めるプログラム

問題の概要

バイナリ文字列 s が与えられたとき、これを3つの空でない文字列 s1、s2、s3 に分割することを考えます。このとき、s1 + s2 + s3 = s（連結）が成り立ち、かつ各部分文字列に含まれる '1' の個数がすべて等しくなるような分割方法の数を求めます。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。

例えば、入力が s = "11101011" の場合、出力は 2 になります。「11 | 1010 | 11」と「11 | 101 | 011」の2通りの分割方法が存在するためです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• count := 文字列 s に含まれる '1' の総数を数える
• m := 10^9 + 7（剰余計算用の定数）
• ans := サイズ2の配列を用意し、0で初期化する
• count を3で割った余りが0でない場合 → '1' を3等分できないため 0 を返す
• count が0の場合 → どの位置で分割しても条件を満たすため、(n-1)C2 mod m を返す（n は文字列の長さ）
• left := 0、right := 文字列の長さ - 1、cum_s := 0、cum_e := 0 で初期化する
• cum_s または cum_e が count // 3 以下である間、以下を繰り返す
  • s[left] が '1' なら cum_s をインクリメント
  • s[right] が '1' なら cum_e をインクリメント
  • cum_s が count // 3 と等しければ ans[0] をインクリメント
  • cum_e が count // 3 と等しければ ans[1] をインクリメント
  • left を1増やし、right を1減らす
• 最後に (ans[0] * ans[1]) mod m を返す

アルゴリズムのポイント

このアルゴリズムの鍵は、左から数えて count // 3 個目の '1' に到達できる位置の数（ans[0]）と、右から数えて count // 3 個目の '1' に到達できる位置の数（ans[1]）を掛け合わせる点にあります。両端の分割位置を決めれば、中央の部分には自動的に残りの count // 3 個の '1' が含まれるため、全体の分割方法の数は ans[0] × ans[1] で求まります。

実装例

理解を深めるために、以下の実装例をご覧ください。なお、comb 関数を使用する場合は from math import comb のインポートが必要です。

def solve(s):
   count = s.count("1")
   m = 10**9 + 7
   ans = [0, 0]
   if count % 3 != 0:
      return 0
   elif count == 0:
      return comb(len(s)-1,2) % m
   left = 0
   right = len(s)-1
   cum_s = 0
   cum_e = 0
   while(cum_s <= count//3 or cum_e <= count//3):
      if s[left] == "1":
         cum_s+=1
      if s[right] == "1":
         cum_e+=1
      if cum_s == count//3:
         ans[0]+=1
      if cum_e == count//3:
         ans[1]+=1
      left += 1
      right -= 1
   return (ans[0]*ans[1]) % m

s = "11101011"
print(solve(s))

入力

"11101011"

出力

2