[Ruby|Python]paiza 累積和メニュー4 【区間内の個数 (文字列)】

2023-10-24

今回はpaiza 累積和メニューセクショ4【区間内の個数(文字列)】を解説します。

n文字の文字列strの、任意の区間内の"b"の数はいくつか？を出力する問題です。

本記事で使用しているアルゴリズムやメソッドについて
累積和メニュー4：【区間内の個数(文字列)】
今回のまとめ

本記事で使用しているアルゴリズムやメソッドについて

解答例で使っているアルゴリズムやメソッドについて、下記の記事で詳しく解説していますので参考にしてみて下さい。

累積和メニュー4：【区間内の個数(文字列)】

4-STEP1: 区間内の個数 (文字列) 1 (paizaランク C 相当)

"b"または"w"からなる10文字の文字列 str="bwbwwbwbwb"で、3文字目(str[2])から8文字目(str[7])の区間内に"b"がいくつあるかを出力する問題です。

str[0] から str[7] までの"b"の数 = b[0] + b[1] + b[2] + b[3] + b[4] + b[5] + b[6] + b[7] = s[8] = 4
str[0] から str[1] までの"b"の数 = b[0] + b[1] = s[2] = 1

str[2] から str[7] までの"b"の数 = s[8] - s[2] = 4 - 1 = 3

Ruby解答例1-1

空の 配列b を用意し、文字列str の先頭から順に文字を調べ、"b"なら1、"w"なら0を配列b の末尾に追加します。
次に 配列b の 累積和s を求め、str[2] から str[7] までの区間の"b"の数を s[7+1] - s[2] で求めます。

# 入力
l = 3
r = 8
str = "bwbwwbwbwb"

# b: 1, w: 0
b = []
str.split("").each do |c|
  if c == "b"
    b << 1
  else
    b << 0
  end
end

# 累積和
s = [0]
b.each { |num| s << s[-1] + num }

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
puts num_of_b

Ruby解答例1-2

Ruby解答例1-1の

str.split("") を str.chars に変更
if文を三項演算子に変更
空配列b=[] を用意して要素を追加した部分をmapに変更

今後はこのコードをベースに実装します。

# 入力
l = 3
r = 8
str = "bwbwwbwbwb"

# b: 1, w: 0
b = str.chars.map { |c| c == "b" ? 1 : 0 }

# 累積和
s = [0]
b.each { |num| s << s[-1] + num }

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
puts num_of_b

Ruby解答例2

"b"が1、"w"が0の 配列b を作らずに 文字列str のループから直接"b"の 累積和s を作ります。

# 入力
l = 3
r = 8
str = "bwbwwbwbwb"

# b: 1, w: 0
b = str.chars.map { |c| c == "b" ? 1 : 0 }

# 累積和
s = [0]
b.each { |num| s << s[-1] + num }

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
puts num_of_b

Python解答例1-1

# 入力
l = 3
r = 8
str = "bwbwwbwbwb"

# b: 1, w: 0
b = []
for c in list(str):
    if c == "b":
        b.append(1)
    else:
        b.append(0)

# 累積和
s = [0]
for num in b:
    s.append(s[-1] + num)

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
print(num_of_b)

Python解答例1-2

Python解答例1-1の

if文を三項演算子に変更
空配列b=[] を用意して要素を追加した部分をリスト内包表記に変更

今後はこのコードをベースに実装します。

# 入力
l = 3
r = 8
str = "bwbwwbwbwb"

# b: 1, w: 0
b = [1 if c == "b" else 0 for c in list(str)]

# 累積和
s = [0]
for num in b:
    s.append(s[-1] + num)

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
print(num_of_b)

Python解答例2

"b"が1、"w"が0の 配列b を作らずに 文字列str のループから直接"b"の 累積和s を作ります。

# 入力
l = 3
r = 8
str = "bwbwwbwbwb"

