※スキルチェック問題ではありません。
規約により公式の解答コードそのままはよろしくないので、
オリジナルのコードにしています。
詳しくはコチラ
なるべくわかりやすい解説を付けました。
1:累積和の計算 (paizaランク C 相当)
数列 A についての情報が与えられるので、 1 ~ N の各 i について、和 S_i = A_1 + … + A_i を求めてください。
- 入力される値
N A_1 A_2 ... A_N - ・ 1 行目には、数列 A の要素数 N が与えられます。
・ 2 行目には、数列 A の各要素 A_1, A_2 … A_N が与えられます。入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。
- 期待する出力
- N 行の出力
・S_i(1 ≦ i ≦ N) を出力してください。
S_1 ... S_N
- 条件
すべてのテストケースにおいて、以下の条件をみたします。 ・ 1 ≦ N ≦ 10 ^ 5 ・ -100 ≦ A_i ≦ 100
- 入力例1
10 0 1 2 3 4 5 6 7 8 9
- 出力例1
0 1 3 6 10 15 21 28 36 45
- 入力例2
1 100
- 出力例2
100
解答と解説
1：総当り法(良くない方法パフォーマンスが良くない)
計算量がO(N²)となってしまい。めちゃくちゃ時間がかかってしまいます。
#1行目の入力値(数値)を変数に代入する
n = gets.to_i
#2行目の半角スペース刻みの入力値(数値)を変数に多重代入する
m = gets.split.map(&:to_i)
#n回繰り返す
n.times do |i|
#mの配列の0(初めから)からmまでの範囲を足したものを出力する
puts m[0..i].sum
end
計算量がO(N²)となってしまい。↑のようにテスト4でめちゃくちゃ時間がかかってしまいます。
2：別解 いい方法(パフォーマンスが良い)
1:変数xを予め用意して(変数名はわかりやすいものなら何でもOKです)0で初期化します
2:変数xに現在の値m[i]を加算して出力します。
#1行目の入力値(数値)を変数に代入する
n = gets.to_i
#2行目の半角スペース刻みの入力値(数値)を変数に多重代入する
m = gets.split.map(&:to_i)
x = 0
#n回繰り返す
n.times do |i|
#xに加算して現在の値m[i]を加算して出力する。
puts x += m[i]
end
計算量がO(N)になったことでテスト4が劇的に速くなりました！
↑のコードを短くすると
n = gets.to_i
m = gets.split.map(&:to_i)
x = 0
n.times { |i| puts x += m[i] }なぜ解答1は実行時間が遅いのか？(入力例１で解説)
解答１の場合このような毎回0から加算していく計算をするので計算数が増えてしまいます。
０ 計算回数0回 0を出力
０＋１＝１ 計算回数1回 1を出力
０＋１＋２＝３ 計算回数2回 3を出力
０＋１＋２＋３＝６ 計算回数3回 6を出力
０＋１＋２＋３＋４＝１０ 計算回数4回 10を出力
０＋１＋２＋３＋４＋５＝１５ 計算回数5回 15を出力
０＋１＋２＋３＋４＋５＋６＝２１ 計算回数6回 21を出力
０＋１＋２＋３＋４＋５＋６＋７＝２８ 計算回数7回 28を出力
０＋１＋２＋３＋４＋５＋６＋７＋８＝３６ 計算回数8回 36を出力
０＋１＋２＋３＋４＋５＋６＋７＋８＋９＝４５ 計算回数9回 45を出力nが10５付近になると膨大な計算数になってしまいます
なぜ解答2で実行時間が速くなるのか？
結論：変数xに加算していき、加算したあとの変数xを出力することで計算数を減らせたので速くなりました。
私達人間が一般的に頭の中で計算して累積和を出す計算方法を使う。
０ 計算回数０回
０＋１＝１ 計算回数１回
１＋２＝３ 計算回数１回
３＋３＝６ 計算回数１回
６＋４＝１０ 計算回数１回
１０＋５＝１５ 計算回数１回
１５＋６＝２１ 計算回数１回
２１＋７＝２８ 計算回数１回
２８＋８＝３６ 計算回数１回
３６＋９＝４５ 計算回数１回というように
これまでに足した数(例：45)と今計算したい数字(例：10)を加算して答えを出します。
解答2はこれまでに足した数xに今計算したい数字m[i]を足して、加算したあとに出力しているので計算数を減らすことができたので実行時間を早くすることができました！