今回はpaiza 累積和メニューセクショ4【区間内の個数(文字列)】を解説します。
n文字の文字列strの、任意の区間内の"b"の数はいくつか?を出力する問題です。
本記事で使用しているアルゴリズムやメソッドについて
解答例で使っているアルゴリズムやメソッドについて、下記の記事で詳しく解説していますので参考にしてみて下さい。
- [アルゴリズム(Ruby)]累積和
- [アルゴリズム(Ruby)]線形探索法
- [Ruby] 標準入力によるデータ取得1
- [Ruby] 標準入力によるデータ取得2
- [Ruby] 標準入力によるデータ取得3
- [Ruby] 標準出力(データを任意に整形して出力する)
- [Ruby]配列の基本操作1
- [Ruby]繰り返し処理
- [Ruby]条件分岐
- [Ruby]繰り返し処理
累積和メニュー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
入力値最終行の末尾に改行が1つ入ります。
期待する出力
文字列 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()))
今回のまとめ
累積和を使って、文字列の任意の区間の条件を満たす文字の数を求めることが出来ました。