AtCoder に登録したら解くべき精選過去問 10 問を Clojure で解いてみた

はじめに

drkenさんの記事で紹介されている10問の問題をClojureでもチャレンジしてみました。
Clojureは初心者で、コードも良い書き方ではないかもしれませんが、それでも良ければ見ていってください。

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~

標準入出力について

標準入力にはreadread-lineを使用します。

標準出力にはprintlnを使用します。

第1問: ABC 086 A - Product (100 点)

ABC 086 A - Product

(defn product [a b]
  (if (zero? (rem (* a b) 2))
    "Even"
    "Odd"))

(println (product (read) (read)))

提出例

関数定義にはdefnを使用します。

条件分岐にはifを使用します。

ゼロ判定にはzero?を使用します。

除算の余りを求める関数にはremを使用します。

第2問: ABC 081 A - Placing Marbles (100 点)

ABC 081 A - Placing Marbles

(defn placing-marbles [s]
  (count (filter #(= \1 %) s)))

(println (placing-marbles (read-line)))

提出例

コレクション内のアイテム数の取得にはcountを使用します。

第1引数がtrueを返すもののみからなるリストを取得するにはfilterを使用します。

第3問: ABC 081 B - Shift Only (200 点)

ABC 081 B - Shift Only

(defn shift-only [n a]
  (loop [counter 0 arr a]
    (if (not-every? even? arr)
        counter
        (recur (+ counter 1) (map #(/ % 2) arr)))))

(defn create-data [s]
  (map #(bigint %) (.split s " ")))

(println (shift-only (Long/parseLong (read-line)) (create-data (read-line))))

提出例

再帰でのループにはlooprecurを使用します。

not-every?は、第2引数に対して第1引数を適用し、結果がfalseの場合、trueを返します。

偶数判定にはeven?を使用します。

mapは、第2引数のリストに対して、第1引数の関数をそれぞれ適用したリストを返します。

文字列を正規表現で分割するにはsplitを使用します。

文字列を数値に変換するにはLong/parseLongを使用します。

第4問: ABC 087 B - Coins (200 点)

ABC 087 B - Coins

(defn coins [a b c x]
  (count
    (for [i (range 0 (inc a)) j (range 0 (inc b)) k (range 0 (inc c))
          :let [res (+ (* 500 i) (* 100 j) (* 50 k))]
          :when (= res x)]
     res)))

(println (coins (read) (read) (read) (read)))

提出例

リスト内包表記にはforを使用します。

自然数列のリストを生成するにはrangeを使用します。

インクリメントはincを使用します。

第5問: ABC 083 B - Some Sums (200 点)

ABC 083 B - Some Sums

(defn find-sum-of-digits [n]
  (reduce + (map #(- % 48) (map #(int %) (seq (format "%d" n))))))

(defn some-sums [arr]
  (let [n (nth arr 0)
        a (nth arr 1)
        b (nth arr 2)]
    (reduce +
      (for [i (range 1 (inc n))
        :let [sum (find-sum-of-digits i)]
        :when (>= sum a)
        :when (<= sum b)] i))))

(defn create-data [s]
  (map #(Long/parseLong %) (.split s " ")))

(println (some-sums (create-data (read-line))))

提出例

TLEになってしまった・・・。
良い書き方があれば教えてください・・・。

@lagenorhynqueさんにツイッターで教えてもらいました。
以下のコードでAC(正解)になります。

(defn find-sum-of-digits [n]
  (->> (str n)
       (map #(- (int %) 48))
       (reduce +)))

(defn some-sums [[n a b]]
  (reduce +
          (for [i (range 1 (inc n))
                :let [sum (find-sum-of-digits i)]
                :when (<= a sum b)] i)))

(defn create-data [s]
  (map #(Long/parseLong %) (.split s " ")))

(println (some-sums (create-data (read-line))))

提出例

seqは、一部のデータ型をリストへキャストします。

formatは、java.lang.String.formatを使用して文字列をフォーマットします。

シーケンスのn番目の要素を取り出すにはnthを使用します。

reduceは、二項演算をする関数とリストを引数にとり、畳み込み処理をします。

->>は、スレッドマクロ(threading macro)といい、Clojureのソースコードを人間に読みやすい形で書けるマクロです。

第6問: ABC 088 B - Card Game for Two (200 点)

ABC 088 B - Card Game for Two

(defn card-game-for-two [n a]
  (let [arr (sort > a)]
    (loop [counter 0 alice 0 bob 0]
      (if (>= counter n)
          (int (- alice bob))
          (if (even? counter)
              (recur (inc counter) (+ alice (nth arr counter)) bob)
              (recur (inc counter) alice (+ bob (nth arr counter))))))))

(defn create-data [s]
  (map #(bigint %) (.split s " ")))

(println (card-game-for-two (Long/parseLong (read-line)) (create-data (read-line))))

提出例

シーケンスを並び替えるにはsortを使用します。

整数にキャストするにはintを使用します。

BigIntへのキャストにはbigintを使用します。

第7問: ABC 085 B - Kagami Mochi (200 点)

ABC 085 B - Kagami Mochi

(defn kagami-mochi [a]
  (count (distinct a)))

(defn create-data [n]
  (loop [counter 0 arr ()]
    (if (>= counter n)
      arr
      (recur (inc counter) (cons (read) arr)))))

(println (kagami-mochi (create-data (read))))

提出例

重複する要素を取り除くにはdistinctを使用します。

先頭に与えられた要素を加えたリストを返すにはconsを使用します。

第8問: ABC 085 C - Otoshidama (300 点)

ABC 085 C - Otoshidama

(defn otoshidama [n y]
  (for [a (range 0 (inc n)) b (range (- (inc n) a))
        :let [c (- n a b)]
        :when (= (+ (* 10000 a) (* 5000 b) (* 1000 c)) y)]
    (format "%d %d %d" a b c)))

(defn main []
  (let [res (first (otoshidama (read) (read)))]
    (if (nil? res)
        (println "-1 -1 -1")
        (println res))))

(main)

提出例

シーケンスの先頭の要素を取り出すにはfirstを使用します。

nilかどうかチェックするにはnil?を使用します。

第9問: ABC 049 C - Daydream (300 点)

ABC 049 C - Daydream

(defn daydream []
  (let [s (apply str (vec (reverse (read-line))))
        divide '("maerd" "remaerd" "esare" "resare")
        l (count s)]
    (loop [cnt 0 pos 0 flg 0]
      (if (and (< cnt 4) (< pos l))
          (if (>= (count s) (+ (count (nth divide cnt)) pos))
              (if (= (subs s pos (+ (count (nth divide cnt)) pos)) (nth divide cnt))
                  (recur 0 (+ pos (count (nth divide cnt))) 1)
                  (recur (inc cnt) pos 0))
              (if (= (subs s pos) (nth divide cnt))
                  (recur 0 (+ pos (count (nth divide cnt))) 1)
                  (recur (inc cnt) pos 0)))
          (if (= flg 1) "YES" "NO")))))

(println (daydream))

提出例

文字列を反転するにはreverseを使用します。

引数のコレクションを含む新しいベクタを作成するにはvecを使用します。

strapplyを組み合わせて、ベクタの要素を連結して文字列にして返します。

部分文字列の取得にはsubsを使用します。

第10問: ABC 086 C - Traveling (300 点)

ABC 086 C - Traveling

(defn traveling [n t x y]
  (loop [cnt  0
         dt   (- (nth t (inc cnt)) (nth t cnt))
         dist (+ (Math/abs (- (nth x (inc cnt)) (nth x cnt)))
                 (Math/abs (- (nth y (inc cnt)) (nth y cnt))))
         can  (if (or (< dt dist) (not (= (rem dist 2) (rem dt 2)))) 0 1)]
    (if (= cnt n)
        (recur (inc cnt)
               (- (nth t (inc (inc cnt))) (nth t (inc cnt)))
               (+ (Math/abs (- (nth x (inc (inc cnt))) (nth x (inc cnt))))
                  (Math/abs (- (nth y (inc (inc cnt))) (nth y (inc cnt)))))
               (if (or (< dt dist) (not (= (rem dist 2) (rem dt 2)))) 0 1))
        (if (= can 1) "Yes" "No"))))

(defn create-data [n]
  (loop [cnt 0 t () x () y ()]
    (if (= cnt n)
        (list (reverse (cons 0 t))
              (reverse (cons 0 x))
              (reverse (cons 0 y)))
        (recur (inc cnt)
               (cons (read) t)
               (cons (read) x)
               (cons (read) y)))))

(def n (read))
(def data (create-data n))

(println (traveling n (nth data 0) (nth data 1) (nth data 2)))

提出例

テストケース13個中、1個がWA(不正解)、3個がTLE(実行時間制限超過)でした・・・。
(残りの9個は、AC(正解))
良い方法があればご教授願います。

@lagenorhynqueさんにツイッターで教えてもらいました。
以下のコードでAC(正解)になります。

(defn abs [x]
  (if (neg? x)
    (- x)
    x))

(-> (loop [lines (map #(clojure.string/split % #"\s")
                      (rest (line-seq (clojure.java.io/reader *in*))))
           [curr-t curr-x curr-y] [0 0 0]]
      (if-let [line (first lines)]
        (let [[t x y :as next-dest] (map #(Integer/parseInt %) line)
              d-t (- t curr-t)
              d-x (abs (- x curr-x))
              d-y (abs (- y curr-y))
              d-x+y (+ d-x d-y)]
          (if (zero? (mod d-t d-x+y))
            (recur (rest lines) next-dest)
            false))
        true))
    (if "Yes" "No")
    println)

提出例

->は、スレッドマクロ(threading macro)といい、Clojureのソースコードを人間に読みやすい形で書けるマクロです。

line-seqは文字列を遅延シーケンスとして返します。

restはリストの先頭の要素を除いた残りの要素を取り出します。

最後に

初心者がゴリ押しでやってみました。
Clojureユーザーの方たちから怒られそうなコードです、すいません。
もっと、関数型プログラミングの勉強をしたほうが良いですね。

結局、第5問と第10問はちゃんと解けませんでした・・・。
何か、良い方法があればご教授願います。

第5問と第10問は、@lagenorhynqueさんが解いてくれました。

とりあえず、AtCoderでClojureを使うのは結構厳しいということがわかりました。
(特に実行時間制限など)

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.