情報自炊

情報を血肉にしたい

【Ruby】AtCoder Beginner Contest 130のD問題振り返り

問題

atcoder.jp

答え

n, k = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i)

count = 0
j = 0
sum = 0
# iを一つずつ右に進めるようなループ
(0..n-1).each do |i|
  # jを一つずつ右進めるようなループ
  while sum < k && j < n do
    sum += a_arr[j]
    j += 1 # jは進むだけで後戻りしない
  end
  # jを最後まで進めても条件を満たさない場合,
  # 以降iを進めてもsumが小さくなるだけなのでbreak
  break if sum < k
  # a_arr[i..j].sum >= k ということは
  # a_arr[i..j+1].sum, a_arr[i..j+2].sum, ... もk以上なので
  # まとめてカウントアップ
  count += n - j + 1
  sum -= a_arr[i]
end

puts count

jを0から(あるいはiから)始まるループを作ってしまうと最悪実行時間がO(n)になってしまうので、全体でO(n^2)になってしまう。jを戻さないのがポイント。

jを戻さなくて良い理由はよく考えると分かる。

a_arr[i..j]で初めてk以上になったとき、次のループはa_arr[(i+1)..j]から始まる。jを好きなだけ戻した部分列は正の整数mを用いてa_arr[(i+1)..(j-m)]のように表すことができる。

このとき a_arr[(i+1)..(j-m)] >= k が成り立つとすると、a_arr[(i+1)..(j-m)]a_arr[i..(j-m)]の部分列なのでa_arr[i..(j-m)] > a_arr[(i+1)..(j-m)] >= k が成り立つ。これは「a_arr[i..j]で初めてk以上になった」という点と矛盾する。だから常にa_arr[(i+1)..(j-m)] < kとなるのでjを戻すのは考えなくて良い。

このアルゴリズムはしゃくとり法と呼ばれるもので私は初めて知った。

デバッグコードあり

n, k = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i)

count = 0
j = 0
sum = 0
(0..n-1).each do |i|
  puts "-------- i=#{i} j=#{j}"
  while sum < k && j < n do
    print "add #{a_arr[j]} (j=#{j}). sum: #{sum}->"
    sum += a_arr[j]
    puts "#{sum}"
    j += 1
  end
  puts "after while. sum=#{sum} j=#{j}"
  break if sum < k
  print "add #{n} - #{j} + 1. count: #{count}->"
  count += n - j + 1
  puts "#{count}"
  sum -= a_arr[i]
  puts "diff #{a_arr[i]} (i=#{i}). sum=#{sum}"
end

puts count

せっかくなのでデバッグコードを仕込みまくって処理を追った。こうするとインデックスの動きがよく見えて分かりやすい。

入力例1

4 10
6 1 2 7
-------- i=0 j=0
add 6 (j=0). sum: 0->6
add 1 (j=1). sum: 6->7
add 2 (j=2). sum: 7->9
add 7 (j=3). sum: 9->16
after while. sum=16 j=4
add 4 - 4 + 1. count: 0->1
diff 6 (i=0). sum=10
-------- i=1 j=4
after while. sum=10 j=4
add 4 - 4 + 1. count: 1->2
diff 1 (i=1). sum=9
-------- i=2 j=4
after while. sum=9 j=4
2

入力例2

3 5
3 3 3
-------- i=0 j=0
add 3 (j=0). sum: 0->3
add 3 (j=1). sum: 3->6
after while. sum=6 j=2
add 3 - 2 + 1. count: 0->2
diff 3 (i=0). sum=3
-------- i=1 j=2
add 3 (j=2). sum: 3->6
after while. sum=6 j=3
add 3 - 3 + 1. count: 2->3
diff 3 (i=1). sum=3
-------- i=2 j=3
after while. sum=3 j=3
3