# 累積和 (b: 1, w: 0)
s = [0]
for c in list(str):
    s.append(s[-1] + (1 if c == "b" else 0))

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
print(num_of_b)

4-STEP2: 区間内の個数 (文字列) 2 (paizaランク C 相当)

"b"または"w"からなる10文字の文字列 str が与えられ、3文字目(str[2])から8文字目(str[7])の区間内に"b"がいくつあるかを出力する問題です。

入出力例

INPUT1の例
str[2] から str[7] の区間 ["w", "b", "w", "b", "b", "w"]に"b"は 3個なので 3 を出力

INPUT2の例
str[2] から str[7] の区間 ["b", "b", "b", "b", "b", "b"] に"b"は 6個なので 6 を出力

INPUT1 = <<"EOS"
bwwbwbbwbw
EOS
OUTPUT1 = <<"EOS"
3
EOS

INPUT2 = <<"EOS"
wbbbbbbbww
EOS
OUTPUT2 = <<"EOS"
6
EOS

Ruby解答例1

文字列strを受け取る処理を追加します。あとはSTEP1-Ruby解答例1-2と同じです。

# 入力
l = 3
r = 8
str = gets.chomp

# b: 1, w: 0
b = str.chars.map { |c| c == "b" ? 1 : 0 }

# 累積和
s = [0]
b.each { |num| s << s[-1] + num }

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
puts num_of_b

Ruby解答例2

文字列strを受け取る処理を追加します。あとはSTEP1-Ruby解答例2と同じです。

# 入力
l = 3
r = 8
str = gets.chomp

# 累積和 (b: 1, w: 0)
s = [0]
str.chars.each { |c| s << s[-1] + (c == "b" ? 1 : 0) }

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
puts num_of_b

Python解答例1

文字列strを受け取る処理を追加します。あとはSTEP1-Python解答例1-2と同じです。

# 入力
l = 3
r = 8
str = input()

# b: 1, w: 0
b = [1 if c == "b" else 0 for c in list(str)]

# 累積和
s = [0]
for num in b:
    s.append(s[-1] + num)

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
print(num_of_b)

Python解答例2

文字列strを受け取る処理を追加します。あとはSTEP1-Python解答例2と同じです。

# 入力
l = 3
r = 8
str = input()

# 累積和 (b: 1, w: 0)
s = [0]
for c in list(str):
    s.append(s[-1] + (1 if c == "b" else 0))

# 区間の "b" の数
num_of_b = s[r] - s[l - 1]
print(num_of_b)

4-STEP3: 区間内の個数 (文字列) 3 (paizaランク C 相当)

1行目で区間x, y、2行目で10個の整数 a[0], a[1] ... a[9] が半角スペース区切りで与えられ、a[x] から a[y]の区間内に偶数がいくつあるかを出力する問題です。

与えられる条件は以下の通りです。

1 ≦ x ≦ y ≦ 10

入出力例

INPUT1の例
str[2] から str[7] の区間 ["w", "b", "w", "b", "b", "w"]に"b"は 3個なので 3 を出力

INPUT2の例
str[2] から str[6] の区間 ["w", "b", "b", "b", "b"]に"b"は 4個なので 4 を出力

INPUT1 = <<"EOS"
3 8
bwwbwbbwbw
EOS
OUTPUT1 = <<"EOS"
3
EOS

INPUT2 = <<"EOS"
3 7
wbwbbbbwwb
EOS
OUTPUT2 = <<"EOS"
4
EOS

Ruby解答例1

入力1行目から x, y、2行目から文字列strを受け取ります。あとはSTEP2-Ruby解答例1と同じです。

# 入力
x, y = gets.split.map(&:to_i)
str = gets.chomp

# b: 1, w: 0
b = str.chars.map { |c| c == "b" ? 1 : 0 }

# 累積和
s = [0]
b.each { |num| s << s[-1] + num }

# 区間の "b" の数
num_of_b = s[y] - s[x - 1]
puts num_of_b

Ruby解答例2

