AtCoder ABC127-D 実行時間を短縮したい

Question

前提・実現したいこと

ABC127-D
AtCoderのABC-D問題です。
他の方が書かれたコードや解説を参考にコードを修正しましたが、
7つ目のテスト項目においてTLEになってしまいます。
実行時間を短縮するために、下記のコードで修正できる箇所はありますでしょうか。

該当のソースコード

N,M=gets.chomp.split.map(&:to_i)
A=gets.chomp.split.map(&:to_i)
c=M.times.map { gets.split.map(&:to_i) }
c.sort_by!{|i,j| j }.reverse!
A.sort!

M.times do |i|
  next if A[0]>c[i][1]
  c[i][0].times do |j|
    break if A[0]>c[i][1]
    A.shift()
    A.push(c[i][1])
  end
end
puts A.inject(:+)

修正したコード

N,M=gets.chomp.split.map(&:to_i)
A=gets.chomp.split.map(&:to_i)
c=M.times.map { gets.split.map(&:to_i) }
c.sort_by!{|i,j| j }.reverse!
A.sort!
sum=0
M.times do |i|
  break if A[0]>c[i][1]
  b = 0
  c[i][0].times do |j|
    break if A[j]>c[i][1]
    b += 1
  end
  A.shift(b)
  sum += c[i][1]*b
end
puts (A.inject(:+)+sum)

修正したコード2

N,M=gets.chomp.split.map(&:to_i)
A=gets.chomp.split.map(&:to_i)
c=M.times.map { gets.split.map(&:to_i) }
c.sort_by!{|i,j| j }.reverse!
A.sort!
sum=0
M.times do |i|
  break if A.empty? || A[0]>c[i][1]
  b = 0
  c[i][0].times do |j|
    break if A[j]>c[i][1]
    b += 1
  end
  A.shift(b)
  sum += c[i][1]*b
end
if A.empty? then
  puts sum
else
  puts (A.inject(:+)+sum)
end

Answer 1

Array#shiftを何度も行っているのが気になります。

c[i][0].times do |j|
break if A[0]>c[i][1]
A.shift()
A.push(c[i][1])
end

を

b = 0
c[i][0].times do |j|
  break if A[j]>c[i][1]
  b += 1
end
A.shift(b)
A.push(*([c[i][1]]*b))

---

さらに、Array#bsearch_indexを用いる事でAが巨大な配列だった場合に高速化できる可能性がありますが
Nがたかだか10万なので、Aがソートされた状態なのを維持する手間に見合うかは微妙です。

Comments

[asm]

ついでに
> next if A[0]>c[i][1]
break if A[0]>c[i][1]
でいいですね

[amatsukixprog]

返信遅くなりまして申し訳ありません。

複数点、指摘していただき、ありがとうございます。
配列の掛け算ができることを初めて知りました。

修正し、テストいたしましたが同じところで、
TLEとなってしまいました。
他にも修正できる箇所はありますでしょうか。

[asm]

cを降順ソートしているので1度交換した数値を更に交換する事はないです。
よって、交換済み・交換対象ではない数値を隔離する事でshift/pushによってコピーされる配列を小さくできます。
もっといえば、交換後の数値を配列に保存する必要はなく、交換後の数値の総和だけ持っていれば計算可能です。

[amatsukixprog]

ありがとうございます！
コードを修正しましたが、次はREが複数発生してしまいました。。。
よろしければご確認いただけないでしょうか。

修正したコード　を追記致しました。

[asm]

> break if A[0]>c[i][1]

Aが空配列になるパターンを考慮していないようです。

break if A.empty? || A[0]>c[i][1]

ですね

[amatsukixprog]

ありがとうございます。
指摘していただいた部分と最後の出力の部分も考慮できていなかったため修正いたしましたが、
REが１つだけ残っていました。
他に問題点はありますでしょうか。。。

修正したコード2を追記致しました

[asm]

出力部分については
puts (A.inject(:+)||0)+sum
でよかったりしますね。
他のエラーはちょっと見つかりませんね・・・　なんだろ

[amatsukixprog]

||で左から順に判定してくれるんですね。初めて知りました。。。
色々書き方を知ることができてよかったです。

教えてくださりありがとうございました。
また自力で探してみたいと思います。