入力例3

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352
-------- i=0 j=0
add 103 (j=0). sum: 0->103
add 35322 (j=1). sum: 103->35425
add 232 (j=2). sum: 35425->35657
add 342 (j=3). sum: 35657->35999
add 21099 (j=4). sum: 35999->57098
after while. sum=57098 j=5
add 10 - 5 + 1. count: 0->6
diff 103 (i=0). sum=56995
-------- i=1 j=5
after while. sum=56995 j=5
add 10 - 5 + 1. count: 6->12
diff 35322 (i=1). sum=21673
-------- i=2 j=5
add 90000 (j=5). sum: 21673->111673
after while. sum=111673 j=6
add 10 - 6 + 1. count: 12->17
diff 232 (i=2). sum=111441
-------- i=3 j=6
after while. sum=111441 j=6
add 10 - 6 + 1. count: 17->22
diff 342 (i=3). sum=111099
-------- i=4 j=6
after while. sum=111099 j=6
add 10 - 6 + 1. count: 22->27
diff 21099 (i=4). sum=90000
-------- i=5 j=6
after while. sum=90000 j=6
add 10 - 6 + 1. count: 27->32
diff 90000 (i=5). sum=0
-------- i=6 j=6
add 18843 (j=6). sum: 0->18843
add 9010 (j=7). sum: 18843->27853
add 35221 (j=8). sum: 27853->63074
after while. sum=63074 j=9
add 10 - 9 + 1. count: 32->34
diff 18843 (i=6). sum=44231
-------- i=7 j=9
add 19352 (j=9). sum: 44231->63583
after while. sum=63583 j=10
add 10 - 10 + 1. count: 34->35
diff 9010 (i=7). sum=54573
-------- i=8 j=10
after while. sum=54573 j=10
add 10 - 10 + 1. count: 35->36
diff 35221 (i=8). sum=19352
-------- i=9 j=10
after while. sum=19352 j=10
36

【Ruby】AtCoder Beginner Contest 130のA〜C問題振り返り

結果はA, B, CがAC。内CはWAを2回。 f:id:hoshitostar:20190616223828p:plain

間違ってAで提出しているところを見るとかなり焦っていた様子が見て取れる。Cを解くまでに43分かかっており、今回はCで大失敗したと言えるだろう。

一応D問題も取り組んでみて、方針は見えていたがプログラミングする時間が無かった…無念。

コンテストページ

atcoder.jp

提出

A

x,a = gets.chomp.split(" ").map(&:to_i)

if x < a then
  puts 0
else
  puts 10
end

B

n,x = gets.chomp.split(" ").map(&:to_i)
l_arr = gets.chomp.split(" ").map(&:to_i)

count = 1

d = 0
l_arr.each do |l|
  d = d + l
  if (d <= x) then
    count += 1
  end
end

puts count

最初のバウンドも数えるため、初期値はcount = 1であることに注意。

C

w, h, x, y = gets.chomp.split(" ").map(&:to_i)

puts w * h / 2.to_f

if x == w/2 && y == h/2 then
  puts "1"
else
  puts "0"
end

上のコードはWA。面積を出すところは合っている。問題はx == w/2 && y == h/2の比較である。これも考え方自体は正解なのだが、問題はw/2h/2の結果が整数(小数部分が切り捨てられる)であるところ。

WAが出てしまい、しばらく長方形の中心以外からも複数線が引けるのか、ノートが長方形だらけになってしまった。

正しくはこう。

w, h, x, y = gets.chomp.split(" ").map(&:to_i)

puts w * h / 2.to_f

if 2 * x == w && 2 * y == h then
  puts "1"
else
  puts "0"
end

D

一応考えだけ載せる。

  • 部分配列の左端と右端のindexをそれぞれ0として初期値を設定
  • 部分配列の左端を固定して右端のindexを右に進めていき、条件を満たすところまで進める
  • 部分配列の右端を固定して左端のindexを右に進めていき、条件を満たさなくなるところまで進める
  • これを繰り返す

たぶんこれでいけるはず…

間違えていました

【Ruby】diverta 2019 Programming Contest 2のA〜C問題振り返り

結果はA, B, CがAC。 f:id:hoshitostar:20190615223822p:plain

500点問題を解けたのは初めて。といってもこの500点はABCでいう400点問題くらいの難しさに感じた。

