エンジニアでもソースコード
先日のエンジニアでも恋がしたい(オンラインハッカソン)のソースコードとその解説を書きます。
ソースコード
第一問目
在庫数の合計を出力する問題。
問題をそのまま実装すればOK。
1行目には対象の個数が入っているので、
その回数分ループを回して入力値を計算して出力します。
input_lines = gets result = 0 (0..input_lines.to_i - 1).each do |i| result += gets.to_i end puts result
第二問目
最低限必要な在庫を補充するための金額を計算する問題。
在庫が足りなければ足りない分補充する金額を計算して、その合計を出力すればOK。
input_lines = gets result = 0 (0..input_lines.to_i - 1).each do |i| # 入力値取得 lines = gets.split("\s") # 必要な在庫 targetStock = lines[0].to_i # 今ある在庫 currentStock = lines[1].to_i # 値段 productPrice = lines[2].to_i # 必要経費 result += (targetStock - currentStock > 0 ? (targetStock - currentStock) * productPrice : 0) end puts result
第三問目
区間内の合計の最大値を求める問題。
AOJやってたときに似たような問題やったなーとか思いつつ解きました。
この問題は何も考えずに解くと計算量がO(n^2)になってタイムアウトします。
input_lines = gets lines = input_lines.split("\s") # ダメージ有効範囲 damageScope = lines[0].to_i # 最大範囲 maxLength = lines[1].to_i inputDamage = [] (0..maxLength - 1).each do |i| inputDamage << gets.to_i end # 最大ダメージ maxDamage = 0 # 現在のダメージ currentDamage = 0 if maxLength == damageScope # 範囲が同じ場合は全ての合計 (0..inputDamage.length - 1).each do |i| maxDamage += inputDamage[i] end else (0..maxLength - damageScope).each do |i| currentDamage = 0 # ダメージ計算 (i..damageScope + i - 1).each do |j| currentDamage += inputDamage[j] end # max値取得 if currentDamage > maxDamage maxDamage = currentDamage end end end puts maxDamage
しかし、累積和というアルゴリズムを使用することで、計算量をがっつりさげられます。(O(n^2) -> O(nm))
input_lines = gets lines = input_lines.split("\s") # ダメージ有効範囲 damageScope = lines[0].to_i # 最大範囲 maxLength = lines[1].to_i # ダメージ取得 inputDamage = [] (0..maxLength - 1).each do |i| inputDamage << gets.to_i end # 最大ダメージ maxDamage = 0 # 現在のダメージ currentDamage = 0 if maxLength == damageScope # 範囲が同じ場合は全ての合計 (0..inputDamage.length - 1).each do |i| maxDamage += inputDamage[i] end else # 累積和の実装 inputDamageSum = [] # 0だけ計算する damageSum = 0 (0..damageScope - 1).each do |i| damageSum += inputDamage[i] end inputDamageSum << damageSum # 数列の作成 current = 0 # 数列つくって読み込めばO(nm)でできる (damageScope..maxLength - 1).each do |i| inputDamageSum << inputDamageSum[current] - inputDamage[current] + inputDamage[i] current += 1 end # 配列の最大値取得 maxDamage = inputDamageSum.max end puts maxDamage
累積和は連続した数値を足していってできる配列のことです。
例えば、以下のような配列があるとします。
hoge = [1,2,3,4,5,6]
この配列の累積和は
fuga = [1,3,6,10,15,21]
となります。(1, 1+2, 1+2+3, 1+2+3+4,....)
で、この累積和を使うと区間の合計を簡単に出すことができます。
例えば、3～5番目の合計を求めたい場合
5番目の合計数値から2番目の数値を引いた値がその合計値になります。(3 + 4 + 5 = 12 => 15 - 3 = 12)
連続した値の数列をa、累積和の数列をbとすると、下記のような式になります。
a[l] + a[l+1] + a[l+2] + ... + a[r] = b[r] - b[l - 1]
result = b[r] - b[l - 1]
この考え方を用いたプログラムを書くと上記のようになります。
おわりに
累積和とかちゃんと書いてますけど実はこんな名前あるとは知らずに解いていたり・・・
昔似たようなプログラム書いたなーってことで調べてたらちゃんと名前があってそれできれいにした感じです。
でも多分他にも有効なアルゴリズムとかあるんじゃないかなと予想しているので、機会があればみなさんも解いてみてはいかがでしょう！
