2016-04-12 CodeJam 2016 Qualification B

B問題までは時間内に解いたので、書き残します。

B問題

問題内容

問題はこちら (https://code.google.com/codejam/contest/6254486/dashboard#s=p1)

  • 無限パンケーキ屋のバイトリーダーになったつもり
  • パンケーキの裏表を透視できる超能力を持っている
  • そしてパンケーキを上からN枚裏返すことができる
    • 上からN枚裏返すとき、(1,,,,N,,,L)が(N,N-1,,,,2,1,N+1,,,L)になることに注意
  • 上から順番の表裏を+-の入力値で表されるので、何回繰り返せば全部表にできるのか

(正確には英語を読みましょう)

回答のコード

#!env ruby

def flip_counter(string)
  count = 0
  before_char = '^'
  string.chars do |char|
    case before_char + char
    when '^-'
      count += 1
    when '+-'
      count += 2
    end
    before_char = char
  end
  count
end


case_num = STDIN.gets.strip

(1..case_num.to_i).each do |i|
  line = STDIN.gets.strip
  count = flip_counter(line)

  print "Case ##{i}: #{count}\n"
end

コーディングしたときに考えてたこと

  • とりあえず法則性があるはずなので少ない枚数で見つけてみる
    • 最初が表と裏で何か違いがあるのか
    • 最初の裏の数に依存するのか
    • など
  • 2枚の並びに依存することが判明
    • ^- → +1回
    • +- → +2回
    • それ以外は特にカウント不要
  • あとは文字列から上記の並びを探すのみ
  • これは法則性を見つけるかどうかの問題だった気がする