Cを解いた時点で残り約40分残っていたのでDの問題を眺めていた。金だけなら楽勝だけど銀と銅も絡んでくるから激ムズだなというところで撤退。

コンテストページ

atcoder.jp

提出

A

n,k = gets.chomp.split(" ").map(&:to_i)

if k == 1
  puts 0
else
  puts n - k
end

入力例が無ければk == 1の例外を間違いなく見逃していた。

B

n = gets.chomp.to_i
x_y_arr = n.times.map{gets.chomp.split(" ").map(&:to_i)}

hash = {}
x_y_arr.each_with_index do |(x, y), i|
  x_y_arr.each_with_index do |(x2, y2), i2|
    next if i == i2
    diff_x = x - x2
    diff_y = y - y2
    hash[[diff_x, diff_y]] ||= 0
    hash[[diff_x, diff_y]] += 1
    #hash[[-diff_x, -diff_y]] ||= 0
    #hash[[-diff_x, -diff_y]] += 1
  end
end

if hash.size == 0 then
  puts 1
else
  puts n - hash.values.max
end

全ての組み合わせ(順番も区別する)で、各座標の差ごとに出現回数を集計して一番多いものに関してpqを決めると良い。Nが多くて50なので処理時間的に2重ループの実行が許される。

これもNが1のときが例外となり、これは入力例が無くそのまま引っかかってしまった。なので一回目の提出はRE。REが出たときに詳細を見て、ケースに対して1件だけREだったので何か例外処理があるんだろうなと考えて、入力制約を見直して気がついた。

C

n = gets.chomp.to_i
a_arr = gets.chomp.split(" ").map(&:to_i).sort

neg_num = 0
pos_num = 0
a_arr.each do |a|
  if a < 0 then
    neg_num += 1
  else
    pos_num += 1
  end
end

puts_arr = []
(n-1).times do
  if a_arr.length == 2 then
    puts_arr << "#{a_arr[1]} #{a_arr[0]}"
    puts a_arr[1] - a_arr[0]
    break
  end
  if neg_num > pos_num then
    x = a_arr.pop
    y = a_arr.shift
    puts_arr << "#{x} #{y}"
    a_arr.push(x - y)
  else
    x = a_arr.shift
    y = a_arr.pop
    puts_arr << "#{x} #{y}"
    a_arr.unshift(x - y)
  end
  if x < 0 then
    neg_num -= 1
  else
    pos_num -= 1
  end
  if y < 0 then
    neg_num -= 1
  else
    pos_num -= 1
  end
  if x - y < 0 then
    neg_num += 1
  else
    pos_num += 1
  end
end


puts_arr.each do |str|
  puts str
end

上のコードはAC。一回目に出したコードは大量にWAとTLEが出てしまい少し冷静に考えてから再提出した。

N - 1回処理をしなければならず、Nの入力制約もだいぶ大きいので2重ループはダメなんだろうなと考えた。だから(n-1).timesのループを回せば出力したい結果が揃うんだろうなと思って考えを巡らせた。

こういうときはもちろん簡単な例をひたすら紙と鉛筆で解いていくに限る。

すると最後の操作で「(なるべく)絶対値の大きい正数」-「(なるべく)絶対値の大きい負数」の形に持っていけば良いのだと分かり、そうすると配列の最大値と最小値が鍵になってくるということも予想がついた。

maxとminを求めるのにループの中でsort, max, minの演算をしてはダメだ。これらの演算はコストが高くTLEが出てしまう。だからソートは入力が与えられた最初の1回だけやって、あとは配列の先頭と末尾をそれぞれ最小値と最大値として拾ってきてなんとかする。

「絶対値の大きい正数」を作るには最小値 - 最大値で、「絶対値の大きい負数」を作るには最小値 - 最大値。そして「絶対値の大きい正数」「絶対値の大きい負数」はそれぞれ1個ずつ用意する必要がある。0個とか2個とかはダメ。だから正数の数と負数の数に気をつけながら両者を求めていった。

