GCJ 2016 Qualification Round B: Revenge of the Pancakes

問題

• と - からなる文字列Sが与えられる。以下の操作を繰り返して、+ のみの文字列に変換するための最小回数を求める。

・文字列Sのi番目までの+と-を反転させて、なおかつ、逆順にする。

例： 文字列Sが ++--+ でi=3の場合、++- を反転(--+）して逆順（+--）にする。 　その結果、文字列Sは +---+ になる。

https://code.google.com/codejam/contest/6254486/dashboard#s=p1

方針

操作の制約として、必ず先頭から指定した範囲の文字列を反転させることになるので、最後の操作の直前の状態は、以下のように「-の連続と+の連続」または「-のみ」の状態になる。

----++++　（-の連続と+の連続）
--------　（-のみ）

つまり、文字列の前の方から順番に+や-が連続する状態を作っていくようにする。

・先頭が+の場合、順番に文字をチェックしていき、-が出現したら直前までの文字列に対して操作を行う

+++--++
↓　先頭が+なので4番目に-を見つけた時点で3番目までを操作対象にする
-----++

・先頭が-の場合、上記の逆の操作をする

以上を繰り返すと、文字列の前半が+の連続、-の連続を交互に繰り返すことになり、最終的に+のみになったら処理終了となる。

実装

最初は文字列を実際に反転させる処理を実装し、毎回文字列を先頭からチェックするような実装にしていた。（計算量は O(N²)）

しかしながら、動作確認をしていて、i番目までを処理した時点でそれより前の文字列は + or - の連続になっていることは分かっているので、先頭に戻らずそのままi番目以降の文字をチェックすれば良いことに気づいた。（計算量は O(N)）

def solve(cakes)
    n = cakes.size
    return 0 if cakes.count{|c|  c == "+" } == n

    c = cakes[0]
    count = 0
    i = 1
    while(i < n)
        if cakes[i] != c then
            count += 1
            c = (c == "+" ? "-" : "+")
        end
        i += 1
    end
    count += 1 if c == "-" 
    return count
end

i = 1
STDIN.gets
STDIN.each_line do |line|
    line.chomp!
    cakes = Array.new
    line.chars {|c| cakes.push(c)}

    printf("Case #%d: %d\n", i, solve(cakes))
    i += 1
end