本履歴

購入した古本の履歴と時々プログラミング

Google Code Jam Qualification Round 2017 A

待ちに待ったGoogle Code Jam。今年もやっていきますよー。 A. Oversized Pancake Flipperは上下逆さまになったパンケーキがN枚与えられるので全部表を向くよう並び替えるもの。ただし、K個の連続したパンケーキを一遍に並び替えるフリッパーを使わなきゃいけない。左右の順番を変えず、1枚1枚のパンケーキをひっくり返すなんてどういうメカニズムだ?!

左L番目からL+K-1番目までパンケーキをひっくり返す操作をFlip(L)と表すと、問題のキーポイントは、1)Flip操作は可換、つまりどういう順番でやっても結果は同じ、2)一番端(例えば左)が裏で与えられたら必ず一番左をひっくり返す必要がある点、すなわち、Flip(1)をする必要がある。それをした後は、一番左のことは忘れて残りのN-1枚が与えられたと考えて、同じことをしていけば最後にK-1枚のパンケーキが残り、それが全部表を向いているかどうかで可能か不可能かの判別ができる(Decrease-and-Conquer)。これをコードに落とせば次の通り。Largeも余裕でパスします。

なんか、よくある問題の気がします。

gets.to_i.times{
    s,k=gets.split
    s=s.chars.map{|c|c==?+}
    k=k.to_i
    ans=0
    0.upto(s.size-k){|i|
        unless s[i]
            k.times{|j|s[i+j]=!s[i+j]}
            ans+=1
        end
    }
  write(s.all? ? ans : "IMPOSSIBLE")
}