RubyでAtCoderの問題解いてみる

ABC086A: Product

言われた通りaとbの積を2で割った余りを見る

a, b = gets.chomp.split(" ").map(&:to_i)
product = a*b
if product % 2 == 0
  puts("Even")
else
  puts("Odd")
end

ABC081A: Placing Marbles

各文字を数字に変換してたす。

s1, s2, s3 = gets.chomp.split("").map(&:to_i)
count = s1 + s2 + s3
puts(count)

ABC081B: Shift only

各整数を2で割っていき、一番小さいカウントを返す

n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
result = a.map do |i|
  count = 0
  while i % 2 == 0 do
    i = i /2
    count += 1
  end
  count
end
puts(result.min)

ABC087B: Coins

地道に硬貨の枚数を3重ループにしてカウントする

c500 = gets.chomp.to_i
c100 = gets.chomp.to_i
c50 = gets.chomp.to_i
x = gets.chomp.to_i
count = 0
(0..c500).each do |i|
  (0..c100).each do |j|
    (0..c50).each do |k|
      if i*500 + j*100+ k*50 == x
        count += 1
      end      
    end
  end
end
puts(count)

ABC083B: Some Sums

全ての数字に対して条件に合うものの総和を返す。AtCoderのRubyはver 2.3なので2.4から導入のArray#sumは使えない。

n, a, b = gets.chomp.split(" ").map(&:to_i)
sum_total = 0
(1..n).each do |i|
  digits = i.to_s.split("").map(&:to_i)
  sum = digits.inject(:+)
  if a <= sum && sum <= b
    sum_total += i
  end
end
puts(sum_total)

ABC088B: Card Game for Two

貪欲に点数が高い方から交互にとっていき、差を返す

n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
a = a.sort.reverse
alice = 0
bob = 0
(0...n).each do |i|
  if i % 2 == 0
    alice += a[i]
  else
    bob += a[i]
  end
end
puts(alice-bob)

ABC085B: Kagami Mochi

与えられた数字のユニークなものの総和。よく考えるとsortする必要なかった

n = gets.chomp.to_i
d = []
(0...n).each do |i|
  tmp = gets.chomp.to_i
  d[i] = tmp
end
count = d.uniq.sort.size
puts(count)

ABC085C: Otoshidama

地道に枚数分ループ。二種類の枚数が決まれば残りの札の枚数は自然と決まる。

n, y = gets.chomp.split(" ").map(&:to_i)
result = ""
exit_flag = false
(0..n).each do |i|
  (0..n-i).each do |j|
    k = n-i-j
    sum = 10000 * i + 5000 * j + 1000 * k
    if sum == y
      result = [i, j, k].join(" ")
      puts(result)
      exit_flag = true
      break
    end
  end
  if exit_flag
    break
  end
end
if result.size == 0
  puts("-1 -1 -1")
end

ABC049C: Daydream

頭の文字がかぶっているので反転させると簡単。全パターン試す。もっと綺麗にかける気もする。

s = gets.chomp
len = s.size
s.reverse!
patterns = ["dream", "dreamer", "erase", "eraser"].map(&:reverse)
pattern_length = patterns.map(&:size)

i = 0
exit_flag = false
while i < len do
  match_flag = false
  (0..3).each do |j|
    if s[i, pattern_length[j]] == patterns[j]
      i += pattern_length[j]
      match_flag = true
      break
    end
  end
  if not match_flag
    exit_flag = true
    break
  end
end

if exit_flag
  puts("NO")
else
  puts("YES")
end

ABC086C: Traveling

その場に止まれないので、点間のパス長がmin + 2*ｘだといける。もっと綺麗に書ける気がする

n = gets.chomp.to_i
t = []
x = []
y = []
(0...n).each do |i|
  t[i], x[i], y[i] = gets.chomp.split(" ").map(&:to_i)
end

dt = []
dx = []
dy = []
dt[0] = t[0]
dx[0] = x[0].abs
dy[0] = y[0].abs
(1...n).each do |i|
  dt[i] = t[i] - t[i-1]
  dx[i] = (x[i] - x[i-1]).abs
  dy[i] = (y[i] - y[i-1]).abs
end

exit_flag = false
(0...n).each do |i|
  distance = dx[i] + dy[i]
  if dt[i] < distance
    exit_flag = true
    break
  elsif (distance - dt[i]) % 2 == 0
    next
  else
    exit_flag = true
    break
  end
end

if exit_flag
  puts("No")
else
  puts("Yes")
end

時間、メモリの制限

問題はどれも実行時間制限: 2 sec、メモリ制限: 256 MB。問題といただけだとN番煎じ感があるので、参考までに上記コードのtimeとmemoryも載せておく。少なくともC問題まではRubyでも余裕そう。

f:id:hiromichinomata:20190330225811p:plain

f:id:hiromichinomata:20190330225844p:plain

所感、Future Work

2018/09にAtCoderJobsがリリースされている。以前競合のpaizaで問題をRubyでといてSランクまでなったが勝手はほぼ同じ。Paizaと違って時間帯fixなのがつらかったが過去問とく分には問題なさそう。

10年前、TopcoderはC++でといていたが当時のchokudaiさんの言を借りるとスクリプト言語はC++/Javaに対して10倍遅いらしい。TuffleRubyはJITなしのRubyに比べて37倍はやい、PHP8は有利な条件でgccより早いという記事も上がっており、だいぶ速度差は縮まっている？どれもかしこも有利な条件で見ているので競プロの問題という同じ土俵でベンチマークとってみるのも面白そう。

Ref

github.com

algonote

There's More Than One Way To Do It