前の記事の続きです。
相変わらずSchemeで解きました。解けました。よかった。
ただ、数学的に難しくてもアルゴリズムや実装的に難しいわけではなかったのだから解けたのだと思います。
Schemeで配列を書くのがまだ上手くできないんですよね・・・リストでごまかしていますが、限界がありますし。
解いた問題
コレです
abc114.contest.atcoder.jp
(define N (read)) (define (genenum start end) (if (= start end) (cons end '()) (cons start (genenum (+ start 1) end)))) ;1〜nの中の素数のリストを返す関数 (define (sosulist n) (define (furui list) (define (delete ele list) (if (null? list) '() (if (= 0 (modulo (car list) ele)) (delete ele (cdr list)) (cons (car list) (delete ele (cdr list)))))) (if (null? list) '() (cons (car list) (furui (delete (car list) list))))) (furui (genenum 2 n))) (define (primehavecount prime n) (if (> (modulo n prime) 0) 0 (+ 1 (primehavecount prime (quotient n prime))))) ;N!が各素数を何個ずつ含むか返す関数 (define (havesosu n) (define (sosucount prime nlist) (if (null? nlist) 0 (+ (primehavecount prime (car nlist)) (sosucount prime (cdr nlist))))) (define (sub primelist nlist) (if (null? primelist) '() (cons (sosucount (car primelist) nlist) (sub (cdr primelist) nlist)))) (sub (sosulist n) (genenum 2 n))) (define (tolist n) (genenum 1 (+ n 1))) (define (listtolistlist list) (if (null? list) '() (cons (tolist (car list)) (listtolistlist (cdr list))))) (define (divisorcounters n) (listtolistlist (havesosu n))) ;startは(1 1)=1になるのが1通り から始めるとして ;anslistは(1 1) elelistは(1 2 3)のような想定 ;リスト×リストを計算する関数 ;無駄を省くため、75を超えたもの、偶数(=何をかけても75にならない)はカットする (define (multi-list anslist elelist) (if (null? elelist) '() (if (or (> (* (car anslist) (car elelist)) 75) (= 0 (modulo (* (car anslist) (car elelist)) 2))) (multi-list anslist (cdr elelist)) (cons (cons (* (car anslist) (car elelist)) (cdr anslist)) (multi-list anslist (cdr elelist)))))) (define (multi-ll-l ansll elelist) (if (null? ansll) '() (append (multi-list (car ansll) elelist) (multi-ll-l (cdr ansll) elelist)))) ;リスト×リストを返す関数 (define (multi-ll-ll ansll elell) (if (null? elell) ansll (multi-ll-ll (multi-ll-l ansll (car elell)) (cdr elell)))) (define (yakusuucounters n) (multi-ll-ll '((1 1)) (divisorcounters n))) (define (count75 ll) (if (null? ll) 0 (let ((thisdiv (car (car ll)))) (+ (if (= thisdiv 75) 1 0) (count75 (cdr ll)))))) (define (ans n) (count75 (yakusuucounters n))) (display (if (= N 1) 0 (ans N))) (newline)