情報自炊

情報を血肉にしたい

【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問題に目を通して考えるようにできたらいいな。