競技プログラミングサイトAtCoder にて、「初心者の方はまずこの問題を解いてみよう!」という趣旨の
AtCoder Beginners Selection - AtCoder Beginners Selection | AtCoder
というページが出来ていました。
最近全然プログラミングやってなかったのと、図書館で借りたこの本
を読んでテンションがあがっていたのもあり、Schemeで問題を解いていくことにしました。
11問あるんですが、今回は一旦7問目まで。
1問目
PracticeA: はじめてのあっとこーだー(Welcome to AtCoder) - AtCoder Beginners Selection | AtCoder
Schemeでの標準入出力のやり方の確認、って感じですね。
(newline) を忘れずに。
(define a (read)) (define b (read)) (define c (read)) (define w (read)) (display (+ a b c)) (display " ") (display w) (newline)
2問目
ABC086A: Product - AtCoder Beginners Selection | AtCoder
if文が出てきます。
(define a (read)) (define b (read)) (display (if (= 0 (modulo (* a b) 2)) "Even" "Odd")) (newline)
3問目
ABC081A: Placing Marbles - AtCoder Beginners Selection | AtCoder
入力を数字として処理してます。
(define s (read)) (define one? (lambda (a) (= a 1))) (define addOneIfOne (lambda (a) (if (one? a) 1 0))) (define (num1count string counter) (if (< string 10) (+ counter (addOneIfOne string)) (num1count (quotient string 10) (+ counter (addOneIfOne (modulo string 10)))))) (display (num1count s 0)) (newline)
4問目
ABC081B: Shift only - AtCoder Beginners Selection | AtCoder
N個の数字の入力、というのが出てきます。
それに関しては、今回の回答で作った、これが自然な書き方かと思います。
;read N-elements-list (define read_list (lambda (n) (if (= n 0) '() (let* ((element (read))) (cons element (read_list (- n 1)))))))
リストとして入力してますが、"list->vector"という関数で配列にも簡単に変換できます。
しかし、カリー化?のやり方が思い出せず・・・面倒なので無理矢理書きました。
"list_min_check"という関数の引数として、ずっと"func"があるのダサいですよね。復習しなきゃ。
(define N (read)) ;read N-elements-list (define read_list (lambda (n) (if (= n 0) '() (let* ((element (read))) (cons element (read_list (- n 1))))))) (define kaijo_check2_sub (lambda (n count) (if (= 1 (modulo n 2)) count (kaijo_check2_sub (quotient n 2) (+ count 1))))) (define kaijo_check2 (lambda (n) (kaijo_check2_sub n 0))) (define list_min_check (lambda (init_or_min list func) (if (null? list) init_or_min (let ((car_val (func (car list))) (cdr_list (cdr list))) (if (> init_or_min car_val) (list_min_check car_val cdr_list func) (list_min_check init_or_min cdr_list func)))))) ;funcをカリー化?するやつどうやるんやっけ (display (list_min_check 50 (read_list N) kaijo_check2)) (newline)
5問目
ABC087B: Coins - AtCoder Beginners Selection | AtCoder
候補を生成して総当たり、で書きました。
;総当たり (define A (read)) (define B (read)) (define C (read)) (define X (read)) (define first (lambda (list) (car list))) (define second (lambda (list) (car (cdr list)))) (define third (lambda (list) (car (cdr (cdr list))))) (define sum (lambda (list) (+ (* 500 (first list)) (* 100 (second list)) (* 50 (third list))))) (define add1_nth_element (lambda (list n) (if (= n 1) (cons (+ 1 (car list)) (cdr list)) (cons (car list) (add1_nth_element (cdr list) (- n 1)))))) (define next_list (lambda (list) (if (< (third list) C) (add1_nth_element list 3) (if (< (second list) B) (cons (first list) (cons (+ (second list) 1) (cons 0 '()))) (if (< (first list) A) (cons (+ (first list) 1) '(0 0)) '()))))) (define answer (lambda (list counter) (if (null? list) counter (let ((next (next_list list))) (if (= (sum list) X) (answer next (+ counter 1)) (answer next counter)))))) (display (answer '(0 0 0) 0)) (newline)
6問目
ABC083B: Some Sums - AtCoder Beginners Selection | AtCoder
こちらも、全部試す作戦で。
;総当たり (define N (read)) (define A (read)) (define B (read)) (define sum_kaku_keta (lambda (num count) (if (< num 10) (+ count num) (sum_kaku_keta (quotient num 10) (+ count (modulo num 10)))))) (define ketawa (lambda (num) (sum_kaku_keta num 0))) (define check_clear (lambda (num) (let ((sum_keta (ketawa num))) (and (<= A sum_keta) (>= B sum_keta))))) (define counter (lambda (list count) (if (null? list) count (let ((cd (cdr list)) (cr (car list))) (if (check_clear cr) (counter cd (+ count cr)) (counter cd count)))))) (define list_1_to_n (lambda (a b) (if (> a b) '() (cons a (list_1_to_n (+ a 1) b))))) (display (counter (list_1_to_n 1 N) 0)) (newline)
7問目
ABC088B: Card Game for Two - AtCoder Beginners Selection | AtCoder
この問題が入った意図としては、「配列の操作(今回だとソート)」をさせるためでしょうか?
(define N (read)) ;Nがたいして大きくないので挿入ソートで。大きい順ね。 (define insert (lambda (element list) (cond ((null? list) (cons element '())) ((>= element (car list)) (cons element 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)))))) (define sum_two (lambda (alice bob list switch) (cond ((null? list) (- alice bob)) ((= switch 1) (sum_two (+ alice (car list)) bob (cdr list) 2)) (#t (sum_two alice (+ bob (car list)) (cdr list) 1))))) (display (sum_two 0 0 (read_insert_sort '() N) 1)) (newline)
ひとまず解いたところまで。
久々にやると楽しい!!!
カリー化的なことが綺麗に書けない(し、それを気にせず汚く書ける)あたり、
まだ関数型言語脳になってるわけではないのでしょう。
頑張りたいところやでホンマ。
あと、これも読まなきゃ。
というわけで、下記の後編に続きます。
frfrfrfr.hatenablog.com