$stdin.read で入力を一括で受け取っています。あとはSTEP2-解答例2と同じです。（入力終了は ctrl+d）

# 入力
input_lines = $stdin.read.split("\n")
x, y = input_lines[0].split.map(&:to_i)
str = input_lines[1]

# 累積和 (b: 1, w: 0)
s = [0]
str.chars.each { |c| s << s[-1] + (c == "b" ? 1 : 0) }

# 区間の "b" の数
num_of_b = s[y] - s[x - 1]
puts num_of_b

Python解答例1

入力1行目から x, y、2行目から配列aの値を受け取ります。あとはSTEP2-Python解答例1と同じです。

# 入力
x, y = map(int, input().split())
str = input()

# b: 1, w: 0
b = [1 if c == "b" else 0 for c in list(str)]

# 累積和
s = [0]
for num in b:
    s.append(s[-1] + num)

# 区間の "b" の数
num_of_b = s[y] - s[x - 1]
print(num_of_b)

Python解答例2

open(0).read() で入力を一括で受け取り、多重代入しています。あとはSTEP2-解答例2と同じです。（入力終了は ctrl+d）

# 入力
input_lines = open(0).read().split("\n")
x, y = map(int, input_lines[0].split())
str = input_lines[1]

# 累積和 (b: 1, w: 0)
s = [0]
for c in list(str):
    s.append(s[-1] + (1 if c == "b" else 0))

# 区間の "b" の数
num_of_b = s[y] - s[x - 1]
print(num_of_b)

4-FINAL: 【区間内の個数 (文字列) 】区間内の個数 (文字列) 4 (paizaランク C 相当)

問題

1 行目に整数 N, X, Y が与えられます。

2 行目に 'b' と 'w' で構成された長さ N の文字列 str が与えられます。

文字列 str の X 文字目から Y 文字目までの 'b' の個数を累積和を用いて求めてください。

入力される値

1 行目に整数 N, X, Y が与えられます。
2 行目に 'b' と 'w' で構成された長さ N の文字列 str が与えられます。

N X Y
str

入力値最終行の末尾に改行が１つ入ります。

期待する出力

文字列 str の X 文字目から Y 文字目までの 'b' の個数を出力してください。

末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

1 ≦ N ≦ 1,000
1 ≦ X ≦ Y ≦ N
str は 'b' と 'w' からなる長さ N 文字の文字列

入力例1: 10 3 8
bwwbwbbwbw

出力例1: 3

入力例2: 10 3 8
wbbwbbbwwb

出力例2: 4

攻略ポイント

ポイント

累積和

[アルゴリズム(Ruby)]累積和

メソッドの定義と呼び出し

[Ruby]メソッドの定義と呼び出し

Ruby 問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<"EOS"
10 3 8
bwwbwbbwbw
EOS
OUTPUT1 = <<"EOS"
3
EOS

INPUT2 = <<"EOS"
10 3 8
wbbwbbbwwb
EOS
OUTPUT2 = <<"EOS"
4
EOS

# 確認用コード
p INPUT1
p OUTPUT1
p INPUT2
p OUTPUT2
# 実行結果
# > "10 3 8\nbwwbwbbwbw\n"
# > "3\n"
# > "10 3 8\nwbbwbbbwwb\n"
# > "4\n"

続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。

まず、入力データを受け取る処理を書きます。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, x, y = input_lines[0].split.map(&:to_i)
  str = input_lines[1]

  # 確認用コード
  [x, y, str]
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > [3, 8, "bwwbwbbwbw"]
# > [3, 8, "wbbwbbbwwb"]

データが正しく受け取れていれば、問題を解く処理を書いていきます。

文字列strの文字を先頭から順に見ていき、文字が"b"なら1、"w"なら0に変換した配列bを作ります。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, x, y = input_lines[0].split.map(&:to_i)
  str = input_lines[1]

  # b: 1, w: 0
  b = str.chars.map { |c| c == "b" ? 1 : 0 }

  # 確認用コード
  [str, b]
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > ["bwwbwbbwbw", [1, 0, 0, 1, 0, 1, 1, 0, 1, 0]]
# > ["wbbwbbbwwb", [0, 1, 1, 0, 1, 1, 1, 0, 0, 1]]

