AtCoder Beginner Contest 342の参戦記録

RubyでAtCoderに参戦した記録です。
AB2完で、C問題はコンテスト終了後に解説を見てからコードを書きました。

ABC342 A Yay!

ある1文字を除いてすべて同じ文字で構成される文字列Sの中で、他の文字と異なる1文字は前から何文字目かを出力する問題です。

s = gets.chomp.chars  # 受け取った文字列sをcharsメソッドで1文字ずつの配列にする
h = s.tally  # 各アルファベットの出現頻度をHashにまとめる
ans = h.key(1)  # Hashの値が1のもののキーとなる文字をansに代入
puts s.index(ans) + 1  # ansの文字列(配列)sの中での登場箇所インデックス + 1を出力

ABC342 B Which is ahead?

並んでいる人の番号が与えられ、続くクエリで指定される2つの番号のうち、前に並んでいる人のほうの番号を出力する問題です。

n = gets.to_i
array=gets.split(" ").map(&:to_i)
q = gets.to_i
query = []
q.times do
	query << gets.split(" ").map(&:to_i)
end

query.each do |qr|
  if array.index(qr[0]) < array.index(qr[1])
    puts qr[0]
  else
    puts qr[1]
  end
end

最初の提出ではquery.eachのパラメータを1つにして添字を指定していましたが、下記のようにパラメータを2つにした方がすっきり記述できるなと後で気づきました。

query.each do |a,b|
  if array.index(a) < array.index(b)
    puts a
  else
    puts b
  end
end

ABC342 C Many Replacement

文字列Nに対し、Q回の操作を行っていく問題ですが、NもQも最大で10**5くらいまでいくとのことで、一回ずつ操作結果を確認しているとTLEとなります。
解答時間内はTLEを解消することができず、撃沈しました。。

# TLE解答
n = gets.to_i
s = gets.chomp
q = gets.to_i
query = []
q.times do
	query << gets.split(" ")
end

query.each do |q|
  if !s.include?(q[0])
    next
  elsif q[0] == q[1]
    next
  else
    s.gsub!(q[0],q[1])
  end
end

puts s

方針１：クエリの結果をHashにまとめる

全クエリの終了後にアルファベットの各文字がどの文字になるかをHashにまとめ、最後に文字列Nを置き換えします。

n = gets.to_i
s = gets.chomp
q = gets.to_i
query = []
q.times do
	query << gets.split(" ")
end

alpha = [*"a".."z"]
hash = {}
alpha.each do |e|
  hash[e] = e
end
query.reverse_each do |c,d|
    hash[c] = hash[d]
end

puts s.gsub(/./,hash)

• クエリをHashにまとめる際はreverse_eachで最後のクエリからみていきます。というのも実際の操作では、後に行われる操作が前の操作を上書きしていくことになるからです。
  例えば「"a"=>"b"」という操作が出てきたとき、それよりも後のクエリで「"b"=>"c"」という操作があるなら、最終的に「"a"=>"c"」ということになります。これを実現するための記述がhash[c] = hash[d]です。
• String#gsubでreplaceとしてHashを指定できることを初めて知りました。第一引数には置き換えする文字列パターンを指定しますが、今回はすべてのアルファベットの置き換え結果をhashに用意してあるので、全文字を置き換え対象とする/./としています。

方針2："abcdefghijklmnopqrstuvwxyz"という文字列でクエリ結果を検証する

n = gets.to_i
s = gets.chomp
q = gets.to_i
query = []
q.times do
	query << gets.split(" ")
end

before = [*"a".."z"].join
after = [*"a".."z"].join
query.each do |c, d|
  after.gsub!(c,d)
end
puts s.tr(before,after)

クエリの数が多くても、a~zの26文字のみであればすべて検証してもTLEにはなりません。

おわりに

C問題はいつもTLEになってしまい、解決法が考えつかないのが悔しいです。引き続き過去問を解くなどして効率の良い方法や考え方の引き出しを増やしていきたいと思います。

参考リンク