情報自炊

情報を血肉にしたい

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個のときは特に、何か特殊なケースが漏れている思い込んでそのケースを見つけるのがかなり難しかった。見つけるまではちょっと直しては「たぶん通るだろう」の精神で提出していたからここは反省すべきです。