2023年8月16日

(AtCoder) ABC314

少し遅くなりましたが、先週末のAtCoder Beginner Contest 314の振り返りを書きました。

A - 3.14

問題: A - 3.14
提出日時: 2023-08-12 21:07:58（所要時間7分）

自分の回答

n = gets.chomp.to_i
pi_s = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
puts pi_s.slice(0..(n + 1))

開始7分で提出しているけど、これならもう少し早く出せたほうが良さそうです。Rubyのsliceメソッドの仕様を検索したり、確認の遅さみたいなのが7分という時間になってしまいました。

B - Roulette

問題: B - Roulette
提出日時: 2023-08-12 21:33:36（所要時間26分）

自分の回答

n = gets.chomp.to_i

people = []
n.times do |i|
  c = gets.chomp.to_i
  numbers = gets.chomp.split(' ').map(&:to_i)
  people << { id: i + 1, numbers: numbers }
end

x = gets.chomp.to_i

winners = []

people.each do |person|
  next unless person[:numbers].include?(x)

  if winners.empty? || person[:numbers].size < winners.first[:numbers].size
    winners = [person]
  elsif person[:numbers].size == winners.first[:numbers].size
    winners << person
  end
end

puts winners.size
puts winners.map { |winner| winner[:id] }.join(' ')

ルーレットを回して、複数人がそれぞれ複数個の目に賭けたとき、賭けた目が最も少ない人の人数と、それぞれの番号を照準で出力せよという問題。

人の番号(id)と賭けた目の配列(numbers)をHashで保持して、そのそれぞれが勝者であるかどうかを判定して、勝者の配列(winners)に入れるという形で実装しました。peopleの繰り返しの中で、すでにある勝者よりも賭けた目が少ない場合にはそれまでの勝者を捨てています。

C - Rotate Colored Subsequence

問題: C - Rotate Colored Subsequence
提出日時: 2023-08-12 23:18:38（コンテスト終了後に提出）

自分の回答（TLE）

n, m = gets.chomp.split(' ').map(&:to_i)
s = gets.chomp
colors = gets.chomp.split(' ').map(&:to_i)
colored_chars = s.chars.map.with_index do |char, i|
  { color: colors[i], char: char }
end

result = colored_chars

m.times do |i|
  target_chars = []
  result.each_with_index do |char, j|
    target_chars << { found_number: j, char: char } if char[:color] == i + 1
  end

  target_chars.each_with_index do |char, i|
    if i == 0 
      result[char[:found_number]] = target_chars.last[:char]
    else
      result[char[:found_number]] = target_chars[i - 1][:char]
    end
  end
end

puts result.map { |char| char[:char] }.join("")

問題の意味を理解するのにも時間がかかり、提出間に合わず。終了後に自分で考えたものを提出したもののTLE（実行時間超過）でした。

提出 #44538197 - AtCoder Beginner Contest 314

TLEになる理由はAtCoderの解説動画を見て理解できました。上記の実装のように、色ごとの繰り返し(M)の中に文字ごとの繰り返し(N)を入れ子にすると計算量はO(MN)です。この問題の制約ではMとNが最大2*10**5なので、O(MN)は(2*10**5) * (2*10**5)で4*10**10となってしまいます。目安としては計算量は10 ** 8くらいに抑えられると良いらしく、それよりもだいぶ大きい計算量です。

理解できたので書き直してみます。まず、色と文字の組み合わせをHashにします。

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

# 色と文字の組み合わせをつくる
# {1=>[0, 3, 6], 2=>[1, 4, 5, 7], 3=>[2]}みたいな形
char_indexes_grouped_by_color = {}
s.chars.each_with_index do |char, i|
  char_indexes_grouped_by_color[colors[i]] ||= []
  char_indexes_grouped_by_color[colors[i]] << i
end

p char_indexes_grouped_by_color

問題の入力例1を入れて動作確認します。

$ ruby c.rb
8 3
apzbqrcs
1 2 3 1 2 2 1 2
{1=>[0, 3, 6], 2=>[1, 4, 5, 7], 3=>[2]}

よさそうです。このそれぞれを右に巡回シフトしていくので、

"apzbqrcs" => "cpzaqrbs"
"cpzaqrbs" => "cszapqbr"
# 変化なし
"cpzaqrbs" => "cszapqbr"

と操作できればよさそうです。この操作をするには、色ごとに巡回シフトしたもので更新した文字列をつくればよしです。

result = s.clone
char_indexes_grouped_by_color.each do |color, char_indexes|
  char_indexes.each_with_index do |char_index, i|
    insertion_point = if i == char_indexes.size - 1
                        char_indexes[0]
                      else
                        char_indexes[i + 1]
                      end

    insertion_char = s[char_index]
    result[insertion_point] = insertion_char
  end
end

書き直したものを提出したところ、ちゃんとAC（正解）しました。

提出 #44606043 - AtCoder Beginner Contest 314

感想

C問題から計算量を意識しないとTLEになる問題が出てくるので、ちゃんと計算量を見積もれるようにならないとです。あと、TLEになる以前に問題を理解するのも遅いのでその辺も数こなして慣れていければと思います。

記事一覧に戻る