RubyでAOJの問題を解いてみた
気分転換にRubyでコンテストの問題を解いてみました。
Wikipediaによると、Rubyはオブジェクト指向スクリプト言語で、HaskellよりもCやJavaに近いみたいです。
IDEにはAptana Studio 3.2.2のEclipse Plug-in Versionを使用。何故かデバッグは出来ませんが、コードの記述がやりやすいのと実行が簡単なのは大きいです。
AOJ1041 Kyudo: A Japanese Art of Archery
簡単な足し算の問題。
class Q1041 def doIt n = gets.to_i / 4 while n > 0 calc n n = gets.to_i / 4 end end def calc(n) sum = 0 for i in 1..n sum += gets.to_i end puts sum end end Q1041.new.doIt
全体的にCやJavaなどの命令型プログラミング言語に似ています。やっぱりループとか変数が使えるのはありがたい。
ビックリしたのが、ブロックを{}ではなく、endなどで表すところですね。ちょっと見づらい?
標準出力の入力、出力はgets、puts関数で行います。StringからIntegerにするのはto_i関数です。
AOJ1042 Yes, I have a number
文字数を数える問題。
class Q1042 def doIt eoi = "END OF INPUT" str = gets str = str[0..(str.length - 2)] while str != eoi calc str str = gets str = str[0..(str.length - 2)] end end def calc str array = str.split(/\s/) len = array.length - 1 for i in 0..len print array[i].length end puts end end Q1042.new.doIt
簡単に思っていたら意外と上手くいきませんでした。
まず、RubyにはJavaのように文字列をある文字で分割するsplit関数があります。これを使って
"a b c" → "a","b","c"と分割すればいいと思っていたのですが、split " "だと、"a b" → "a","b"になってしまいます("a b" → "a","","b" としたい)。
しかし、split関数は正規表現でも分割できます。split(/\s/)を使うことで上手くいきます(どうもsplit(" ")はsplit(/\s+/)と等価なようです)。
あと、標準入力に打ち込んでgetsで取得したabcと文字列の"abc"が==演算子でTRUEになりませんでした。
これが全くわからなくて、何で?と思い文字コードを調べてみると、
(getsのabc) = '97','98','99','10'
"abc" = '97','98','99'
getsについている余分な'10'って何だ・・・?と思って調べると、'10' = \nとのこと。改行コードでした。
rubyのgetsは改行コードも含めて取ってくるみたいです。よって、getsの最後を削って比較。
AOJ1043 Selecting Teams Advanced to Regional
割と簡単なシミュレーション問題。
class Q1043 def makeTeam n,team ary = Array.new(n) for i in 0..n-1 s = gets.split(" ").map {|x| x.to_i} ary[i] = team.new(s[0], s[1], s[2], s[3]) end ary = ary.sort{|a, b| (b.a == a.a) ? ((b.p == a.p) ? a.i <=> b.i : a.p <=> b.p) : b.a <=> a.a } mem = Array.new(1001, 0) sum = 0 for i in 0..n-1 if sum < 10 then if mem[ary[i].u] < 3 then sum += 1 mem[ary[i].u] += 1 puts ary[i].i end elsif sum < 20 then if mem[ary[i].u] < 2 then sum += 1 mem[ary[i].u] += 1 puts ary[i].i end elsif sum < 26 then if mem[ary[i].u] < 1 then sum += 1 mem[ary[i].u] += 1 puts ary[i].i end end end end def doIt n = gets.to_i team = Struct.new("Team", :i, :u, :a, :p) while n > 0 makeTeam n,team n = gets.to_i end end end Q1043.new.doIt
この問題で大事なのはデータのソートと構造体の使い方です。
おそらくPriorityQueueを使って、チームの構造体を使えばいけるかなと思い、調べてみるもRubyの標準ライブラリにはPriorityQueueが見つけられません。それどころか、Mapとか他のコンテナも見つけられませんでした。あったのはSetのみ。
意外にもRubyはコンテナがHaskellよりも貧弱でした(外部提供のものはいっぱいありましたが・・・)。
しかし、rubyの配列ソート関数sortがあったのでこれを使うことに。ソート条件を指定するとソートしてくれます。これはなかなか使いやすいです。
構造体を配列にして最後にソートします。
次に構造体です。
team = Struct.new("Team", :i, :u, :a, :p) ary[i] = team.new(s[0], s[1], s[2], s[3])
rubyは上記のようにすると簡単に構造体が作れます。teamが構造体のひな形です。ただ、同じ名前の構造体ひな形は同じプログラムに一つしか作れないみたいですね。
何気なく使っていましたが、Rubyの配列はサイズが足りなかったら自動で動的確保してくれます。便利。ただ、多次元配列が扱いにくいみたいですが。
AOJ1044 CamelCase
文字列操作問題。
class Q1044 CONS = ?a - ?A def change name,type names = divStr name len = names.length ans = "" #cons = ?a - ?A if(type == "U") for i in 0..len-1 names[i][0] = (names[i][0] - CONS).chr ans += names[i] end elsif(type == "L") ans += names[0] for i in 1..len-1 names[i][0] = (names[i][0] - CONS).chr ans += names[i] end else ans += names[0] for i in 1..len-1 ans += "_" + names[i] end end puts ans end def divStr str ary = Array.new tmp = "" len = str.length i = 0 while(i < len) c = str[i] if(c == ?_) ary.push tmp tmp = "" elsif(?A <= c && c <= ?Z) if(tmp != "") ary.push tmp end tmp = "" tmp += (c + CONS).chr else tmp += c.chr end i += 1 #puts tmp =begin print "tmp = " puts tmp print "ary = " puts ary =end end ary.push tmp return ary end def doIt s = gets.split " " while(s[1] != "X") change s[0],s[1] s = gets.split " " end end end Q1044.new.doIt
まず、Stringと文字コードの変換について。"a"の文字コードは?aで表します(?a = 97)。また、文字コードをStringにするには、chr関数を使います(97.chr = "a")。
配列の最後に要素を足す関数はpushです。動的確保って本当に便利・・・。
最後にrubyのコメントの書き方を。
一行は#、複数業は=beginと=endで囲むとコメントアウトできます。