配列bの累積和sを求め、 s[y] - s[x-1] で str[x-1] から str[y-1] の区間内の"b"の数を求めます。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, x, y = input_lines[0].split.map(&:to_i)
  str = input_lines[1]

  # b: 1, w: 0
  b = str.chars.map { |c| c == "b" ? 1 : 0 }

  # 累積和
  s = [0]
  b.each { |num| s << s[-1] + num }

  # 区間の "b" の数
  s[y] - s[x - 1]
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > 3
# > 4

INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。

Ruby 解答コード

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, x, y = input_lines[0].split.map(&:to_i)
  str = input_lines[1]

  # b: 1, w: 0
  b = str.chars.map { |c| c == "b" ? 1 : 0 }

  # 累積和
  s = [0]
  b.each { |num| s << s[-1] + num }

  # 区間の "b" の数
  s[y] - s[x - 1]
end

puts solve($stdin.read)

Ruby 他の解答例

STEP1～3の解答例2に倣った書き方です。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  _, x, y = input_lines[0].split.map(&:to_i)
  str = input_lines[1]

  # 累積和 (b: 1, w: 0)
  s = [0]
  str.chars.each { |c| s << s[-1] + (c == "b" ? 1 : 0) }

  # 区間の "b" の数
  s[y] - s[x - 1]
end

puts solve($stdin.read)

Python 問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = """\
10 3 8
bwwbwbbwbw
"""
OUTPUT1 = """\
3
"""

INPUT2 = """\
10 3 8
wbbwbbbwwb
"""
OUTPUT2 = """\
4
"""

# 確認用コード
print(repr(INPUT1))
print(repr(OUTPUT1))
print(repr(INPUT2))
print(repr(OUTPUT2))
# 実行結果
# > '10 3 8\nbwwbwbbwbw\n'
# > '3\n'
# > '10 3 8\nwbbwbbbwwb\n'
# > '4\n'

続いて問題を解くメソッド（solveメソッドとします）を変数の下に定義します。

まず、入力データを受け取る処理を書きます。

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, x, y = map(int, input_lines[0].split())
    str = input_lines[1]

    # 確認用コード
    return [x, y, str]


# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [3, 8, 'bwwbwbbwbw']
# > [3, 8, 'wbbwbbbwwb']

データが正しく受け取れていれば、問題を解く処理を書いていきます。

文字列strの文字を先頭から順に見ていき、文字が"b"なら1、"w"なら0に変換した配列bを作ります。

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, x, y = map(int, input_lines[0].split())
    str = input_lines[1]

    # b: 1, w: 0
    b = [1 if c == "b" else 0 for c in list(str)]

    # 確認用コード
    return [str, b]


# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > ['bwwbwbbwbw', [1, 0, 0, 1, 0, 1, 1, 0, 1, 0]]
# > ['wbbwbbbwwb', [0, 1, 1, 0, 1, 1, 1, 0, 0, 1]]

配列bの累積和sを求め、 s[y] - s[x-1] で str[x-1] から str[y-1] の区間内の"b"の数を求めます。

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, x, y = map(int, input_lines[0].split())
    str = input_lines[1]

    # b: 1, w: 0
    b = [1 if c == "b" else 0 for c in list(str)]

    # 累積和
    s = [0]
    for num in b:
        s.append(s[-1] + num)

    # 区間の "b" の数
    return s[y] - s[x - 1]


# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > 3
# > 4

INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。

Python 解答コード

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, x, y = map(int, input_lines[0].split())
    str = input_lines[1]

    # b: 1, w: 0
    b = [1 if c == "b" else 0 for c in list(str)]

    # 累積和
    s = [0]
    for num in b:
        s.append(s[-1] + num)

    # 区間の "b" の数
    return s[y] - s[x - 1]


