RubyでAtCoderに参戦した記録です。
今回はABC3完でした。
ABC348 A Penalty Kick
N回のペナルティキックの結果を「o」と「x」で記述します。３の倍数回目の時のみキックに失敗するそうです。
n= gets.to_i
for i in (1..n) do
if i % 3 ==0
print "x"
else
print "o"
end
end
特に難しいわけでもないのですが、最初n.timesで書こうとして「あれ？」となりました。
# 誤答です
n.times do
if (n+1)%3 == 0
print "x"
else
print "o"
end
end
.timesでは0~nまでが順番に渡されるという記憶があったのですが、それは下記のようにパラメータを設定した時ですね。
n.times do |i|
if (i+1)%3 == 0
print "x"
else
print "o"
end
end
ABC348 B Farthest Point
座標上に与えられたN個の点について、それぞれの点から距離が最大の点の番号を出力します。距離が最大の点が複数個ある場合は、それらの点のうち番号が最も小さいものを出力します。
距離を求めるのにルートの計算が必要ですが、小数を扱うと誤差が生まれるためなるべく整数で計算できる方法を考えよう、と下記の本にあったのを思い出し、ルートの計算はしない状態で大小比較をしています。
https://www.amazon.co.jp/dp/B09C3TPQYV
各点同士の距離を記録するのに、二次元配列dを用意しました。
各点の距離の２乗を計算し、配列に代入していきます。
この時d[i][j]とd[j][i]は、点iと点jの距離ということで同じ数値が入ります。
例）点が4個でそれぞれの座標が(0,0),(2,4),(5,0),(3,4)だったとき、配列dは[[0, 20, 25, 25], [20, 0, 25, 1], [25, 25, 0, 20], [25, 1, 20, 0]]となります。表にするとこんな感じです。
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 20 | 25 | 25 |
| 1 | 20 | 0 | 25 | 1 |
| 2 | 25 | 25 | 0 | 20 |
| 3 | 25 | 1 | 20 | 0 |
最後に、各行についてその行の最大値を持つ最小のインデックスを割り出します。Array#indexは、引数と==で等しい要素を持つ最初のインデックスを返すので、これを利用しました。点の番号は1から始まるので、+1をして出力します。
n= gets.to_i
array = []
n.times do
array << gets.split(" ").map(&:to_i)
end
d = Array.new(n) { Array.new(n) }
for i in (0..n-1)
for j in (0..n-1)
distance = (array[i][0]-array[j][0])**2 + (array[i][1]-array[j][1])**2
d[i][j] = distance
d[j][i] = distance
end
end
d.each do |p|
puts p.index(p.max) + 1
end
二次元配列の初期化の方法が間違っていることに気づかず、だいぶ時間をロスしてしまいました。悲しみ…
ABC348 C Colorful Beans
N種類のビーンズが1粒ずつあり、それぞれおいしさA、色Cの情報が与えられます。色でしか見分けがつかない中でどれか1粒を選ぶとき、おいしさの最小値の最大値を出力します。
この問題はA、Cなどの値の制約が10の9乗以下とかなり大きいので、工夫しないとTLEになることが予想されます。
過去のコンテストから、ハッシュを使って値を管理するとよさそうだなと推測し実装しました。
具体的には、h = {ビーンズの色 => その色のビーンズの美味しさの最小値}となるように、各ビーンズの情報を1つずつ調べ値を更新していきます。
最後に、ハッシュの全値のうちの最大値を求めることで、おいしさの最小値の最大値が求まります。
n= gets.to_i
array = []
n.times do
array << gets.split(" ").map(&:to_i)
end
h = {}
array.each do |a|
if h[a[1]].nil? || h[a[1]] > a[0]
h[a[1]] = a[0]
end
end
puts h.values.max
この問題はサクッと解けたので、B問題より先にやっておけばよかった…と少し後悔。。
おわりに
配点が250点の時はC問題も解けることが多いようです。300点問題も解けるようになるぞ！
参考リンク