#gcj2016

[tnoda-clojure]

Google Code Jam 2016 Qualification Round B: ホットケーキ返し

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

問題

N 枚のホットケーキが重ねられてホットケーキの山ができているが，それぞれのホットケーキは表を向いていたり，裏を向いていたりする。ここで，ホットケーキの重なっている様子を，表 (+), 裏 (-) でそれぞれあらわす。たとえば，

-++--

は，上から順に，裏，裏，表，表，裏，と重っている様子を示す。

さて，ここで，ホットケーキの山を裏返して全てのホットケーキを表向きにしたいが，なるべく少ない回数で全て表向きにしたい。最小何回の裏返しで全てのホットケーキが表向きになるか？ ただし，ホットケーキを裏返しにするときには，途中のホットケーキだけを裏返すことができず，上から i 枚目 (i <= N) までのホットケーキを全て裏返すこととする。たとえば，

--+--

は，途中の 3 枚目だけを裏返すことはできず， 3 枚目を裏返そうとすると, 1–3 枚目までの全てが裏返って，

++---

となる，このあと， 1–2 枚目を裏返して，1–5 枚の全てを裏返すと全て表になるので，計 3 回が最小操作回数となる。

解き方

表と裏が入れ替わる回数を数えればよい

ただし，一番底が裏になっていれば +1

Clojure での解答例

(defn solve [s] (let [ps (partition-by identity (reverse s)) z (count ps)] (if (= \- (ffirst ps)) z (dec z)))) (loop [i 1 ss (-> *in* java.io.BufferedReader. line-seq next)] (when ss (println (format "Case #%d: %d" i (solve (first ss)))) (recur (inc i) (next ss))))

実行例

$ java -cp clojure-1.8.0.jar clojure.main tnoda.gcj2016.qual/src/tnoda/gcj2016/qual/B.clj < B-large.in > clj-large.out

余談

問題を読んだ瞬間に (partition-by identity) が思いついたのですが， clojure-1.8.0.jar を持っていくのを忘れたので，本番では Python で提出しました。 Python のほうが若干コードが長くなっているのですが，どちらにしても一瞬で書けるので，この程度の問題なら，誤差の範囲です。