Scheme
Gauche
競技プログラミング

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

はじめに

drkenさんの記事で紹介されている10問の問題をScheme(Gauche)でもチャレンジしてみました。

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

@SaitoAtsushiさんからSchemeは引数の評価順序が未定義であることを教えてもらったので、問題1、4、5、8を修正しました。

標準入出力について

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

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

参考Webサイト

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

ABC 086 A - Product

(define (product a b)
  (if (zero? (remainder (* a b) 2))
      "Even"
      "Odd"))

(let* ((a (read))
       (b (read)))
  (display (product a b)))

提出例

関数などを定義するにはdefineを使用します。

define (リファレンスマニュアル)
define (Racket)

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

if (リファレンスマニュアル)
if (Racket)

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

zero? (リファレンスマニュアル)

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

remainder (リファレンスマニュアル)

変数束縛にはlet*を使用します。

let* (リファレンスマニュアル)

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

ABC 081 A - Placing Marbles

(define (placing-marbles str)
  (let ((counter 0))
    (dotimes (i (string-length str))
             (if (char=? (string-ref str i) #\1)
                 (set! counter (+ counter 1))))
    counter))

(display (placing-marbles (read-line)))

提出例

指定した回数だけ処理を繰り返すにはdotimesを使用します。

dotimes (リファレンスマニュアル)

文字列の長さを求めるにはstring-lengthを使用します。

string-length (リファレンスマニュアル)

文字の比較にはchar=?を使用します。

char=? (リファレンスマニュアル)

変数に値をセットするには`set!'を使用します。

set! (リファレンスマニュアル)

文字列の中から文字を取り出すにはstring-refを使用します。

string-ref (リファレンスマニュアル)

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

ABC 081 B - Shift Only

(define (check a)
  (let ((flg 0))
    (dotimes (i (vector-length a))
             (if (odd? (vector-ref a i))
                 (set! flg 1)))
    flg))

(define (calc a)
  (dotimes (i (vector-length a))
           (set! (vector-ref a i) (/ (vector-ref a i) 2)))
  a)

(define (shift-only a cnt)
  (if (= (check a) 1)
      cnt
      (shift-only (calc a) (+ cnt 1))))

(define (create-data n)
  (let ((a (make-vector n)))
    (dotimes (i n)
      (set! (vector-ref a i) (read)))
    a))

(display (shift-only (create-data (read)) 0))

提出例

ベクタを作成するにはmake-vectorを使用します。

make-vector (リファレンスマニュアル)

ベクタの長さを取得するにはvector-lengthを使用します。

vector-length (リファレンスマニュアル)

ベクタの中から要素を取得するにはvector-refを使用します。

vector-ref (リファレンスマニュアル)

奇数判定にはodd?を使用します。

odd? (リファレンスマニュアル)

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

ABC 087 B - Coins

(define (coins a b c x)
  (let ((res 0)
        (total 0))
    (dotimes (i (+ a 1))
      (dotimes (j (+ b 1))
        (dotimes (k (+ c 1))
          (set! total (+ (* 500 i) (* 100 j) (* 50 k)))
          (if (= total x)
              (set! res (+ res 1))))))
    res))

(let* ((a (read))
       (b (read))
       (c (read))
       (x (read)))
  (display (coins a b c x)))

提出例

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

ABC 083 B - Some Sums

(define (find-sum-of-digits n)
  (let ((sum 0))
    (while (> n 0)
           (set! sum (+ sum (remainder n 10)))
           (set! n (quotient n 10)))
    sum))


(define (some-sums n a b)
  (let ((total 0)
        (sum 0))
    (dotimes (i (+ n 1))
             (set! sum (find-sum-of-digits i))
             (if (and (>= sum a) (<= sum b))
                 (set! total (+ total i))))
    total))

(let* ((n (read))
       (a (read))
       (b (read)))
  (display (some-sums n a b)))

提出例

条件式が真を返す限り処理を繰り返すにはwhileを使用します。

while (リファレンスマニュアル)

商を求めるにはquotientを使用します。

quotient (リファレンスマニュアル)

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

ABC 088 B - Card Game for Two

(define (card-game-for-two a)
  (let ((alice 0)
        (bob 0))
    (set! a (sort a >))
    (dotimes (i (vector-length a))
             (if (zero? (remainder i 2))
                 (set! alice (+ alice (vector-ref a i)))
                 (set! bob (+ bob (vector-ref a i)))))
    (- alice bob)))

(define (create-data n)
  (let ((a (make-vector n)))
    (dotimes (i n)
      (set! (vector-ref a i) (read)))
    a))

(display (card-game-for-two (create-data (read))))

提出例

ソートするにはsortを使用します。

sort (リファレンスマニュアル)

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

ABC 085 B - Kagami Mochi

(define (kagami-mochi a)
  (let ((res 0)
        (num (make-vector 110 0)))
    (dotimes (i (vector-length a))
             (set! (vector-ref num (vector-ref a i))
                   (+ (vector-ref num (vector-ref a i)) 1)))
    (dotimes (i 101)
             (if (> (vector-ref num i) 0)
                 (set! res (+ res 1))))
    res))

(define (create-data n)
  (let ((a (make-vector n)))
    (dotimes (i n)
      (set! (vector-ref a i) (read)))
    a))

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

提出例

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

ABC 085 C - Otoshidama

(define (otoshidama n y)
  (let ((res10000 -1)
        (res5000 -1)
        (res1000 -1)
        (c 0)
        (total 0))
    (dotimes (a (+ n 1))
      (dotimes (b (- (+ n 1) a))
        (set! c (- n a b))
        (set! total (+ (* 10000 a) (* 5000 b) (* 1000 c)))
        (if (= total y)
          (begin
            (set! res10000 a)
            (set! res5000 b)
            (set! res1000 c)))))
    (format "~a ~a ~a\n" res10000 res5000 res1000)))

(let* ((n (read))
       (y (read)))
  (display (otoshidama n y)))

提出例

処理を順次実行するにはbeginを使用します。

begin (リファレンスマニュアル)

フォーマット出力にはformatを使用します。

format (リファレンスマニュアル)

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

ABC 049 C - Daydream

(use srfi-13)

(define (daydream s divide)
  (let loop((cnt 0) (pos 0) (flg 0))
    (if (and (< cnt 4) (< pos (string-length s)))
        (if (>= (string-length s) (+ (string-length (vector-ref divide cnt)) pos))
            (if (string=? (substring/shared s pos (+ (string-length (vector-ref divide cnt)) pos))
                   (vector-ref divide cnt))
                (loop 0 (+ pos (string-length (vector-ref divide cnt))) 1)
                (loop (+ cnt 1) pos 0))
            (if (string=? (substring/shared s pos)
                   (vector-ref divide cnt))
                (loop 0 (+ pos (string-length (vector-ref divide cnt))) 1)
                (loop (+ cnt 1) pos 0)))
        (if (= flg 1) "YES" "NO"))))

(define (create-data)
  (let ((divide (vector "dream" "dreamer" "erase" "eraser")))
    (dotimes (i 4)
      (set! (vector-ref divide i) (string-reverse (vector-ref divide i))))
    divide))

(display (daydream (string-reverse (read-line))
                   (create-data)))

提出例

useは、モジュールのインポートと必要に応じてファイルのロードを合わせて行う、便利なマクロです。
srfi-13は文字列ライブラリです。

use (リファレンスマニュアル)
srfi-13 (文字列ライブラリ)

loopは、名前付きletとよばれるループマクロ。

loop (もうひとつの Scheme 入門)

substring/shared

substring/shared (リファレンスマニュアル)
substring/shared (文字列ライブラリ)

文字列判定にはstring=?を使用します。

string=? (リファレンスマニュアル)

ベクタの作成にはvectorを使用します。

vector (リファレンスマニュアル)

文字列の反転にはstring-reverseを使用します。

string-reverse (リファレンスマニュアル)

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

ABC 086 C - Traveling

(define (traveling n tm x y)
  (let ((can 1) (dt 0) (dist 0))
    (dotimes (i n)
      (set! dt   (- (vector-ref tm (+ i 1)) (vector-ref tm i)))
      (set! dist (+ (abs (- (vector-ref x (+ i 1)) (vector-ref x i)))
                    (abs (- (vector-ref y (+ i 1)) (vector-ref y i)))))
      (if (< dt dist)
          (set! can 0))
      (if (not (= (remainder dist 2) (remainder dt 2)))
          (set! can 0)))
    (if (= can 1) "Yes" "No")))

(define (create-data)
  (let ((n  (read))
        (tm (make-vector 110000 0))
        (x  (make-vector 110000 0))
        (y  (make-vector 110000 0)))
    (dotimes (i n)
      (set! (vector-ref tm (+ i 1)) (read))
      (set! (vector-ref x (+ i 1)) (read))
      (set! (vector-ref y (+ i 1)) (read)))
    (values n tm x y)))

(display (call-with-values create-data traveling))

提出例

関数が多値を返すにはvaluesを使用します。

values (リファレンスマニュアル)

返された多値を渡すにはcall-with-valuesを使用します。

call-with-values (リファレンスマニュアル)

最後に

Scheme(Gauche)速いです。
正直、Common Lisp(SBCL)より早かったのには驚きでした・・・。
Lisp系言語の中では一番競技プログラミングに向いているかもしれません。