AtCoder Beginners Selection を Scheme(Lisp)で解く後編 - プログラミングを上達させたい

競技プログラミングサイトAtCoder にて、「初心者の方はまずこの問題を解いてみよう！」という趣旨の
AtCoder Beginners Selection - AtCoder Beginners Selection | AtCoder
というページが出来ていました。

最近全然プログラミングやってなかったのと、図書館で借りたこの本

を読んでテンションがあがっていたのもあり、Schemeで問題を解いていくことにしました。
11問あるんですが、この記事では8問目からラストまで。

前編はコチラ↓
AtCoder Beginners Selection を Scheme(Lisp)で解く前編 - プログラミングを上達させたい

8問目

ABC085B: Kagami Mochi - AtCoder Beginners Selection | AtCoder
配列にソート＆重複消す操作が必要な問題です。
今回は、そもそも入力の段階でソートと重複消去を行っています。
特殊な挿入ソート、って感じですね。

(define N (read))
 
;Nがたいして大きくないので挿入ソートで。同じ要素あれば挿入せず。
(define insert
  (lambda (element list)
    (cond ((null? list) (cons element '()))
          ((> element (car list)) (cons element list))
          ((= element (car list)) list)
          (#t (cons (car list) (insert element (cdr list)))))))
    
 
(define read_insert_sort
  (lambda (list n)
    (if (= n 0) list
        (let* ((new_element (read)))
          (read_insert_sort (insert new_element list) (- n 1))))))
 
(display (length (read_insert_sort '() N)))
 
(newline)

9問目

ABC085C: Otoshidama - AtCoder Beginners Selection | AtCoder
Nが2000なので、ドシンプルな総当たりとしてやってしまうと
Nの3乗のオーダー⇒2000の3乗で80億パターンとなり、制限時間オーバーしてしまいます。
ただ、1000円札と5000円札の枚数が分かれば1万円札の枚数は引き算で算出できるため、
1000円札と5000円札の枚数について総当たりでループかければ間に合います。
2000*2000=400万なので、大丈夫ですね。

(define N (read))
(define YEN (read))
 
;今回も総当たり
;ただし1000円札の枚数と5000円札の枚数に関しての総当たり
(define next_list
  (lambda (now_list)
    (let ((first (car now_list))
          (second (car (cdr now_list))))
      (cond ((>= first N) '())
            ((>= (+ first second) N)
             (list (+ first 1) 0))
            (#t (list first (+ second 1)))))))
 
(define clear_check
  (lambda (list)
    (let ((first (car list))
          (second (car (cdr list))))
      (= YEN (+ (* (- N (+ first second)) 10000) (* first 5000) (* second 1000))))))
 
(define ans
  (lambda (now_list)
    (cond ((null? now_list) '(-1 -1 -1))
          ((clear_check now_list)
           (list (- N (+ (car now_list) (car (cdr now_list)))) (car now_list) (car (cdr now_list))))
          (#t (ans (next_list now_list))))))
 
(define an (ans (list 0 0)))
 
(display (car an))
(display " ")
(display (car (cdr an)))
(display " ")
(display (car (cdr (cdr an))))
(newline)

10問目

ABC049C: 白昼夢 / Daydream - AtCoder Beginners Selection | AtCoder
与えられた文字列の末尾から順にチェックしていきます。
schemeは標準入出力が分かりにくい部分があり、いつも使っている入力関数"read"で文字列を読み込むと、文字列ではなくシンボルとして読み込まれてしまいます。
よって、"symbol->string"という関数を噛ませる必要があります。

;単なる文字列はreadで読むと型がsymbolになっている。注意!!!!
;symbol->stringで文字列に変換する
(define mojiretsu (symbol->string (read)))
 
(define tailcheck
  (lambda (string checkstr)
    (let ((strlen (string-length string))
          (checklen (string-length checkstr)))
      (and (>= strlen checklen) (string=? (substring string (- strlen checklen) strlen) checkstr)))))
 
(define check
  (lambda (str)
    (let ((len (string-length str)))
      (cond ((= (string-length str) 0)
             "YES")
            ((tailcheck str "dreamer")
             (check (substring str 0 (- len 7))))
            ((tailcheck str "dream")
             (check (substring str 0 (- len 5))))
            ((tailcheck str "eraser")
             (check (substring str 0 (- len 6))))
            ((tailcheck str "erase")
             (check (substring str 0 (- len 5))))
            (#t "NO")))))
 
(display (check mojiretsu))
(newline)

11問目

ABC086C: Traveling - AtCoder Beginners Selection | AtCoder
移動できるかに関しては
・そもそも時間的に間に合うか
・ちょうどぴったり着地できるか(1秒に1段動かなきゃいけない＝偶奇の一致)
の2つをチェックしなければいけません。

また、スタート地点(0秒後に(0,0))を忘れずに！

(define N (read))
 
(define time-and-position
  (lambda (a b c)
    (cons a (cons b (cons c '())))))
 
(define time (lambda (list) (car list)))
(define xpos (lambda (list) (car (cdr list))))
(define ypos (lambda (list) (car (cdr (cdr list)))))
 
(define N-read
  (lambda (n)
    (if (= n 0) '()
        (let* ((first (read))
               (second (read))
               (third (read))
               (element (time-and-position first second third)))
          (cons element (N-read (- n 1)))))))
 
(define canmove?
  (lambda (t-pos1 t-pos2)
    (let ((move-dis (+ (abs (- (xpos t-pos1) (xpos t-pos2)))
                       (abs (- (ypos t-pos1) (ypos t-pos2)))))
          (move-time (+ (abs (- (time t-pos1) (time t-pos2))))))
      (and (<= move-dis move-time)
           (= (modulo move-dis 2) (modulo move-time 2))))))
 
(define check
  (lambda (list)
    (cond ((null? list) "Yes")
          ((null? (cdr list)) "Yes")
          ((canmove? (car list) (car (cdr list)))
           (check (cdr list)))
          (#t "No"))))
 
;'(0 0 0)という初期状態を忘れずに！
(display (check (cons '(0 0 0) (N-read N))))
(newline)

無事なんとか、Scheme(Lisp)で初級問題を解ききることができました。
難しい問題も解いていかなければ・・・苦手なグラフとかも・・・
あと、カリー化などちゃんと勉強して、よりエレガントなコードを書けるように頑張っていきたいです。
ひとまずこれ読まなきゃ。

おわり。