Atcoder Beginners SelectionをRubyで解いてみた

こんにちは、春の応用情報を受けるため参考書を買ったのですが開いてすらない、かささぎです。たぶん落ちる。。。

Atcoder で初心者が解いてみるべき問題を集めたAtcoder Beginners Selectionというコンテストができたみたいなので、解いてみました。

軽く調べたところ、drkenさんの記事　AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～　で選ばれた問題を、Atcoderの実際のコンテストと同じ形式で解けるようです。

期限は4018年までです。

普段AtcoderではJavaを使って解いているのですが、難易度があまり高くないことから、勉強のためRubyですることにしました。
Rubyは1年ほど前に軽く勉強して以来ほとんど触っておりません。

それでは解いたものの解説をしていきます。

PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

　＜ソースコード＞

N1 = gets.to_i
N2,N3 = gets.chomp.split.map(&:to_i)
S = gets.chomp

puts("#{N1+N2+N3} #{S}")

　入力では、普段はJavaで書いているため、改行などをあまり気にすることなくScannerクラスのsc.nextを何も考えず使いまくっていたのですが、Rubyではそうもいきませんでした。
同じ行に空白区切りで複数のデータを取得する際はsplitが必要です。
　出力はprintだと改行なし、putsだと改行ありです。変数の値は#{}内に記述することで出力できます。ちなみにRubyでのコメントアウトには#を用います。

ABC086A - Product

　＜ソースコード＞

a,b = gets.split.map(&:to_i)
puts (a*b)%2==0 ? "Even" : "Odd"

　puts C ? "A" : "B" で、Cの条件がtrueならA、falseならBを出力という処理になります。
　ちなみにRubyでは偶数かどうかを返すEven?メソッド、奇数かどうかを返すodd?メソッドもあります。
　せっかくRubyの練習をしているので、そちらを使ったほうがよかったかもしれなかったですね。

ABC081A - Placing Marbles

　＜ソースコード＞

s = gets
puts s.count("1")

　対称データの個数を数えて返してくれるcountメソッドを用いました。このような便利なメソッドがいろいろあるのはRubyの強みですね。

ABC081B - Shift only

　＜ソースコード＞

N = gets.to_i
s = gets.chomp.split.map(&:to_i)
min = 99

N.times do |num|  
	cnt = 0
	while s[num]%2 == 0 do
		cnt += 1
		s[num] /= 2
	end

	if(cnt < min) then
		min = cnt
	end
end

puts min

　ここから少し難しくなります。

　それぞれの値を2で割れるだけ割って、それぞれの値で割れた回数の最低値を出力しています。
　minの初期値は割り切れうる最大回数より大きな値にしておく必要があります。問題の条件より、

　よって30以上であればどんな値でもいいです。今回は面倒くさかったので99にしておきました。

　N.timesループは、0~N-1までN回繰り返されます。何回目のループなのかはイテレータ 　|変数名| で参照できます。
　イテレータによる処理が高機能であるため、Rubyではインクリメント・デクリメントが用意されていないそうです。
そのためcnt += 1と記述しています。それを知らず最初はエラーを吐きました。

ABC087B - Coins

　＜ソースコード＞

A = gets.to_i
B = gets.to_i
C = gets.to_i
X = gets.to_i

ans = 0

(A+1).times do |a|
	(B+1).times do |b|
		(C+1).times do |c|
			m = a*500 + b*100 + c*50;
			ans += 1 if m==X
			break if m>X 
		end
	end
end

puts ans

　3重ループを用いました。O(n^3)ですが、nの最大が50なので問題ありません。
　
　Rubyでのif文は

if (条件) then
  処理
end

ですが、処理が1つのみの場合は、

処理 if (条件)

　と書くことができます。ただしJavaのように、

 if (条件)
 処理

　のように書くことはできません。

ABC083B - Some Sums

　＜ソースコード＞

N,A,B = gets.split.map(&:to_i)

ans = 0
N.times do |num|
	val = num+1

	cnt = 0
	val.to_s.size.times do |v|
		cnt += val.to_s[v].to_i
	end

	if cnt >=A && cnt<=B then
		ans += val 
	end
end

puts ans

　こちらもNの最大値が10^4のため、2重ループ(O(n^2))を用いています。これが10^9とかだと、もう少し効率の良いアルゴリズムを考えなければなりません。

　val.to_s[v].to_i という処理は、v文字目を取得するためにいったんString型に変換し、得たデータをint型にキャストしています。

ABC088B - Card Game for Two

　＜ソースコード＞

N = gets.to_i
A = gets.split.map(&:to_i)
A.sort! {|a,b| b <=> a}
ans = 0
A.size.times do |a|
	 a%2==0 ? ans+=A[a] : ans-=A[a]
