京都大学プログラミングコンテストを全部schemeで解こう(A,B)

久しぶりの投稿です。
最近はあまり時間がとれてないので(忙しいわけではなく、やる気が出ない)、前からかなり空いちゃいました。

さて、先日(7/5)に京都大学プログラミングコンテスト2014がありました。
せっかくなので参加してみました。

難しい問題ばかりなので、ほとんど点数はとれなかったのですが、面白そうな問題ばっかりでした。
ゆっくり時間をかけてでも全部解けば相当実力がつくのでは・・・？ということで、ゆっくりゆっくりやってみようと思います。
しかもなるたけ、schemeで。

さて、やっていきましょう。
まずはA問題です。
簡単なやつですね。
マッサージチェア、学生の座標を小さい順に並べて、差の和をとる。

(define (insert ele list)
  (cond ((null? list) (cons ele list))
        ((<= ele (car list)) (cons ele list))
        (#t (cons (car list) (insert ele (cdr list))))))
 
(define (input-and-sort count)
  (if (= count 0) '()
      (let* ((inp (read)))
        (insert inp (input-and-sort (- count 1))))))
 
(define list1 (input-and-sort 3))
(define list2 (input-and-sort 3))
 
(define (solve lis1 lis2 ans)
  (if (null? lis1) ans
      (solve (cdr lis1) (cdr lis2) (+ ans (abs (- (car lis1) (car lis2)))))))
 
(display (solve list1 list2 0))
(newline)

次はB問題です。
これ、面白いですね。今までのAtcoderの問題とちょっと違う感じ。
本番はJavaで解きましたが、ここではschemeでやってみました。

(define kouho (make-vector 1001 #t))
(vector-set! kouho 0 #f)

(define (true-update! n)
  (define (sub num index)
    (if (<= index 1000)
        (let ((tf (if (= (modulo index num) 0) #t #f)))
          (begin
            (vector-set! kouho index tf)
            (sub num (+ index 1))
            ))))
  (sub n 1))

(define (false-update! n)
  (define (sub i index)
    (if (<= (* i index) 1000)
        (begin
          (vector-set! kouho (* i index) #f)
          (sub i (+ index 1))
          )))
  (sub n 1))

(define (update-kouho)
  (define (sub n)
    (cond ((> n 1000))
          ((vector-ref kouho n)
           (begin
             (display "? ")
             (display n)
             (newline)
             (let* ((res (read)))
               (if (or (eq? res 'y) (eq? res 'Y))
                   (begin
                     (true-update! n)
                     (sub (+ n 1))
                     )
                   (begin
                     (false-update! n)
                     (sub (+ n 1))
                     )))))
          (#t (sub (+ n 1)))))
  (sub 1))

(update-kouho)

(define (solve)
  (define (sub n)
    (if (vector-ref kouho n)
         n
        (sub (- n 1))))
  (sub 1000))

(display "! ")
(display (solve))
(newline)

方針としては、
まず、長さ1000の配列を作って(やりやすさ上、1001ですが)、全部にtrueを入れます。
そして、まず1で割り切れるかどうかを聞いて、もちろん'Y'が返ってきます。
次に、2で割り切れるかどうかを聞いて、
・割り切れるなら2の倍数でないところをfalseに
・割り切れないなら2の倍数のところをtrueに
配列を更新します。
次に、2の次を見ていって、
・そこがfalseなら飛ばして
・trueなら、2でやったときと同じような更新をして
いきます。
んで、1000まで見終わったら、配列を1000から、つまり大きい方から見ていって、初めてtrueだったやつが答えです。
これだと、制限である質問回数(=200回)もクリアできますね。
出してみると、ちゃんとACでした。よかったよかった。

さて、今回はここまでです。ちゃんと最後まで解ききれるといいなぁ。
実力orモチベーション的に途中でやめちゃいそうな気もするけど、なんとか頑張りたいものです。