Google Code Jam 2017 予選参加してみました - エンジニアリングにはほど遠い

この記事は攻略記事ではなくただの思い出メモです。

せっかくなので去年同様Clojureでやってみました。

Clojureでの処理

lein exec hoge.clj

標準入力読み込みは

(read-line)

問題を解くときは以下な感じ

実行

lein exec hoge.clj < q.txt > a.txt

読み込み部

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

A問題

問題の理解

上下の概念があるパンケーキが並んでいて、一操作は与えられた数(K)を一度にひっくり返す行為。全部表にするための操作数
全部表にできない場合はIMPOSSIBLE

方針

左から見ていって裏があった場合はひっくり返す操作をする
操作をしていって、残り枚数がKの時に全部+ならそれまでの操作数、全部-なら操作数+1、それ以外は全部表にするのは不可能
力技だけど解けた

ソース

(defn- inverse [s]
  (-> s
      (clojure.string/replace #"-" "_")
      (clojure.string/replace #"\+" "-")
      (clojure.string/replace #"_" "+")))

(defn- iter [s k ans]
  (if (= (count s) k)
    (cond
      (= (count (re-seq #"-" s)) 0) ans
      (= (count (re-seq #"\+" s)) 0) (inc ans)
      :else       nil)
    (if (= (first s) \+)
      (recur (subs s 1) k ans)
      (recur (str (inverse (subs s 0 k)) (subs s k)) k (inc ans)))))

(defn- work [s k]
  (if (= (count (re-seq #"-" s)) 0)
   0
   (iter s (read-string k) 0)))

(defn- solve [line]
  (or (apply work (clojure.string/split line #" ")) "IMPOSSIBLE"))

(read-line)

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

B問題

問題の理解

与えられた数値までの数で数字が昇順になるような数の最大を求める

方針

与えられた数に関して、グループ分けをする。(1113325なら111,33,2,5)グループを2個ずつ見ていって、左のグループの数が大きい場合はそのグループの左端の桁の数を1減らし、残りの右全部の各桁を9にする。
partition-byが使えそう
左端が0になった場合は取り除く

ソース

(defn- ninize [list-]
  (take (count list-) (repeat 9)))

(defn- numberize [list-]
  (map #(read-string (str %)) list-))

(defn- asc-list [num-str]
  (defn- iter [[f s & r] result]
    (cond (nil? f) (flatten result)
          (nil? s) (flatten (conj result f))
          :else
          (if (< (first f) (first s))
            (recur (conj r s) (conj result f))
            (flatten (conj result
                           (dec (first f))
                           (ninize (drop 1 f))
                           (map ninize (conj r s)))))))
  (iter (->> num-str
             seq
             (partition-by identity)
             (map numberize)) []))

(defn remove-head-zero [list-]
  (if (= (first list-) 0)
    (drop 1 list-)
    list-))

(defn- solve [line]
  (->> line
       asc-list
       remove-head-zero
       (apply str)))

(read-line)

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

C問題

問題の理解

N個並んでいるシャワー部屋があり、来た人は必ず隣との距離が最大になるように入る
N個に対してk番目の人が入る場合の部屋の隣との距離の最大と最小を求める

方針

k>1の場合、一人目に半分に分けられた部屋に対してkを半分にして考えることができる(NをA,B(B>=A)に分けたとして、k2はB,k3はA,k4はBに絶対入る)
これを整理すると、
- Nが偶数かつkが奇数： N.k = (N/2 - 1).(k/2)
- それ以外： N.k = (N/2).(k/2)

ソース

(defn- max-min [n k]
  (if (= k 1)
    (list (long (/ n 2)) (- (long (/ n 2)) (if (even? n) 1 0)))
    (recur (- (long (/ n 2)) (if (and (even? n) (odd? k)) 1 0)) (long (/ k 2)))))

(defn- solve [line]
  (clojure.string/join
    " "
    (apply max-min (map read-string (clojure.string/split line #" ")))))

(read-line)

(loop [input (read-line) idx 1]
  (when-not (nil? input)
    (println (str "Case #" idx ": " (solve input)))
    (recur (read-line) (inc idx))))

D問題

リタイア。

まとめ

Cは去年より優しかったようで、今年は解けました。一応予選通ったんで１回戦突破目標でがんばります。