paiza プログラミング

[Ruby]paiza スキルチェック過去問題セット 日別訪問者数の最大平均区間 (paizaランク B 相当)の解説

paiza解説 訪問者数の最大平均

こんにちは!じゃいごテックのあつしです。

今回はpaizaレベルアップ問題集から日別訪問者数の最大平均区間という問題を解説していきたいと思います。こちらは過去にスキルチェックで実際に出題されていた問題らしいです!

難易度は 1630±10 で、B級としては割と簡単な問題だと思います。

日別訪問者数の最大平均区間 (paizaランク B 相当)を解いてみる

※ paiza レベルアップ問題集 スキルチェック過去問題セットより

問題

あなたは、とあるウェブサイトを管理していました。
ある連続したk日間、このウェブサイトでキャンペーンを行ったのですが、いつからいつまでの期間に行ったかを忘れてしまいました。

幸い、ウェブサイトを運営していた全n日分のアクセスログが残っており、1日ごとの訪問者数が分かっています。
とりあえず、連続するk日の中で、1日あたりの平均訪問者数が最も多い期間を、キャンペーンを行った期間の候補だと考えることにしました。

n日分の訪問者数のリストとキャンペーンの日数kが入力されるので、キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を出力してください。

入力される値

入力は2行から成ります。

1行目にはnとkが半角スペース区切りで入力されます。

2行目にはn個の整数a_1, a_2, …, a_nが半角スペース区切りで入力されます。a_iはi日目の訪問者数を表します。

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

期待する出力

キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を、この順で半角スペース区切りで1行で出力してください。

条件

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

  • 1≦n≦1,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
攻略ポイント

ポイント

問題を解く流れ
入出力データを準備する

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。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)

  # キャンペーン候補を初期化
  campaign = { "candidate" => -1, "index" => -1, "max" => -1 }

  # 0 から n - k までカウントアップする
  (0..n - k).each do |index|
    # visitor_count[idx] から k 日分の来客者数を計算する
    section_count = visitor_count[index..index + k - 1].sum

    # 【動作確認用コード】
    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
  campaign
end

p solve(INPUT1)
# > ******************************
# > キャンペーン候補の情報: {"candidate"=>-1, "index"=>-1, "max"=>-1}
# > 今回の範囲情報: "index"=>0, "max"=>6 
# > 区間最大を更新しました!
# > ******************************
# > キャンペーン候補の情報: {"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}
入出力データ(変数)で動作を確認する

最後に出力されたハッシュがキャンペーン候補の情報ですので、確認用コードをコメントアウトし、 指定された出力形式を返すように修正します。

def solve(input_lines)
  # 入力データを空白文字列(改行と半角スペース)で分割しそれぞれを整数に変換
  # 先頭から n: ログの日数, k: キャンペーン日数, 以降を visitor_count に代入する
  n, k, *visitor_count = input_lines.split.map(&:to_i)

  # キャンペーン候補を初期化
  campaign = { "candidate" => -1, "index" => -1, "max" => -1 }

  # 0 から n - k までカウントアップする
  (0..n - k).each do |index|
    # visitor_count[idx] から k 日分の来客者数を計算する
    section_count = visitor_count[index..index + k - 1].sum

    # 【動作確認用コード】
    # 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)

  # キャンペーン候補を初期化
  campaign = { "candidate" => -1, "index" => -1, "max" => -1 }

  # 0 から n - k までカウントアップする
  (0..n - k).each do |index|
    # visitor_count[idx] から k 日分の来客者数を計算する
    section_count = visitor_count[index..index + k - 1].sum

    # 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)

今回のまとめ

繰り返し処理の初回で必ず更新されるデータでキャンペーン情報を初期化し、続く繰り返し処理でキャンペーン候補を条件に合わせて更新することによって問題を解きました。

この問題には続きがあります。
「日別訪問者数の最大平均区間(large)(A級)」にも挑戦してみましょう!



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


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






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







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







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







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


-paiza, プログラミング
-,

© 2024 じゃいごテック