プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

Lisp(Scheme)で書く、重複を許した組み合わせ(AtCoderBeginnerContest114 C問題)

久々の投稿です。
水色になってから全然AtCoder出られておらず、また勉強もできていないです。
水色になったものの、本当に"ギリギリ水色になれるレベル"である実感があるので、勉強していかないと青は無理そうです。
ということでAtCoder Beginner Contest 114を、(何故かそういう気分だったので)Schemeで解くことにしました。
abc114.contest.atcoder.jp

何の記事なんだよ!!コレは!!

この記事ではこのC問題で必要となった"「重複を許した組み合わせ」をSchemeで記述する"ことについて書きます。


せっかくなので、ついでにA問題とB問題の解答も書きます。

A問題

A: 753 - AtCoder Beginner Contest 114 | AtCoder

(define n (read))
(display (if (or (= n 3) (= n 5) (= n 7)) "YES" "NO"))
(newline)

B問題

B: 754 - AtCoder Beginner Contest 114 | AtCoder

(define n (read))
 
(define (abs1 n) (if (< n 0) (- 0 n) n))
 
(define (solve num ans)
  (if (< num 100) ans
      (let* ((kouho (modulo num 1000))
             (sa (abs1 (- kouho 753)))
             (nextnum (quotient num 10)))
         (if (< sa ans) (solve nextnum sa)
             (solve nextnum ans)))))
      
(display (solve n 10000))
(newline)

A問題、B問題ともに、問題の要請を素直に記述しました。

本題だよ!!!聞いてんのか!!!

まずはこのC問題自体について。

C: 755 - AtCoder Beginner Contest 114 | AtCoder

入力される数字が10^9までということで、全チェックでは間に合わなさそうです。
ただ、入力例3を見てみると「この問題でありうる最も大きい答え」が高々5桁であることが分かります。
そこから、そもそもこの“七五三数”の候補を、“N(<=1000000000)以下の全ての数”から減らせないか…?と考えると、
調べる数を“0,3,5,7のみで構成された9桁の数”で考えて良いことに気付きます。
0が入っているのは、9桁より小さい数も一緒に扱うためです。例えば、3575は000003575として扱います。
これだと、高々4^9=約25万個の数を調べればよいということになります。

重複組合せの記述

せっかくSchemeで書いてるので、この数をリストで表したいところです。
例えば003535777は(0 0 3 5 3 5 7 7 7)という感じです。
として、桁の数=9と要素のリスト=(0 3 5 7)を引数として渡す関数を作り、
(generator 9 (0 3 5 7))として、候補の数のリストが生成されるようにしたいです。

↓その関数の挙動イメージ

> (generator 2 (1 2))
((1 1) (1 2) (2 1) (2 2))

> (generator 9 (0 3 5 7))
((0 0 0 0 0 0 0 0 0)
 (0 0 0 0 0 0 0 0 3)
....
 (7 7 7 7 7 7 7 7 5)
 (7 7 7 7 7 7 7 7 7))

書いてみると、最終的にこんな感じになりました。
※一番下の"p-generate"が該当する関数です

;要素と"リストのリスト"を掛け合わせる関数
(define (e-l ele lislis)
  (if (null? lislis) '()
      (cons (cons ele (car lislis)) (e-l ele (cdr lislis)))))
 
;リストと"リストのリスト"を掛け合わせる関数
(define (multi-list listA listB)
  (if (null? listA) '()
      (append (e-l (car listA) listB) (multi-list (cdr listA) listB))))
 
;サブ用の関数
(define (p-list count base ans)
  (if (= count 0) ans
      (p-list (- count 1) base (multi-list base ans))))
 
(define (p-generate count list)
  (p-list count list '(())))

これで重複組み合わせが書けたことになります。やはり再帰があると書きやすいですね。
(p-generate 9 '(0 3 5 7))をAtCoderのコードテスト上で動かしてみると200~400msで全ての候補を出力完了しました。

これと同じように、順列、組み合わせも書けるとかなり便利そうです。
こちらのサイトで勉強しようと思います。
以上です。
最後に、このC問題の解答の全体を載せて終わりとします。

(define upper (read))
 
(define (e-l ele lislis)
  (if (null? lislis) '()
      (cons (cons ele (car lislis)) (e-l ele (cdr lislis)))))
 
(define (multi-list listA listB)
  (if (null? listA) '()
      (append (e-l (car listA) listB) (multi-list (cdr listA) listB))))
 
(define (p-list count base ans)
  (if (= count 0) ans
      (p-list (- count 1) base (multi-list base ans))))
 
(define (p-generate count list)
  (p-list count list '(())))
 
(define (numgenerate list)
  (define (sub lis num)
    (if (null? lis) num
        (sub (cdr lis) (+ (* num 10) (car lis)))))
  (sub list 0))
 
;ゼロは左端から見ていって左端から連続で出ている場合のみOK
;例えば"000575733"はOKだが、"000305755"はアウト
(define (zero-check list)
  (define (sub lis sum)
    (cond ((null? lis) #t)
          ((and (= (car lis) 0) (> sum 0)) #f)
          (#t (sub (cdr lis) (+ sum (car lis))))))
  (sub list 0))
 
;3,5,7が全部1回以上出ているかのチェック
(define (check357 list)
  (define (sub lis c3 c5 c7)
    (if (null? lis) (and c3 c5 c7)
        (let ((ele (car lis))
              (cd (cdr lis)))
          (cond ((= ele 3) (sub cd #t c5 c7))
                ((= ele 5) (sub cd c3 #t c7))
                ((= ele 7) (sub cd c3 c5 #t))
                (#t (sub cd c3 c5 c7))))))
  (sub list #f #f #f))
 
(define (check numlist)
  (and (<= (numgenerate numlist) upper) (zero-check numlist) (check357 numlist)))
 
(define (solve list ans)
  (if (null? list) ans
      (if (check (car list)) (solve (cdr list) (+ ans 1))
          (solve (cdr list) ans))))
 
(display (solve (p-generate 9 '(0 3 5 7)) 0))