【Ruby】AtCoder Beginner Contest 129のA〜D問題振り返り

結果はA, B, CがAC。DがTLE。

f:id:hoshitostar:20190609224735p:plain

C問題のREは全部の積を求めてから余りを求めていたから。この手のREは初めてだったので次回から余りを出力する問題では気をつける。

問題一覧

atcoder.jp

提出

A問題

提出日時:2019-06-09 21:01:52

p,q,r=gets.chomp.split(" ").map(&:to_i)

puts [p+q, r+p, q+r].min

A問題にしてはちょっと難しいと思った。

B問題

提出日時:2019-06-09 21:09:14

n=gets.chomp.to_i
w_arr=gets.chomp.split(" ").map(&:to_i)

min = 100000000

(0..(n-1)).each do |t|
  abs = w_arr[0..t].inject(&:+).to_i - w_arr[(t+1)..-1].inject(&:+).to_i
  abs *= -1 if abs < 0
  min = abs if abs < min
end

puts min

ここで時間を食ったのが痛かった。添字と、配列が空だとinjectの戻り値がnilになる考慮が足りずに確認が思った以上にかかった。

C問題

提出日時:2019-06-09 21:35:34

n,m = gets.chomp.split(" ").map(&:to_i)

a_arr = []
m.times do |i|
  a_arr << gets.chomp.to_i
end
a_arr << n+1

fib = [1, 1]
100000.times do |i|
  fib[2+i] = fib[2+(i-1)] + fib[2+(i-2)]
end

arr = []
step = 0
prev = -1
a_arr.each do |a|
  if a - prev == 1 then
    puts 0
    exit
  end
  count = a - step - 1
  #puts count
  if count > 0 then
    arr << fib[count]
  end
  step = a + 1
  prev = a
end

result = 1
arr.each do |a|
  result *= a
  result = result % 1000000007
end

puts result

読みながらだと方針が全然分からなかった。壊れている床までの連続したstep数によって組み合わせが決まって、しかもその組み合わせは前のものに依存しているのかなあくらいの印象。

こういう場合は手を動かして簡単な例から作っていくのが良く、step:1 ,2, 3, ... と実際に数えてみた。1, 2, 3, 5, 8と出てきたのでフィボナッチ数列と予想が付き、1段上りと2段上りがあるからstep(i) = step(i-1) + step(i-2)の形になるのは納得だなあ(証明というよりは感覚)と考えたところで実装。

問題はフィボナッチ数列をどう実装するか。前の結果を利用していくタイプだとかなり難しいなと焦りそうになったが、Nの上限が10の5乗であることからあらかじめ全部求めても問題ないと判断して割とゴリ押し気味に実装。手元での確認で結果が出るまでにワンテンポ遅れるので不安だったがなんとか大丈夫だった。

D問題

提出日時:2019-06-09 22:22:46

何回かTLE出しましたが基本方針は変わらず。

h,w = gets.chomp.split(" ").map(&:to_i)

arr = []
h.times do |i|
  tmp_arr = []
  input = gets.chomp
  (0..(input.length-1)).each do |j|
    tmp_arr << (input[j] == "#")
  end
  tmp_arr << true
  arr << tmp_arr
end

tmp_arr = []
w.times do |i|
  tmp_arr << true
end
tmp_arr << true
arr << tmp_arr

h_pos = []
h_tmp_count = []
w.times do |i|
  h_pos << -1
  h_tmp_count << -1
end

max = 0

(0..(h-1)).each do |i|
  w_pos = -1
  w_tmp_count = -1
  (0..(w-1)).each do |j|
    bool = arr[i][j]
    next if bool


    w_count = 0
    if j < w_pos then
      w_count = w_tmp_count
    else
      ((j+1)..(w)).each do |j2|
        bool_j2 = arr[i][j2]
        if bool_j2 then
          w_pos = j2
          w_tmp_count = w_count
          break
        else
          w_count += 1
        end
      end
    end

    h_count = 0
    if i < h_pos[j]
      h_count = h_tmp_count[j]
    else
      ((i+1)..(h)).each do |i2|
        bool_i2 = arr[i2][j]
        if bool_i2 then
          h_pos[j] = i2
          h_tmp_count[j] = h_count
          break
        else
          h_count += 1
        end
      end
    end

    count = h_count + w_count + 1
    max = count if count > max
  end
