AtCoder Beginner Contest 343参戦記録

RubyでAtCoderに参戦した記録です。
初めてABC3完できました！（配点は低めでしたが…）
D問題はコンテスト終了後に解説を見てからコードを書きました。

ABC343 A Wrong Answer

0~9の整数のうち、与えられた整数A、Bの和と等しくないもののうち1つを出力する問題です。

a,b=gets.split(" ").map(&:to_i)
for i in (0..9)
  if i != a + b
    puts i
    break
  end
end

ABC343 B Adjacency Matrix

N個の頂点があるグラフについて、各頂点が他のどの頂点と辺を持っているかを出力する問題です。

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

array.each do |e|
  ans = []
  e.each_with_index do |g, i|
    if g == 1
      ans << i + 1
    end
  end
  puts ans.join(" ")
end

0と1で表される行列が与えられ、各行が各頂点についての情報となります。各行の値が1の時のインデックス+1が、その頂点と辺がつながっている頂点の数値です。

ABC343 C 343

与えられる正整数Nの回文立方数の最大値を求めます。
ここでの回文立方数とは、何らかの正整数の3乗で表され、先頭に0を付けずに10進数表記したとき、数字が回文になっているものと定義されています。

n = gets.to_i
i = 1
while i * i * i <= n
  if (i*i*i).to_s == (i*i*i).to_s.reverse
    ans = i
  end
  i += 1
end
puts ans ** 3

Nは10**18以下ということで、1~Nまで全て調べるとTLEになってしまいます。
ここで回文立方数は何かの整数の3乗ということで、Nの三乗根までを調べればよいということになります。
回文判定は、数値をto_sメソッドでStringとし、reverseしたものと同値であるかで判定しました。
条件を満たすiのうちの最大のものがansに格納されるので、その3乗を出力します。

ABC343 D 343

N人が参加するコンテストにおいて、1秒ごとに誰が何点獲得したかのデータが与えられます。各秒において、何種類の得点の値が現れるかを出力する問題です。
こちらも各秒ごとにN人全員の得点を調べているとTLEになってしまいます。

Hashのキーを得点、値を選手の番号の配列にすることも考えましたが、次にその選手が得点したときにHashからその選手の現在の得点を探すのに手がかかりやはりTLE、ということで時間内の回答はできませんでした。

解決策：各選手のその時点の得点を格納する配列と、各得点保持者が何人いるかを格納するハッシュを用意する

AtCoderのYouTube解説放送をみて、そうか、各人の得点を別の配列で管理しておけば、ハッシュではその得点の人が何人いるかという人数だけ増減させればいいのか、と気づかされました。。

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

member = Array.new(n){0}
hash = {0=>n}  # 最初は0点がn人
hash.default = 0  
array.each do |a,b|
    hash[member[a-1]] -= 1  # 最初は全員0点から始まるので、member[a-1]==0、つまりhash[0](=>n)を参照するので、1を引いてもマイナスにはならない
    hash.delete(member[a-1]) if hash[member[a-1]] == 0  # その得点の人が0人になったらHashから削除
    member[a-1] += b
    hash[member[a-1]] += 1  # 上でHashのdefault値を設定することで、ここでのエラーを防ぐ(nilクラスへのNoMethodError)
    puts hash.size
end

おわりに

今回は配点が低めだったとはいえ、初めてC問題で得点出来て素直にうれしかったです。
D問題も手が届かないような技術を使っているわけではなかったので、解説を見て悔しさがありました。。引き続き精進していきます。