paiza プログラミング

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

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

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

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

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

累積和メニュー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

空の 配列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 = []
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 問題を解く流れ

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

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 カエレバ
楽天市場
Amazon
Yahooショッピング

-paiza, プログラミング
-

© 2024 じゃいごテック