この記事では
プログラミング学習サービスpaizaラーニングの
スキルチェックレベルアップ問題集をわかりやすく解説します！
プログラミング言語はpythonです。
今回はAランク相当の以下の問題を解説します。
他のレベルアップ問題集の解答と解説もしているので
ぜひご参考ください！
またpaizaの各ランクの攻略法は
こちらで詳しく紹介しているので、ぜひご参考ください！
この問題を解くための4つのポイント
まずは「この問題を解くためのポイント」をご説明します。
問題はこちらからご確認ください。
日別訪問者数の最大平均区間(large) (paizaランク A 相当)
この問題を解くためのポイントは以下の4つです。
- 各期間の訪問者数を計算する回数を考える
- 訪問者数が最大の期間を効率的に数える
- 効率的に訪問者数の合計を計算
- 期間の開始日も記録
各期間の訪問者数を計算する回数を考える
まずは「各期間の訪問者数を計算する回数を考える」です。
今回の問題では
- 全日数
- キャンペーンの日数
- 1日ごとの訪問者数
の3つが入力され、キャンペーンの日数と1日ごと訪問者数から
- キャンペーンの候補数
- キャンペーン候補の最も早い開始日
の2つを結果として出力します。
そのため全日数をキャンペーンの日数で分け
for文を使って各期間の訪問者数を計算しなければなりません。
そこで必要になるのが処理を繰り返す回数です。
例えば「全日数が5日、キャンペーンの日数が3日」の場合は
- 1日目～3日目
- 2日目～4日目
- 3日目～5日目
の3つの期間の訪問者数を計算する必要があります。
そして処理を繰り返す日数は
(全日数) - (キャンペーンの日数) + 1
で求められます！
"""
totalは全日数
periodはキャンペーンの日数
"""
# "(全日数)-(キャンペーンの日数)+1"回処理を繰り返す
for i in range(total - period + 1):
# 各期間に対する処理を書くfor文と四則演算についてはこちらをご参考ください！
訪問者数が最大の期間を数える
次は「訪問者数が最大の期間を数える」です。
今回の問題では「各期間の平均訪問者数が最大の区間」を
キャンペーン期間を候補として考えます。
各期間の訪問者数のリストを作成します。
# "(全日数)-(キャンペーンの日数)+1"回処理を繰り返す
for i in range(total - period + 1):
# 各期間に訪問者数のリスト
part_visitors = visitors[i:i+period]リストのスライスについては、こちらをご参考ください！
次に平均訪問者数が最大であれば合計訪問者数も最大なので
sum関数を使って合計訪問者数を計算します。
# "(全日数)-(キャンペーンの日数)+1"回処理を繰り返す
for i in range(total - period + 1):
# 各期間に訪問者数のリスト
part_visitors = visitors[i:i+period]
# 各期間の合計訪問者数
sum_visit = sum(part_visitors)また新たにリストを作らず1行で書くとよりシンプルです。
# "(全日数)-(キャンペーンの日数)+1"回処理を繰り返す
for i in range(total - period + 1):
# 各期間の合計訪問者数
sum_visit = sum(visitors[i:i+period])次に最大の合計訪問者数とその期間の数を記録する変数を用意します。
# 最大の合計訪問者数
max_visit = 0
# 合計訪問者数が最大の期間の数
count = 0
# "(全日数)-(キャンペーンの日数)+1"回処理を繰り返す
for i in range(total - period + 1):
# 各期間の合計訪問者数
sum_visit = sum(visitors[i:i+period])次にif elif文を使って
- 各期間の合計訪問者数がこれまでの最大より大きいか
- 各期間の合計訪問者数がこれまでの最大と同じか
の2つの条件で条件分岐を行います。
# 最大の合計訪問者数
max_visit = 0
# 合計訪問者数が最大の期間の数
count = 0
# "(全日数)-(キャンペーンの日数)+1"回処理を繰り返す
for i in range(total - period + 1):
# 各期間の合計訪問者数
sum_visit = sum(visitors[i:i+period])
# これまでの最大合計訪問者数より大きい場合
if sum_visit > max_visit:
# これまでの最大合計訪問者数と同じ場合
elif sum_visit == max_visit:if文についてはこちらをご参考ください！
そしてそれぞれの条件を満たすとき
最大の合計訪問者数とキャンペーン期間の候補数に以下の処理を行います。
- 各期間の合計訪問者数がこれまでの最大より大きい場合
- 最大の合計訪問者数の値を更新
- キャンペーン期間の候補数を
1にする
- 各期間の合計訪問者数がこれまでの最大と同じ場合
- キャンペーン期間の候補数を
1増やす
- キャンペーン期間の候補数を
# 最大の合計訪問者数
max_visit = 0
# キャンペーン期間の候補数
count = 0
# "(全日数)-(キャンペーンの日数)+1"回処理を繰り返す
for i in range(total - period + 1):
# 各期間の合計訪問者数
sum_visit = sum(visitors[i:i+period])
# これまでの最大合計訪問者数より大きい場合
if sum_visit > max_visit:
# 最大の合計訪問者数を更新
max_visit = sum_visit
# キャンペーン期間の候補数をリセット
count = 1
# これまでの最大合計訪問者数と同じ場合
elif sum_visit == max_visit:
# キャンペーン期間の候補数を1増やす
count += 1四則演算についてはこちらをご参考ください！
効率的に訪問者数の合計を計算する
次は「効率的に訪問者数の合計を計算する」です。
上記では各期間の合計訪問者数をsum関数を使って計算しました。
しかし今回の問題の全日数の最大値が300,000であるため
キャンペーンの日数が長ければ長いほど、計算に時間がかかってしまいます。
そのため、「 1つ前の期間の合計を使う 」方法で効率的に合計を計算します。
例えば、「全日数が5日、キャンペーンの日数が3日」の場合は
- 1日目~3日目の合計を計算する
- 2日目~4日目の合計は、1日目~3日目の合計から1日目の数を引き4日目の数を足す
- 3日目~5日目の合計は、2日目~4日目の合計から2日目の数を引き5日目の数を足す
のように1つ前の期間の合計を使って計算していきます。
まず最初の期間の合計をsum関数で計算して、変数に代入します。
# 最初の期間の合計訪問者数
sum_visit = sum(visitors[:period])また最初の期間が最大の可能性もあるので
最大の合計訪問者数に代入し、候補数には1を代入します。
# 最初の期間の合計訪問者数
sum_visit = sum(visitors[:period])
# 最大の合計訪問者数
max_visit = sum_visit
# 合計訪問者数が最大の期間の数
count = 1次に最初の期間がすでに計算されているので、for文の範囲を1ずらします。
# "(全日数)-(キャンペーンの日数)"回処理を繰り返す
for i in range(1,total - period + 1):
# 各期間に対する処理を書くfor文については、こちらをご参考ください！
そして合計訪問者数の計算を前の期間の合計を使った方法に変更します！
# "(全日数)-(キャンペーンの日数)"回処理を繰り返す
for i in range(1,total - period + 1):
# 各期間の合計訪問者数を効率的に計算
sum_visit = sum_visit - visitors[i-1] + visitors[i+period-1]リストについては、こちらをご参考ください！
期間の開始日も記録する
最後は「期間の開始日も記録する」です。
今回の問題では最終的な結果として
キャンペーンの候補数だけでなく、
最も早い開始日も出力しなければなりません。
そのために開始日を記録する変数を用意します。
# キャンペーン候補の開始日
date = 1そして各期間の合計訪問者数が更新された場合に
for文のインデックスを使って開始日も更新します。
# 最初の期間の合計訪問者数
sum_visit = sum(visitors[:period])
# 最大の合計訪問者数
max_visit = sum_visit
# 合計訪問者数が最大の期間の数
count = 1
# キャンペーンの開始日
date = 1
# "(全日数)-(キャンペーンの日数)"回処理を繰り返す
for i in range(1,total - period + 1):
# 各期間の合計訪問者数を効率的に計算
sum_visit = sum_visit - visitors[i-1] + visitors[i+period-1]
# これまでの最大合計訪問者数より大きい場合
if sum_visit > max_visit:
# 最大の合計訪問者数を更新
max_visit = sum_visit
# キャンペーン期間の候補数をリセット
count = 1
# キャンペーンの開始日を更新
date = i + 1
# これまでの最大合計訪問者数と同じ場合
elif sum_visit == max_visit:
# キャンペーン期間の候補数を1増やす
count += 1ただしfor文のインデックスは0から始まりキャンペーンの開始日と1ずれるため
インデックスに1を加えることに注意しましょう！
for文については、こちらをご参考ください！
日別訪問者数の最大平均区間(large)(paizaランク A 相当)の解答
ではここまで紹介したポイントを使って、問題を解いていきます。
入力を受け取り、リストや変数を準備する
今回の問題では
- 1行目で 半角スペース区切りで全日数とキャンペーンの日数
- 2行目で1日ごとの訪問者数
が入力されます。
そのため内包表記を使って
- 全日数とキャンペーンの日数は変数に代入
- 1日ごとの訪問者数はリストに代入
のように入力を受け取ります。
# 全日数とキャンペーンの日数の入力を受け取る
total, period = [int(x) for x in input().split() ]
# 1日ごとの訪問者数の入力を受け取る
visitors = [int(x) for x in input().split()]標準入力や内包表記については、こちらをご参考ください！
キャンペーンの候補数と最も早い開始日を求める
次は「キャンペーンの候補数と最も早い開始日を求める」です。
全日数をキャンペーンの日数の期間に分けて
各期間の合計訪問者数を計算します。
# "(全日数)-(キャンペーンの日数)"回処理を繰り返す
for i in range(1,total - period + 1):
# 各期間の合計訪問者数を効率的に計算
sum_visit = sum_visit - visitors[i-1] + visitors[i+period-1]そしてif elif文で条件分岐を行い
キャンペーンの候補数と最も早い開始日を求めます。
# 最初の期間の合計訪問者数
total = sum(visitors[:period])
# 最大の合計訪問者数
max_visit = sum_visit
# 合計訪問者数が最大の期間の数
count = 1
# キャンペーンの開始日
date = 1
# "(全日数)-(キャンペーンの日数)"回処理を繰り返す
for i in range(1,total - period + 1):
# 各期間の合計訪問者数を効率的に計算
sum_visit = sum_visit - visitors[i-1] + visitors[i+period-1]
# これまでの最大合計訪問者数より大きい場合
if sum_visit > max_visit:
# 最大の合計訪問者数を更新
max_visit = sum_visit
# キャンペーン期間の候補数をリセット
count = 1
# キャンペーンの開始日を更新
date = i + 1
# これまでの最大合計訪問者数と同じ場合
elif sum_visit == max_visit:
# キャンペーン期間の候補数を1増やす
count += 1if文については、こちらをご参考ください！
結果を出力
最後は「結果を出力」です。
今回の問題では最終的な結果として
キャンペーンの候補数と最も早い開始日を半角スペース区切りで出力します。
# キャンペーンの候補数と開始日を出力
print(count, date)出力についてはこちらをご参考ください！
解答
まとめると解答は以下です。
# 全日数とキャンペーンの日数の入力を受け取る
total, period = [int(x) for x in input().split() ]
# 1日ごとの訪問者数の入力を受け取る
visitors = [int(x) for x in input().split()]
# 最初の期間の合計訪問者数
sum_visit = sum(visitors[:period])
# 最大の合計訪問者数
max_visit = sum_visit
# 合計訪問者数が最大の期間の数
count = 1
# キャンペーンの開始日
date = 1
# "(全日数)-(キャンペーンの日数)"回処理を繰り返す
for i in range(1,total - period + 1):
# 各期間の合計訪問者数を効率的に計算
sum_visit = sum_visit - visitors[i-1] + visitors[i+period-1]
# これまでの最大合計訪問者数より大きい場合
if sum_visit > max_visit:
# 最大の合計訪問者数を更新
max_visit = sum_visit
# キャンペーン期間の候補数をリセット
count = 1
# キャンペーンの開始日を更新
date = i + 1
# これまでの最大合計訪問者数と同じ場合
elif sum_visit == max_visit:
# キャンペーン期間の候補数を1増やす
count += 1
# キャンペーンの候補数と開始日を出力
print(count, date)ぜひご参考ください！
まとめ
今回はpaizaのレベルアップ問題集の中で
- 日別訪問者数の最大平均区間(large)： (paizaランク A 相当)
の解答と解説を紹介しました。
Aランクの問題になると、例え正しい出力が得られたとしても
「ランタイムエラー」で減点されることが増えてくるかと思います。
アルゴリズムを考える時はもちろん提出前にも
無駄な処理がないかどうかをちゃんと確認しましょう！
また他のレベルアップ問題集の問題についての解説も、ぜひご参考ください！
