久々の投稿です。
水色になってから全然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))
