Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで「1」のみを含む部分文字列の個数を求めるプログラム

問題の概要

2進数文字列 s が与えられたとき、すべての文字が「1」である部分文字列の個数を求めます。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返す必要があります。

例えば、入力が s = "1011010" の場合、出力は 5 になります。これは、単独の「1」が4回、「11」が1回現れるためです。

解法のアプローチ

この問題は、次の手順に従って解くことができます。

  • m := 10^9 + 7 とします

  • result := 0 で初期化します

  • 2進数文字列を「0」で分割します

  • 分割された各要素 x に対して、以下を処理します

    • x が空文字列の場合は、次の反復へ進みます

    • result に x の長さ n に対する n × (n + 1) / 2 の値を加算します

  • result を m で割った余りを返します

この解法のポイントは、連続する「1」が n 個並んでいる場合、そこから選べる部分文字列の総数が n(n+1)/2 通りになるという組み合わせの性質を利用することです。「0」で文字列を分割すれば、それぞれの連続した「1」のブロックごとに計算できます。

実装例

以下のコードで実際の動作を確認してみましょう。

def solve(s):
    m = 10**9+7
    result = 0
    for x in s.split('0'):
        if not x: continue
        result += (len(x)*(len(x)+1)) // 2
    return result % m

s = "1011010"
print(solve(s))

入力

"1011010"

出力

5
  1. Pythonで同じラベルを持つサブツリー内のノード数を求めるプログラム

    ここでは、n個のノードからなる根付きの一般木を考えます。ノードには0からn-1までの番号が振られており、各ノードには小文字の英字ラベルが割り当てられています。ラベルは配列labelsとして与えられ(labels[i]がi番目のノードのラベル)、木は辺リストで表現されます。各辺eは[u, v]という形式で、uが親、vが子であることを意味します。 求めたいのは、サイズnの配列Aです。A[i]には「i番目のノードと同じラベルを持つ、そのサブツリー内のノードの総数」を格納します。 例えば、入力が次のような場合を考えてみましょう。 n = 5、label = ccaca のとき、出力は [3, 2,

  2. Pythonで最大の成功確率を持つパスを見つけるプログラムの実装方法

    問題の概要 n 個のノード(ノードには 0 から順に番号が振られています)からなる無向重み付きグラフを考えます。このグラフは辺リスト(edge list)として入力され、各辺 e には「その辺を通過する際の成功確率」probability[e] が割り当てられています。さらに、開始ノード(start)と終了ノード(end)も与えられます。 求めたいのは、start から end へ移動するときに成功確率が最大となる経路であり、答えとしてその成功確率を返します。経路がひとつも存在しない場合は 0 を返してください。 たとえば、次のような入力が与えられたとします。 この場合の出力は 0.25