引き続き、生活に余裕があるときはAtCoderに取り組んでいます。この前あったヒューリスティックコンテストも出たかったのですが、スケジュールが合わず・・・
無理なくやれる範囲でやっていきます。
さて、今回解いていたのはこの問題です。
atcoder.jp
300点問題。答えが意外とでかくなるケースがあり、答えの候補を2,3,4...と探していくとTLEになってしまうという問題です。最大になってしまう場合というのは数列X内に50以下の全ての素数が出てくるケースで、その場合は2,3,5,,,41,47という50以下の素数(15個)をすべてかけた数が正解となり、6*10^17くらい大きくなります。よって候補を制限せずの全探索ではアウトですね。
この場合は、答えの候補として「50以下の素数のうちいくつか(1個のみ〜全部)を掛け合わせたものたち」に絞れば十分ということになります。これをSchemeで解く際に、色々トライしてみたので、その記録を残します。
combinationを使う
Schemeで問題を解く時にこれまでも重複を許した組み合わせとかでうまいこと解けたりしたので、今回もそんな感じでできないかなぁと画策しました。
表現として、
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 2) ;これで2を表す (1 1 1 1 1 1 1 1 1 1 1 1 2 5 11) ;これで2*5*11=110を表す
みたいな作戦です。
流れとしては
(define Plist '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)) (combination-list 14 Plist) ;これで必要なパターン生成
という感じ。
実装してみました。上記のPlistも、一応汎用的な形で使えるような関数で書きました。
(define (all-combinations set seed) (define (add-list ele count list) (if (= count 0) list (add-list ele (- count 1) (cons ele list)))) (let* ((setsize (length set)) (newset (add-list seed (- setsize 1) set))) (combinations-list setsize newset))) (define (combinations-list n ls) (define (comb n ls a b) (cond ((= n 0) (cons (reverse a) b)) ((pair? ls) (comb (- n 1) (cdr ls) (cons (car ls) a) (comb n (cdr ls) a b))) (else b))) (comb n ls '() '())) (display (all-combinations '(2 3 5) 1)) ;((1 1 2) (1 1 3) (1 1 5) (1 2 3) (1 2 5) (1 3 5) (1 2 3) (1 2 5) (1 3 5) (2 3 5))
実際にテストとして実行してみた結果を上記の最後の行のコメントとして書いているのですが、残念なことに"(1 2 5)"とかが2個ずつある・・・
複数ある"1"を区別しているため、結局重複がガンガンにある形となってしまいました。。。残念。
というわけで、別の作戦に移ります。ちゃんと「複数個の候補からn個ピックアップ、をn=1〜全部 でやる」ようなコードを書きます。
関数 「number->string」 を利用する
そういえばこれまで使った関数として number->string というものがありました。
これは、引数1個だと普通に数字を文字列に変え、引数2つだと2つ目の引数をnとしたときに「1つ目の引数をn進数で表したときの文字列」を返してくれるものです。
(number->string 3) ;"3" (number->string 3 2) ;"11"
これを使えばきれいに書けるんちゃうんか！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
やってみます。
下準備として、「長さnの0と1で作られた文字列」と「リスト」を取り、「文字列でi番目が1だったらリストのi番目の要素は残す」という関数を作ります。
(define (pick-up booleanlist elelist) (let ((strlen (string-length booleanlist))) (if (or (= strlen 0) (null? elelist)) '() (if (char=? #\1 (string-ref booleanlist 0)) (cons (car elelist) (pick-up (substring booleanlist 1 strlen) (cdr elelist))) (pick-up (substring booleanlist 1 strlen) (cdr elelist)))))) ;> (pick-up "11010" '(2 3 5 7 11)) ;(2 3 7)
あとは、例えば上記の(2 3 7)を2*3*7に直し、それが条件を満たすかをチェックしていけばよいということになります。
この方針で実装し、無事ACしました。最終的なコードはこんな感じです。
(define N (read)) (define (readN n) (if (= n 0) '() (let ((ele (read))) (cons ele (readN (- n 1)))))) (define (pick-up booleanlist elelist) (let ((strlen (string-length booleanlist))) (if (or (= strlen 0) (null? elelist)) '() (if (char=? #\1 (string-ref booleanlist 0)) (cons (car elelist) (pick-up (substring booleanlist 1 strlen) (cdr elelist))) (pick-up (substring booleanlist 1 strlen) (cdr elelist)))))) (define (check ele list) (if (null? list) #t (and (> (gcd ele (car list)) 1) (check ele (cdr list))))) (define (make-num list) (if (null? list) 1 (* (car list) (make-num (cdr list))))) (define Plist '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)) (define two15 (* 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)) (define (appendto15 str) (if (>= (string-length str) 15) str (appendto15 (string-append "0" str)))) (define (solve list) (define (sub i ans) (if (= i two15) ans (let ((nownum (make-num (pick-up (appendto15 (number->string i 2)) Plist)))) (if (and (check nownum list) (< nownum ans)) (sub (+ i 1) nownum) (sub (+ i 1) ans))))) (sub 1 (make-num Plist))) (display (solve (readN N))) (newline)
注意としては、上記の「pick-up」関数の書き方だと、引数booleanlist(listと言いつつ文字列です)の長さが足りてない場合でもエラーなく動いてしまいます。また、booleanlistの長さまでしかチェックしないため、booleanlistが"1100"でも"110000"でも同じ答えを返してしまいます。
よって、「appendto15」という「生成した文字列を右詰にする&文字数が足りないなら左に0を足す」関数を追加で作りました。
この「pick-up」関数は今後も使えそうなので、マイお気に入り関数として保存しておこうと思います！
以上、300点問題にかなり手こずった記録でした。
