Edited at

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

More than 1 year has passed since last update.


はじめに

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を使うのは結構厳しいということがわかりました。

(特に実行時間制限など)