更新日: 2014年12月18日
Ruby

ゆるふわな競技プログラミングWEBサービス yukicoder に挑戦してみた

昨日読んだ以下のエントリーがとても興味深かった。例で出されていた電卓のクイズが面白くて、ついつい惹き込まれて読んじゃいました。

社会人10年目から始める競技プログラミングのすすめ – kuuso1のブログ

【お知らせ】英単語を画像イメージで楽に暗記できる辞書サイトを作りました。英語学習中の方は、ぜひご利用ください！

画像付き英語辞書 Imagict | 英単語をイメージで暗記
【開発記録】
英単語を画像イメージで暗記できる英語辞書サービスを作って公開しました

それで、このエントリーの最後のほうで競技プログラミングのWEBサービスがいくつか紹介されていたのですけど、その中で yukicoder というWEBサービスを見つけまして、このサービスが日本語だし面白そう。

yukicoderへようこそ!
yukicoderは競技プログラミング・アルゴリズムをゆるふわに練習する目的で運営されています。

yukicoder

topcoder 等は英語ですしガチすぎる印象で及び腰なのですけど、yukicoder は日本語だしとっつきやすそうだったのでちょっと挑戦してみた次第です。初めて挑戦してみた問題はこれ↓。★1つなので一番簡単なレベルの問題です。

No.29 パワーアップ – yukicoder

解答コード

2通りの解答用コードを書いてみました。最初おもいっきり間違えちゃったのですけどねｗ

解答1（no_29_1.rb）

h = Hash.new(0)
n = gets.chomp.to_i
n.times do
  gets.split.map(&:to_i).each do |i|
    h[i] += 1
  end
end

count = 0
rest = 0
1.upto(10) do |j|
  count += h[j] / 2
  rest += 1 if h[j] % 2 == 1
end

count += rest/4
puts count

h = Hash.new(0)

n = gets.chomp.to_i

n.times do

gets.split.map(&:to_i).each do |i|

h[i] += 1

end

count = 0

rest = 0

1.upto(10) do |j|

count += h[j] / 2

rest += 1 if h[j] % 2 == 1

end

count += rest/4

puts count

#6688 No.29 パワーアップ – yukicoder

解答2（no_29_2.rb）

n = gets.chomp.to_i
items = []
n.times do
  gets.split.map(&:to_i).each do |i|
    items << i
  end
end
items.sort!

flags = Array.new(n * 3){ false }
count = 0
prev = items[0]
1.upto(n * 3) do |i|
  if prev == items[i] && !flags[i-1] && !flags[i]
    count += 1
    flags[i-1] = true
    flags[i]   = true
  end
  prev = items[i]
end

count += flags.select{|i| !i}.size/4
puts count

n = gets.chomp.to_i

items = []

n.times do

gets.split.map(&:to_i).each do |i|

items << i

end

items.sort!

flags = Array.new(n * 3){ false }

count = 0

prev = items[0]

1.upto(n * 3) do |i|

if prev == items[i] && !flags[i-1] && !flags[i]

count += 1

flags[i-1] = true

flags[i] = true

end

prev = items[i]

end

count += flags.select{|i| !i}.size/4

puts count

#6690 No.29 パワーアップ – yukicoder

ローカルで試す場合

ページ最下部の「テストケース一括ダウンロード」から、テスト用のファイル一覧をダウンロードできます。以下のように配置しました。


$ tree -L 2
.
├── no_29_1.rb
├── no_29_2.rb
└── testcase
    ├── test_in
    └── test_out

$ tree -L 2

├── no_29_1.rb

├── no_29_2.rb

└── testcase

├── test_in

└── test_out

testcase/test_in 以下が入力用ファイル、testcase/test_out 以下が出力（解答）のファイルです。

書いたコードは、ローカルで以下のように実行できます。


$ ls ./testcase/test_in | sort -n | ruby -n -e 'print "./testcase/test_in/#{$_}"' | xargs -n 1 ruby ./no_29_1.rb
$ ls ./testcase/test_in | sort -n | ruby -n -e 'print "./testcase/test_in/#{$_}"' | xargs -n 1 ruby ./no_29_2.rb

$ ls ./testcase/test_in | sort -n | ruby -n -e 'print "./testcase/test_in/#{$_}"' | xargs -n 1 ruby ./no_29_1.rb

$ ls ./testcase/test_in | sort -n | ruby -n -e 'print "./testcase/test_in/#{$_}"' | xargs -n 1 ruby ./no_29_2.rb

ファイル名の一覧を数値順でソートするのに苦労しました… find でできなかったので、結局 ls と sort -n を使った。あと、xargs は “-n 1” のオプションで引数を1つずつ処理できるのですね、初めて知った。

初級Linuxプログラミング xargsで1個ずつ処理
 xargs でコマンドに引数をひとつずつ渡す方法 – ablog

以上のコマンドで、test_in 以下の入力用ファイルを1つずつ読み込んで、Rubyコード（./no_29_1.rb, ./no_29_2.rb）に、test_in 以下の入力用ファイルを1つずつ渡して、それぞれの出力を確認できます。出力を testcase/test_out 以下のファイルの解答と答え合わせすればOK。

アルゴリズム強くなりたいですし、yukicoder 面白いですので、時間がある時にぼちぼちトライしてみようと思います。

私は以下の本で Ruby を覚えました。メタプログラミングRubyは入門を超える内容で難しめです。

たのしいRuby 第5版

パーフェクトRuby (PERFECT SERIES 6)

メタプログラミングRuby 第2版