(AtCoder) ABC323

何気にRated参加で初の3完でした。

コンテスト成績証 - AtCoder

A

開始6分ほどで提出。自分としてはそんなに問題のない早さ。自分のレベルだと焦ってWA出すとかよりはゆっくりめで始めた方が良いと思う。

B

16分ほどかけて提出。こちらはもう少し早くしたいところ。

C

こちらは解き始めてから提出まで1時間くらいかかった。計算量減らす工夫はあまり必要のない問題だったけど、問題を読んでコードにしていくときに、処理を散らかして途中でわからなくなってしまいそうになった。やることが多い場合はちょうどよく関数に切り出していくのは大事だと感じた。業務と同じだ。

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

# [1000, 500, 700, 2000]
$points = gets.chomp.split(' ').map(&:to_i)

def calc_score(i, result)
  bonus_point = i + 1
  current_score = bonus_point
  remained_problems = []
  result.each_with_index do |result, j|
    if result == 'o'
      current_score += $points[j]
    else
      remained_problems << { point: $points[j], index: j }
    end
  end

  [current_score, remained_problems]
end

# { current_score:, raw_result:, remained_problems: }
def win_others?(i, current_score, results)
  win = true
  results.each_with_index do |result, j|
    next if j == i
    if current_score < result[:current_score]
      win = false
      break
    end
  end

  win
end

current_results = []
n.times do |i|
  # [['x', 'x', 'x', 'o'], ... ]
  raw_result = gets.chomp.chars
  current_score, remained_problems = calc_score(i, raw_result)

  current_results << { current_score:, raw_result:, remained_problems: }
end

current_results.each_with_index do |current_result, i|
  # 未回答の問題をスコアの高い順に並べる
  sorted_remained_problems = current_result[:remained_problems].sort do |a, b|
    b[:point] <=> a[:point]
  end

  # あと何問とけばほかのプレイヤーに勝るか
  num_of_problems_to_win_others = 0

  current_score = current_result[:current_score]

  # すでに他のプレイヤーに勝っている場合は0で終了
  if win_others?(i, current_score, current_results)
    puts num_of_problems_to_win_others 
    next
  end

  # それぞれ解いた場合のポイントを加算したときに、ほかのプレイヤーを上回るかどうかを判定
  # 上回ったところで、それまでに解いた数を出力して終了
  # remained_problems [{ point: 2000, index: 3 }, ... ]
  sorted_remained_problems.each do |problem|
    current_score += problem[:point]
    num_of_problems_to_win_others += 1

    if win_others?(i, current_score, current_results)
      puts num_of_problems_to_win_others
      break
    end
  end
end

D

時間があまり残ってなかったのもあるけど、全く解法が思いつかなかった。解説を読んで理解しておこうと思う。