end

puts max

これこそは前の結果を利用していくタイプだと思って実装。

4 6
#..#..
.....#
....#.
#.#...

こういう入力があって(0,1)の座標に明かりを設置したとき「右方向に1の明かり + 下方向に3の明かり + 自身」で5マスになるのだが、このとき(0,2)の座標では横方向の明かりの数が、(1,1), (2,1), (3,1)の座標では縦方向の明かりの数が、それぞれ流用できる。この流用していくアルゴリズムでいけるのかなと思ったがダメだった。

そしてここを書いているタイミングで解説が公表されたので読んでみると…

上下左右方向だと…!?

障害物が存在しないときに最悪計算量が O(HW(H + W)) となってしまい、これでは時間内に答えを求めることができません。

これは確かに。私の提出だとi2とj2のためのループでH + Wの時間が発生してしまいO(HW(H + W))となっている。

例えば、L[i][j] の要素は次のように計算できます。

RとDとUはそれぞれi, jとプラス1するかマイナス1するかの違いで求められるってことか。勉強になる。

A, B, C問題の解説もそれぞれ勉強になる。

A問題の3つの和から最大数を引くってのはかなりトリッキー。

B問題はO(N)でも解くことができる。

C問題はフィボナッチ数列を求める過程で、壊れた床をスキップする処理を書けること。

ベストなコードに近づくのは難しいがこれがまた別の形で役に立つと思う。

【Ruby】AtCoder Beginner Contest 128のA〜D問題振り返り

結果はA, B, C, DがAC。昨日と同じ。昨日はD問題を8回目でACという反省点があったが、今回は4回目でACを通すことができた。

f:id:hoshitostar:20190526223543p:plain

TLEを出さなかったのは進歩かも。

問題一覧

https://atcoder.jp/contests/abc128/tasks

提出

A問題

a,p=gets.chomp.split(" ").map(&:to_i)

puts (a * 3 + p) / 2

B問題

n=gets.chomp.to_i
arr = []
n.times do |i|
  s,p=gets.chomp.split(" ")
  arr << [s, p.to_i, i+1]
end

arr.sort_by!{|(s,p,i)| [s, -p]}

arr.each do |(s,p,i)|
  puts i
end

第2ソートまでが指定されている問題だが、rubyのソートは実装が楽なのでこういうとき嬉しい。

C問題

n,m = gets.chomp.split(" ").map(&:to_i)

ks = []
m.times do |i|
  ks << gets.chomp.split(" ").map(&:to_i)
end

p_arr = gets.chomp.split(" ").map(&:to_i)

c = 0
# 1 <= n <= 10
(2 ** n).times do |i|
  bi = (i.to_s(2)).reverse + "0" * 10
  arr = []
  n.times do |j|
    arr[j] = bi[j] == "1" ? true : false
  end

  flag = true
  ks.each_with_index do |kss, l|
    k = kss[0]
    s_arr = kss[1..-1]
    count = 0
    s_arr.each do |s|
      count += 1 if arr[s-1]
    end
    p = p_arr[l]
    if count % 2 != p then
      flag = false
      break
    end
  end
  c += 1 if flag
end

puts c

問題文を読むとかなり複雑そうで実際けっこう考えてしまったのだが、スイッチの個数が10個までなので、スイッチのON, OFFの組み合わせ全部をたどっても問題ないと判断して2の10乗分のループを回した。内側のループもM回しか回らない(そしてMは上限10)ので大丈夫。

全体的にコードが煩雑で強引さが気になる。ループを回したときのindexを2進数変換してフラグ配列に持たせているのだがもう少し簡単に書けそう。

D問題

最初の提出。RE13個。方針は合っていたがバグが多すぎた。