print(solve(open(0).read()))

Python 他の解答例

STEP1～3の解答例2に倣った書き方です。

def solve(input_str):
    # 入力
    input_lines = input_str.split("\n")
    _, x, y = map(int, input_lines[0].split())
    str = input_lines[1]

    # 累積和 (b: 1, w: 0)
    s = [0]
    for c in list(str):
        s.append(s[-1] + (1 if c == "b" else 0))

    # 区間の "b" の数
    return s[y] - s[x - 1]


print(solve(open(0).read()))

今回のまとめ

累積和を使って、文字列の任意の区間の条件を満たす文字の数を求めることが出来ました。

【PR】アルゴリズム学習でお世話になった本

アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。

通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。

プログラミングコンテストチャレンジブック第2版問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者～中級者向けに書かれているので解説が非常に丁寧です。

最強最速アルゴリズマー養成講座プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋直大 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。

Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤弘毅 ]

posted with カエレバ

comment

: Ruby プログラミング

[Ruby]配列の基本操作1

こんにちは！じゃいごテックのあつしです。 paizaスキルチェックやスキルアップ問題集でよく使う配列の操作についてご紹介します！配列はとてもボリュームが多いので数回に分けてご紹介しようと思います。 ...

: Ruby プログラミング

[Ruby]メソッドの定義と呼び出し

こんにちは！じゃいごテックのあつしです。今回は自作メソッドの定義と呼び出しについてご紹介します。プログラミングでは繰り返し処理や条件分岐を組み合わせて処理を書いていきますが、ある纏まった処理を使い ...

: paiza プログラミング

[Ruby|Python]paiza 標準入力メニューセクション8（小数点数）

今回はpaiza 標準入力メニューセクション8（小数点数の入力）を解説します。セクション8は、1行目で要素数nが与えられ、続くn行の文字列を受け取り小数点数に変換して受け取る問題と、1行目または1要 ...

: paiza プログラミング

[Ruby]paiza Bランクレベルアップメニュー五目並べ (paizaランク B 相当)の解説

こんにちは！じゃいごテックのあつしです。今回はpaiza Bランクレベルアップメニューから五目並べという問題を解説します。この問題集は二次元配列に関する5個のSTEP問題(D～C級)とFINAL ...

: paiza プログラミング

[Ruby|Python]paiza paizaの森練習問題コンテスト過去問題2

paizaの森練習問題コンテストは、「paizaの森 (Discord)」にて約2か月に1回のペースで開催されており、ユーザー同士が開催時刻にpaizaの森に集まり「よーいドン」で与えられた数問の練習 ...

PREV: [Ruby|Python]paiza 累積和メニュー3 【区間内の個数】
NEXT: [Ruby|Python]paiza 累積和メニュー5 【二次元累積和】

[Ruby|Python]paiza 累積和メニュー4 【区間内の個数 (文字列)】

本記事で使用しているアルゴリズムやメソッドについて

累積和メニュー4：【区間内の個数(文字列)】

4-STEP1: 区間内の個数 (文字列) 1 (paizaランク C 相当)

Ruby解答例1-1

Ruby解答例1-2

Ruby解答例2

Python解答例1-1

Python解答例1-2

Python解答例2

4-STEP2: 区間内の個数 (文字列) 2 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

4-STEP3: 区間内の個数 (文字列) 3 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

4-FINAL: 【区間内の個数 (文字列) 】 区間内の個数 (文字列) 4 (paizaランク C 相当)

問題

攻略ポイント

Ruby 問題を解く流れ

Ruby 解答コード

Ruby 他の解答例

Python 問題を解く流れ

Python 解答コード

Python 他の解答例

今回のまとめ

【PR】アルゴリズム学習でお世話になった本

4-FINAL: 【区間内の個数 (文字列) 】区間内の個数 (文字列) 4 (paizaランク C 相当)