end
puts ans

　最終的に求めるものは、Aliceの点数とBobの点数の差分ですから、Aliceを正、Bobを負として点数計算しています。
　単純にAliceの総点とBobの総点を求めてから差分をとってもいいと思います。

　.sort!で配列を昇順にソートします。元のデータを変更する際には!を付けます。
　今回はデータを高い順、つまり降順にソートしたいです。

　わからなかったのでggったのですが、A.sort! {|a,b| b <=> a}　と書けばいいみたいですね。
　両端のデータをイテレータを用いて取得していきながら、swapしているみたいです。

ABC085B - Kagami Mochi

　＜ソースコード＞

N = gets.to_i
D = []
N.times do
	D << gets.to_i
end
puts D.uniq.size

　この問題では値の重複を除いた数を出力すればACです。
　<<で、配列末尾に値を追加できます。
　.uniqメソッドは配列の重複値を除いた配列を返してくれます。つまりそれのsizeを出力すればOKです。

ABC085C - Otoshidama

　＜ソースコード＞

def ans(a,b,c)
	puts("#{a} #{b} #{c}")
	exit
end

X,Y = gets.split.map(&:to_i)
ans = []
N = Y/1000

val = N-X
(0..val/9).each do |v|
	if (val - v*9)%4==0 then
		y = v
		i = (val - y*9)/4
		h = N - 10*y - 5*i

		ans(y,i,h) if(y+i+h == X && h>=0)
	end
end
ans(-1,-1,-1)

　この問題は一度解いたことがあったので、その時とは別のアルゴリズムを考えました。
　Yは1000の倍数だという条件を用いて、各お札の枚数をa,b,c とおくと次のようになります。

　(1)-(2)より、

　ここまでできれば、あとはループし、それぞれの合計枚数がXであるときに出力するだけです。
　まあ5000円札の計算式を少し間違えてて1WA出してしまいましたが...

　ちなみに、一度出力したらプログラムを終了するために関数を用いました。
　Rubyでの関数は以下のように作れます。

def 関数名(引数の変数名)
　処理
end

　引数の変数名は大文字で始めてはいけないみたいです。

ABC049C - 白昼夢 / Daydream

　
　＜ソースコード＞

s = gets.chomp
s.gsub!('eraser','')
s.gsub!('erase','')
s.gsub!('dreamer','')
s.gsub!('dream','')
puts s.length==0 ? 'YES' : 'NO'

　文字列から、4つの単語をすべて取り除いたときに、何か文字が残っていたらNO、なにもなかったらYESです。

　気をつけなければならないのは取り除いていく順番です。
　eraserよりerase、dreamerよりdreamを先に取り除くと、'eraserdreamer'などでWAです。
　また、erase,eraserよりdreamerを先に取り除くと、'dreamerase'などでWAです。
　従ってソースコードのような順にする必要があります。

　gsub("A","B")メソッドでは、正規表現の"A"をすべて”B"に変換してくれます。
　また、文字の取得時にchompメソッドを付け、改行コードを取り除く処理が必要です。

ABC086C - Traveling

　＜ソースコード＞

N = gets.to_i
turn = []
px = []
py = []

N.times do
	t,x,y = gets.split.map(&:to_i)
	turn << t
	px << x
	py << y
end

x=y=t=n=0

N.times do

	if(((x-px[n]).abs() + (y-py[n]).abs() > turn[n] - t )||
	   ((x-px[n]).abs() + (y-py[n]).abs() ) %2 != (turn[n] - t)%2) then
		break
	end

	x = px[n]
	y = py[n]
	t = turn[n]
	n = n+1
end

puts (n == N) ? 'Yes' : 'No'

　xの差分とyの差分の合計が、turnの差分より大きい場合はもちろん実行不可能です。

　また、その場にとどまることができないという条件より、
　xの差分とyの差分の偶奇とturnの差分の偶奇が違う場合も実行不可能です。

　そのどちらかが現れた場合、ループをbreakします。
　最終的に最後までたどり着いたかどうかでYesかNoを出力しています。

　YesとNoをすべて大文字にしていて1WA出しました。
　初歩的なミスですね。気を付けます。

感想

　
　Rubyは慣れておらず、たまにエラーを吐いて躓いたりしました(インクリメントとか)。
　しかしやはりインタプリタ言語は便利ですね。わざわざコンパイルしなくていいのがありがたい。

　またJavaではAtcoderで提出する際にクラス名をMainにしなければならないのですが、ローカル環境ではMain1、Main2…という感じにしていてわざわざ提出時に修正していたので、そういうこともしなくていいのはいいです。

　Rubyについて少しは理解できたので、Ruby on railsにも挑戦したいと思います。

　それでは。