n, k = gets.chomp.split(" ").map(&:to_i)
v_arr = gets.chomp.split(" ").map(&:to_i)

max_value = 0
(0..k).each do |a|
  next if a > v_arr.length
  a_arr = a > 0 ? v_arr[0..(a-1)] : []
  (0..(k - a)).each do |b|
    next if b > v_arr.length - a
    b_arr = b > 0 ? v_arr[(b*(-1))..-1] : []
    arr = (a_arr + b_arr).sort
    cd = k - a - b
    index = arr.index{|x| x < 0}
    if index.nil? then
      value = arr.inject(0){|sum, i| sum + i }
    elsif cd - 1 > index then
      index -= 1 if arr[(index+1)].nil?
      value = arr[(index+1)..-1].inject(0){|sum, i| sum + i }
    else
      value = arr[cd..-1].inject(0){|sum, i| sum + i }
    end
    max_value = value if value > max_value
  end
end

puts max_value

特に index = arr.index{|x| x < 0}index = arr.index{|x| x >= 0} の間違いで、気づいたときはかなり焦った。

バグを全て直したコード。AC。

n, k = gets.chomp.split(" ").map(&:to_i)
v_arr = gets.chomp.split(" ").map(&:to_i)

max_value = 0
(0..k).each do |a|
  next if a > v_arr.length
  a_arr = a > 0 ? v_arr[0..(a-1)] : []
  (0..(k - a)).each do |b|
    next if b > v_arr.length - a
    b_arr = b > 0 ? v_arr[(b*(-1))..-1] : []
    arr = (a_arr + b_arr).sort
    cd = k - a - b
    next if cd < 0
    index = arr.index{|x| x >= 0}
    if index.nil? then
      value = 0
    elsif index == 0 then
      value = arr.inject(0){|sum, i| sum + i }
    elsif cd > index then
      if index == arr.length - 1 then
        value = 0
      else
        value = arr[index..-1].inject(0){|sum, i| sum + i }
      end
    else
      value = arr[cd..-1].inject(0){|sum, i| sum + i }
    end
    max_value = value if value > max_value
  end
end

puts max_value

宝石を入手する操作(操作A, B)を先にやって、その後に宝石を戻す操作(操作C, 操作D)をやるという方針。操作CとDは左端に戻すか右端に戻すかの違いがあるが、戻した後にDには触らないので実質同じ操作とみなせる。

操作AとBで取得した配列の和を取ってソートして、初めて非負整数が出るindexを求める。そのindexと操作CDの回数を見比べて、できるだけ負の数を除くような処理をしてvalueを求める。

これをA, Bの組み合わせでループを回して最大を求める。

A〜Dに限って言えば前回よりも難しかった。しばらくはD問題に対してより速くより正確に解くのを目標としたい。特により速く解いて、E問題に目を通して考えるようにできたらいいな。

AtCoder Beginner Contest 127のA〜D問題振り返り

結果はA, B, C, DがAC。初めてD問題まで解けたので嬉しい。ただしD問題はペナルティをくらいまくった。 f:id:hoshitostar:20190525225444p:plain

問題一覧

https://atcoder.jp/contests/abc127/tasks

提出

A問題

a,b=gets.chomp.split(" ").map(&:to_i)

if a >= 13 then
  puts b
elsif a >= 6 && a<= 12 then
  puts b / 2
else
  puts 0
end

しっかり条件分岐をさせればOK。

B問題

r,d,x=gets.chomp.split(" ").map(&:to_i)

(1..10).each do |i|
  puts r * x - d
  x = r * x - d
end

1ループごとにxを更新しながら出力すればOK。 きれいに書くなら最初に x = r * x - d をしてから puts x をする。

C問題

n,m = gets.chomp.split(" ").map(&:to_i)

max_l = 0
min_r = n
m.times do |i|
  l,r=gets.chomp.split(" ").map(&:to_i)
  max_l = l if l > max_l
  min_r = r if r < min_r
end

result = min_r - max_l + 1
if result > 0 then
  puts result
else
  puts 0
end

