Rubyで解くAtCoder ABC 200 (A,B,C問題まで)

はじめに

Rubyの勉強の一環として，AtCoderのコンテストの過去問を解いています。
（割と楽しくて，半分くらい趣味になっていますが・・・）

コンテストに出てみた

せっかくなら大会に出たほうが目標ができて楽しめると思ったので，初心者向けのコンテストに出てみました。

結果としてはA~Fの問題のうち，A~Cまで解けて，DやEの問題を読んで考えてみている間に制限時間が終わってしまいました。
Rubyでの解説は少ないため，解説を読んで自分なりに考えたりしたことをまとめてみようと思います。

A - Century

1~3000の数字 N が与えられるので，西暦 N 年は何世紀かを出力する問題。

「金額にしたとき，何枚の100円玉で払えるか」という小学生向けの覚え方を思い出して，whileループで解いてみました。

ABC200_A

n = gets.to_i
cnt = 0

while n > 0
  cnt += 1
  n -= 100
end

puts cnt

【解説を読んで】
「99を足して100で割って小数点以下を切り捨て」だともっと短く書けました。

ABC200_A

N = gets.to_i
puts (N + 99)/100.to_i

B - 200th ABC-200

整数 N に対し， 以下のいずれかの操作を K 回行った結果を出力します。

1. 整数 N が 200 の倍数であれば、N を 200 で割る。
2. そうでなければ、整数 N を、N の後ろに文字列として 200 を付け加えた整数に置き換える。

操作 1 はそのまま 200 で割ればいいとして，操作 2 は文字列に変換して操作してから数値に戻す必要があるかなと思ったのですが・・・
操作 2 は「1000 をかけて 200 を足す」とすれば数値のまま同じことができるので，こうしました。

ABC200_B

n,K = gets.split.map(&:to_i)

K.times do
  if n%200 == 0
    n /= 200
  else
    n = n*1000 + 200
  end
end

puts n

C - Ringo's Favorite Numbers 2

N 個の数列内から 2 つの数値を選んだとき，その差が200で割り切れる ( 0 も含む) 組み合わせの個数を求める問題。

知識がまだ少ないので，自分なりに考えてやってみました。
「200 で割った余りが同じ数字どうしの組は，差が 200 で割り切れる」ことが基本方針です。

まず，数列内の全ての数値を，200 で割った余りに変換します。
その後，group_byメソッドで値ごとにキーにしたハッシュを生成します。

(例)
[123, 223, 123, 523, 200, 2000]
↓
[123, 23, 123, 123, 0, 0]
↓
{123 => [123, 123, 123], 23 => [23], 0 => [0, 0]}

数字が 2 つあれば，その中から 2 つ選ぶ組み合わせは $ _2 C _2 $ 通り
数字が 3 つあれば，その中から 2 つ選ぶ組み合わせは $ _3 C _2 $ 通り
数字が 4 つあれば，その中から 2 つ選ぶ組み合わせは $ _4 C _2 $ 通り
...
数字が n つあれば，その中から 2 つ選ぶ組み合わせは $ _n C _2 $ 通り

ということで，キー値ごとの値の個数を $ _n C _2 = o
$ で計算して足し合わせています。

ABC200_C

N = gets.to_i
nums = gets.split.map(&:to_i)
nums.map! { |i|i%200 }

h = nums.group_by{|i| i}
cnt = 0

h.each_value do |arr|
  n = arr.length
  cnt += n*(n-1)/2
end

puts cnt

感想

初めての大会でしたが，非常に楽しめました。
D問題以降は基本的なアルゴリズムの知識が必要そうなので，解説を読んだりほかの過去問も解いてみて，少しずつできるようになりたいと思っています。
ほぼ毎週，初心者向けの大会があるらしいので，来週も出てみようと思います。