情報自炊

情報を血肉にしたい

【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個とかはダメ。だから正数の数と負数の数に気をつけながら両者を求めていった。