lの最大値とrの最小値を求めた後に、その間の数をカウントすればOK。min_r - max_l + 1 はマイナスになることもあるので注意。

ここまでで13分で解けているのでこれまでと比べるとかなりハイペース。もしかすると今回の問題は易しめだったのかもしれません。残りはガッツリD問題。ロジックは30分以内で組めたのですがバグを除去するのに追加で30分以上苦しみました。

D問題

まずは愚直にやってみてTLE。

n, m = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i).sort
min = a_arr.min

m.times do |i|
  b, c = gets.chomp.split(" ").map(&:to_i)
  next if c <= min
  min = 1000000000
  a_arr.each_with_index do |a, j|
    if c > a then
      a_arr[j] = c
      b -= 1
    end
    min = a if a < min
    break if b == 0
  end
  a_arr.sort!
end

puts a_arr.inject(0) {|sum,x| sum + x }

この時点でAの配列をソートすべきだとは分かっていたけど、毎回ソートするのはちょっとなあとも思ってました。まだまだ実行時間の見積もりができていない。

今度は1個だけRE。

n, m = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i).sort

bc = []
m.times do |i|
  bc << gets.chomp.split(" ").map(&:to_i)
end
bc.sort_by!{|(b,c)| -c }

index = 0
bc.each do |(b, c)|
  tmp_index = index
  b.times do |i|
    j = index + i
    if a_arr[j] <= c
      a_arr[j] = c
      tmp_index = j
    else
      break
    end
  end
  index = tmp_index + 1
  break if a_arr[index].nil?
end

puts a_arr.inject(0) {|sum,x| sum + x }

A配列は昇順ソート、BC配列はCの値で降順ソートするのが鍵。A内でより小さい値を、C内のより大きい値で更新していけば最大となる。そして1回更新すればそこのインデックスは見る必要が無い。

なぜ1個だけREなのか試行錯誤を30分くらいしていました。結果、A配列の範囲外のインデックスにアクセスしていることによるエラーという(上のソースコードだとa_arr[j]のところでエラー)。

これがAC。

n, m = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i).sort

bc = []
m.times do |i|
  bc << gets.chomp.split(" ").map(&:to_i)
end
bc.sort_by!{|(b,c)| -c }

index = 0
bc.each do |(b, c)|
  i = 0
  b.times do
    if a_arr[index + i] <= c
      a_arr[index + i] = c
    else
      break
    end
    i += 1
    break if a_arr[index + i].nil?
  end
  index += i
  break if a_arr[index].nil?
end

puts a_arr.inject(0) {|sum,x| sum + x }

TLE→RE9個→RE4個→RE1個→RE1個→RE1個→RE1個→ACとかなりペナルティを食らってしまった。RE1個のときは特に、何か特殊なケースが漏れている思い込んでそのケースを見つけるのがかなり難しかった。見つけるまではちょっと直しては「たぶん通るだろう」の精神で提出していたからここは反省すべきです。

選択ソート

最小のものを探して交換していくソート。実行時間はO(n^2)。「xxソート」という言葉と、その言葉が意味するアルゴリズムが紐付かないことがあるのでしっかり覚えるようにする。

# 選択ソート
arr = gets.chomp.split(" ").map(&:to_i)
puts "before: #{arr}"

(0..(arr.length-2)).each do |i|
  min = arr[i]
  min_j = i
  # 最小を見つける
  ((i+1)..(arr.length-1)).each do |j|
    if arr[j] < min then
      min = arr[j]
      min_j = j
    end
  end
  # arr[i]とarr[min_j]を交換
  tmp = arr[i]
  arr[i] = min
  arr[min_j] = tmp
  puts "#{i}: #{arr}"
end

puts "after: #{arr}"

実行例
標準入力:3 5 4 2 1

before: [3, 5, 4, 2, 1]
0: [1, 5, 4, 2, 3]
1: [1, 2, 4, 5, 3]
2: [1, 2, 3, 5, 4]
3: [1, 2, 3, 4, 5]
after: [1, 2, 3, 4, 5]