読者です 読者をやめる 読者になる 読者になる

SchemeでABC

SICPゼミで前々からSchemeで競プロの問題を解いてみようみたいな話があったので暇つぶしにちょっとやってみた。
今回はABC036のA問題とB問題
abc036.contest.atcoder.jp

A問題

int二つとって割り算して切り上げてねみたいな問題。
Schemeはintで割り算すると分数とかいう斬新なものが返ってくる仕様なので先に割り切れるように調整してから割り算してやる。
入力は二つだけなので(read)を二つ書けばOK。

(define a (read))
(define b (read))
(define (ans a b)
  (if (= (remainder b a) 0)
      (/ b a)
      (+ (/ (- b (remainder b a)) a) 1)))
(display (ans a b))
(newline)

一応

(/ (+ b (- a (remainder b a))) a)

とかやれば分岐いらなさそうだけどまぁ誤差ということで。

B問題

N×Nの行列が与えられるのでそれを90度回転させて出力するという問題。
とりあえずフルのコード。

;ゼミから転用
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence )))))
(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) nil sequence ))
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))
(define (transpose mat)
  (accumulate-n cons nil mat))
(define (reverse l)
  (if (= (length l) 1)
    (list (car l))
    (append (reverse (cdr l)) (list (car l)))))
(define nil '())

;入力を1行ずつn行読み取ってリストに
(define (read-lines n)
  (if (= n 1)
      (list (read))
      (append (list (read)) (read-lines (- n 1)))))

;1行ずつのstringをlist構造に変換して行列(2重のリスト構造)に
(define (linesToMatrix lines)
  (accumulate 
    (lambda (x y) (append (list (string->list (x->string x))) y)) nil lines))

;行列の各行をひっくり返してstringに戻す
(define (make-reverse-matrix matrix)
  (accumulate 
    (lambda (x y) (append (list (list->string (reverse x))) y)) nil matrix))

;listを末尾から出力
(define (print-list ls)
  (map (lambda (x) (display x) (newline)) ls))

;実際の入力に対する処理
(define n (read))
(define lines (read-lines n))
(define matrix (linesToMatrix lines))
(define ans (transpose matrix))
(define answer (print-list (reverse (make-reverse-matrix ans))))

方針としては、受け取った行列を転置させて各行をreverseさせましょうみたいな感じ。
accumulate、accumulate-n、transposeなどは
sicp-zemi.hatenablog.jp
でやったので簡単に行けるだろうと思ったんだが入力をリストに変換するやり方がわからなくて苦労した(終わってみれば簡単そうに見えるんだけど)。
あとlistを1つずつ出力するとなると普通にやると末尾からの出力になってしまう(再帰で掘ってくるから)ので一旦reverseしてから出力した。mapにしてるのでundefのリストが返るだけでエラーが出ないのがミソ。
もっともn番目の要素を出力するみたいな組み込みがあるみたいだからそれを使えばiterativeに表示できるんだろうけど。