AtCoder Beginner Contest 004

テキストだけで考え方を表現するのは難しいので、今回から図表を導入する。
さしあたって、ツールはdraw.ioを使ってみる。

abc004.contest.atcoder.jp

www.slideshare.net

A - 流行

puts gets.to_i * 2

B - 回転

result = []
4.times { result.unshift(gets.split.reverse.join(' ')) }
puts result.join("\n")

f:id:tkori:20160208100237p:plain

上図のように変換すればいいので、行ごとに逆順にし、それをLIFO(後入れ先出し)で出力すればOK。
行で考えずに入力全体を逆順に出力する方法(puts $stdin.read.chomp.reverse)でもいける。

C - 入れ替え

cards = [*1..6]
n = gets.to_i % 30
n.times { |i| cards[i%5], cards[i%5+1] = cards[i%5+1], cards[i%5] }
puts cards.join

f:id:tkori:20160208104045p:plain

(i mod 5)+1番目のカードと(i mod 5)+2番目のカードを入れ替える操作を繰り返していくだけだが、数が増えていくと、計算量が増えて時間が足りなくなる。
しかし、操作を繰り返していくうちに法則が見えてくる。
初期配置からカードを30回操作すると、再び初期配置に戻ってくるのだ。
つまり、カードの配置は30回周期なので、入力された数を30で割った余りを求めてから、その数だけ操作を行えばいい。

D - マーブル

def calc(left, right)
  (left..right).reduce(0) { |a, e| a + e.abs }
end
 
R, G, B = gets.split.map(&:to_i)
result = 1_000_000_000
 
(-300..300).each do |g_left|
  g_right = g_left + G - 1
  b_left = 100 - (B - 1) / 2
  b_left = g_right + 1 if g_right >= b_left
  b_right = b_left + B - 1
  r_right = -100 + (R - 1) / 2
  r_right = g_left - 1 if r_right >= g_left
  r_left = r_right - R + 1
  
  r_left += 100; r_right += 100
  b_left -= 100; b_right -= 100
  tmp = calc(r_left, r_right) + calc(g_left, g_right) + calc(b_left, b_right)
  result = [result, tmp].min
end
 
puts result

えらく難儀した。
今はこの問題について書く気力がないので手短に(笑)

緑のマーブルの左端を起点にして、赤と青のマーブルの配置を定めていく。
起点の位置を-300から300の位置で走査していき、最小の操作回数になるものを求める。

最終的には他の人の解答を見てすっきり書くことができたが、こういう探索問題の考え方は身に付いていないなと実感。