こんにちは！じゃいごテックのあつしです。
今回はpaizaレベルアップ問題集から日別訪問者数の最大平均区間(large)という問題を解説していきたいと思います。こちらは過去にスキルチェックで実際に出題されていた問題らしいです！
難易度は 2015±18 で、A級としては割と簡単な問題だと思います。
日別訪問者数の最大平均区間(large) (paizaランク A 相当)を解いてみる
※ paiza レベルアップ問題集 スキルチェック過去問題セットより
問題
※ この問題は、練習問題「日別訪問者数の最大平均区間 (paizaランク B 相当)」と同じ問題ですが、入力値の条件が異なります。
あなたは、とあるウェブサイトを管理していました。
ある連続したk日間、このウェブサイトでキャンペーンを行ったのですが、いつからいつまでの期間に行ったかを忘れてしまいました。
幸い、ウェブサイトを運営していた全n日分のアクセスログが残っており、1日ごとの訪問者数が分かっています。
とりあえず、連続するk日の中で、1日あたりの平均訪問者数が最も多い期間を、キャンペーンを行った期間の候補だと考えることにしました。
n日分の訪問者数のリストとキャンペーンの日数kが入力されるので、キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を出力してください。
入力される値
入力は2行から成ります。
1行目にはnとkが半角スペース区切りで入力されます。
2行目にはn個の整数a_1, a_2, …, a_nが半角スペース区切りで入力されます。a_iはi日目の訪問者数を表します。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を、この順で半角スペース区切りで1行で出力してください。
条件
すべてのテストケースにおいて、以下の条件をみたします。
- 1≦n≦300,000
- 1≦k≦n
- 0≦a_i≦100
- 入力例1
- 5 3
1 2 3 2 1
- 出力例1
- 1 2
- 入力例2
- 10 2
6 2 0 7 1 3 5 3 2 6
- 出力例2
- 5 1
攻略ポイント
ポイント
- 要素数 n 個の配列中で連続する k 個の範囲について計算する
- 範囲の合計の最大値を求める
- 最大値が何回出現するか数える
- 候補の中で最も早い候補日を求める
- 計算量を考慮する
参考記事
問題を解く流れ
入出力データを準備する
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。INPUT1 が与えられた時に OUTPUT1 を出力すれば正解と言うことになります。
INPUT1 = <<~"EOS" 5 3 1 2 3 2 1 EOS OUTPUT1 = <<~"EOS" 1 2 EOS INPUT2 = <<~"EOS" 10 2 6 2 0 7 1 3 5 3 2 6 EOS OUTPUT2 = <<~"EOS" 5 1 EOS p INPUT1 p OUTPUT1 p INPUT2 p OUTPUT2 # > "5 3\n1 2 3 2 1\n" # > "1 2\n" # > "10 2\n6 2 0 7 1 3 5 3 2 6\n" # > "5 1\n"
入出力データ例をきちんと受け取れていれば確認用コードは削除します。
入力データ受け取りを実装する
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義して処理を追加していきます。
まずは、入力された文字列を各変数に代入します。
- 空文字列(半角スペース・改行文字)で分割し、全ての要素を整数化
- 1個目、2個目の要素を n (訪問者数のリスト), k (キャンペーン期間) に代入
- 続く要素を半角スペースで分割して visitor_count(日毎の訪問者数) に代入
def solve(input_lines) # 入力データを空白文字列（改行と半角スペース）で分割しそれぞれを整数に変換 # 先頭から n: ログの日数, k: キャンペーン日数, 以降を visitor_count に代入する n, k, *visitor_count = input_lines.split.map(&:to_i) # 動作確認用コード [n, k, visitor_count] end p solve(INPUT1) # > [5, 3, [1, 2, 3, 2, 1]]
問題を解く処理を実装する
各変数 n, k, visitor_count にデータが正しく代入されていれば、solve メソッドに処理を追加します。
def solve(input_lines)
# 入力データを空白文字列（改行と半角スペース）で分割しそれぞれを整数に変換
# 先頭から n: ログの日数, k: キャンペーン日数, 以降を visitor_count に代入する
n, k, *visitor_count = input_lines.split.map(&:to_i)
# 1日目 (index: 0) の計算結果を最大として初期化
section_count = visitor_count[..k - 1].sum
campaign = { "candidate" => 1, "index" => 0, "max" => section_count }
# 2日目 (index: 1) から n-k+1 日目（index: n-k）までカウントアップする
(1..n - k).each do |index|
# 計算範囲から外れる日の訪問者数を引く
section_count -= visitor_count[index - 1]
# 計算範囲に追加される日の訪問者数を足す
section_count += visitor_count[index + k - 1]
# 【動作確認用コード】
puts <<~"EOS"
******************************
キャンペーン候補の情報: #{campaign}
今回の範囲情報: "index"=>#{index}, "max"=>#{section_count}
EOS
# campaign の更新をチェックする
if section_count > campaign["max"]
# 【動作確認用コード】
puts "区間最大を更新しました！"
# 【最大を更新した場合】
# candidate: 候補を 1 で初期化
# index: インデックス, max: 最大来客数 を上書きする
campaign["candidate"] = 1
campaign["index"] = index
campaign["max"] = section_count
elsif section_count == campaign["max"]
# 【最大と同じだった場合】
# candidate: 候補を +1 する
campaign["candidate"] += 1
# 【動作確認用コード】
puts "区間最大でした! 候補日を +1 します -> #{campaign["candidate"]}"
end
end
campaign
end
p solve(INPUT1)
# > ******************************
# > キャンペーン候補の情報: {"candidate"=>1, "index"=>0, "max"=>6}
# > 今回の範囲情報: "index"=>1, "max"=>7
# > 区間最大を更新しました！
# > ******************************
# > キャンペーン候補の情報: {"candidate"=>1, "index"=>1, "max"=>7}
# > 今回の範囲情報: "index"=>2, "max"=>6
# > {"candidate"=>1, "index"=>1, "max"=>7}
入出力データ（変数）で動作を確認する
最後に出力されたハッシュがキャンペーン候補の情報ですので、確認用コードをコメントアウトし、 指定された出力形式を返すように修正します。
INPUT1 = <<~"EOS"
5 3
1 2 3 2 1
EOS
OUTPUT1 = <<~"EOS"
1 2
EOS
INPUT2 = <<~"EOS"
10 2
6 2 0 7 1 3 5 3 2 6
EOS
OUTPUT2 = <<~"EOS"
5 1
EOS
def solve(input_lines)
# 入力データを空白文字列（改行と半角スペース）で分割しそれぞれを整数に変換
# 先頭から n: ログの日数, k: キャンペーン日数, 以降を visitor_count に代入する
n, k, *visitor_count = input_lines.split.map(&:to_i)
# 1日目 (index: 0) の計算結果を最大として初期化
section_count = visitor_count[..k - 1].sum
campaign = { "candidate" => 1, "index" => 0, "max" => section_count }
# 2日目 (index: 1) から n-k+1 日目（index: n-k）までカウントアップする
(1..n - k).each do |index|
# 計算範囲から外れる日の訪問者数を引く
section_count -= visitor_count[index - 1]
# 計算範囲に追加される日の訪問者数を足す
section_count += visitor_count[index + k - 1]
# 【動作確認用コード】
# puts <<~"EOS"
# ******************************
# キャンペーン候補の情報: #{campaign}
# 今回の範囲情報: "index"=>#{index}, "max"=>#{section_count}
# EOS
# campaign の更新をチェックする
if section_count > campaign["max"]
# 【動作確認用コード】
# puts "区間最大を更新しました！"
# 【最大を更新した場合】
# candidate: 候補を 1 で初期化
# index: インデックス, max: 最大来客数 を上書きする
campaign["candidate"] = 1
campaign["index"] = index
campaign["max"] = section_count
elsif section_count == campaign["max"]
# 【最大と同じだった場合】
# candidate: 候補を +1 する
campaign["candidate"] += 1
# 【動作確認用コード】
# puts "区間最大でした! 候補日を +1 します -> #{campaign["candidate"]}"
end
end
# 候補数と最初の候補日を半角スペースで区切り末尾に改行を入れる
"#{campaign["candidate"]} #{campaign["index"] + 1}\n"
end
# 動作確認用コード
p solve(INPUT1)
p solve(INPUT1) == OUTPUT1
puts solve(INPUT1)
# > "1 2\n"
# > true
# > 1 2
標準入力で動作を確認する
確認用コード削除、標準入力（キーボード入力や paiza の提出前動作確認）からのデータ受け取りに変更し、動作確認をしたら提出します。
※ 手動入力の場合 STDIN.read の 入力終了は Ctrl+D 又は Ctrl+Z
解答コード
def solve(input_lines)
# 入力データを空白文字列（改行と半角スペース）で分割しそれぞれを整数に変換
# 先頭から n: ログの日数, k: キャンペーン日数, 以降を visitor_count に代入する
n, k, *visitor_count = input_lines.split.map(&:to_i)
# 1日目 (index: 0) の計算結果を最大として初期化
section_count = visitor_count[..k - 1].sum
campaign = { "candidate" => 1, "index" => 0, "max" => section_count }
# 2日目 (index: 1) から n-k+1 日目（index: n-k）までカウントアップする
(1..n - k).each do |index|
# 計算範囲から外れる日の訪問者数を引く
section_count -= visitor_count[index - 1]
# 計算範囲に追加される日の訪問者数を足す
section_count += visitor_count[index + k - 1]
# campaign の更新をチェックする
if section_count > campaign["max"]
# 【最大を更新した場合】
# candidate: 候補を 1 で初期化
# index: インデックス, max: 最大来客数 を上書きする
campaign["candidate"] = 1
campaign["index"] = index
campaign["max"] = section_count
elsif section_count == campaign["max"]
# 【最大と同じだった場合】
# candidate: 候補を +1 する
campaign["candidate"] += 1
end
end
# 候補数と最初の候補日を半角スペースで区切り末尾に改行を入れる
"#{campaign["candidate"]} #{campaign["index"] + 1}\n"
end
puts solve(STDIN.read)
今回のまとめ
Aランク問題からは答えが合っていてもタイムオーバーでNG判定になることがあります。
今回の場合、ループ内で sum メソッドを使うとタイムオーバーになってしまいます。ループ内で sum メソッドを使うと、 (n - k + 1) 掛ける k 回の計算が発生するためです。
計算回数が一番多くなる条件で比べてみると…
- sum有の計算回数 = (n - k + 1) k --> (300,000 - 150,000 + 1) 150000 = 22,500,150,000 回
- sum無の計算回数 = k + (n - k) 3 --> 150,000 + (300,000 - 150,000) 3 = 600,000 回
ループ内で sum メソッドを使わない様に工夫すると、同じ解を求めているのに計算回数が約37,500分の1になる！
ちなみに、競技プログラミングでは計算量が 10の8乗回あたりからタイムオーバーになることが多いようです。ざっくりで良いので計算量を把握しておけば提出前に「タイムオーバーのケースがあるかも？」と気づくことができます。
A級以降は計算量も重要になってきますので、アルゴリズムも学習しておくと満点が取り易くなると思います！
