AtCoder Beginner Contest 169に出ました(4完) - プログラミングを上達させたい

Ratedなコンテストに出場。今年2度目。

結果としては4完、ただ4つめに解けた問題であるD問題でアホみたいに何回もTLEとWAを連発してしまい、4問目までの解答時間は139分とコンテスト時間より長くなった・・・(ACしたのは89分＋C問題1回WA＋D問題3回WA＋D問題6回TLE)

あと、今回は大きい数が出てくる問題ばかりだったので、全てSchemeで解きました。えへへ

atcoder.jp

A問題

普通にかけ算。

(define a  (read))
(define b (read))
(display (* a b))
(newline)

AtCoderの問題ページの解答欄に直で書き込み、開始35秒でAC。
ただそれでも全然はやい方じゃなかった。どういう戦い？

B問題

普通に頭からかけ算していって、もし10^18を超えたらその時点で計算終了。
ただし、入力に一個でも0が入っている場合は0になる。
入力例3が優しい。なかったら確実にWAしてた。

(define m (read))
(define (read-n n)
  (if (= n 0) '()
      (cons (read) (read-n (- n 1)))))
 
(define (have-zero? list)
  (if (null? list) #f
      (or (= 0 (car list)) (have-zero? (cdr list)))))
 
(define (multi-list list)
  (define (sub lis now)
    (cond ((null? lis) now)
          ((> now 1000000000000000000) -1)
          (#t (sub (cdr lis) (* now (car lis))))))
  (let ((value (sub list 1)))
    (cond ((have-zero? list) 0)
          ((> value 1000000000000000000) -1)
          (#t value))))
 
(display (multi-list (read-n m)))
(newline)

20分くらい手間取った。
Schcmeではfloorで簡単に切り捨てができるが、なぜか"217.0"という風に、".0"がついてきてしまう。
あと、整数でなく有理数として大きい数が出ると、e+10みたいな表記法になってしまう。
それらを克服するため、結局floor関数は使わず、
a * (b * 100)を100で割る、という流れにした。また、b*100は普通にやっても".0"が残るので、文字列に変換して処理したりした。
少ない行数だがやっていることは面倒くさい。

(define a (read))
(define b (string-append (number->string (read)) "00"))
(define bdash (string->number (string-append (substring b 0 1) (substring b 2 4))))
(display (quotient (* a bdash) 100))
(newline)

D問題

これは
①素因数分解する
②素因数の累乗回数から、その素因数から何個の異なる数字を作れるか計算し足していく
という方針。
②に関しては、累乗回数が3になったとき初めて2個作れる(1乗と2乗)、6になったとき3個(1乗と2乗と3乗)、、、と、つまりn番目の三角数を超えるかどうかで判定すればよい。
また、入力が素数の場合は答え= 1。

まずはそれを踏まえて愚直に書いた、TLEした解答から。

(define a (read))
 
(define (div-count n d)
  (if (> (modulo n d) 0) 0
      (+ 1 (div-count (quotient n d) d))))
 
(define (score n)
  (define (sub i sum)
    (if (> sum n) 0
        (+ 1 (sub (+ i 1) (+ sum i 1)))))
  (sub 1 1))
  
(define (div-sho n d)
  (if (> (modulo n d) 0) n
      (div-sho (quotient n d) d)))
 
(define (prime? n)
  (define (sub i)
    (if (> (* i i) n) #t
        (if (= (modulo n i) 0) #f (sub (+ i 1)))))
  (cond ((= n 1) #f)
        ((= n 2) #t)
        (#t (sub 2))))
 
(define (solve n)
  (define (sub num i ans)
    (cond ((= num 1) ans)
          ((= (modulo num i) 0)
           (sub (div-sho num i) (+ i 1) (+ ans (score (div-count num i)))))
          (#t (sub num (+ i 1) ans))))
  (cond ((= n 1) 0)
        ((prime? n) 1)
        (#t (sub n 2 0))))
 
(display (solve a))
(newline)

提出したところ、2206msでTLE・・・
でも、これを1.1倍速にしたらええんやろって何回も提出(これがよくなかった)。
具体的には
・素数の判定で試しに割る数を、"root(n)以下の全ての数"じゃなくて"2、3以降の全ての奇数"に変える
・solveの中で割れるか試す数も、1個飛ばしにする
などやっていたのですが、全て2206msでTLE・・・

TLEが毎回同じ2206msなのに疑問を持ち、質問してみたところ、「制限時間を大きく上回ってしまった場合は制限時間の1.1倍程度でジャッジが打ち切られる仕様になっております」との回答が。
というわけで、このタイミングで大幅に方向転換する考え方に変更。

多分、入力が "3 * ばかでかい素数"とかのときに遅くなるなぁということで、素因数を見つけた後に、残った数が素数がチェックするようにコードを変更し、無事AC。
実行時間も66msと一気にスピードアップ。

(define (div-count n d)
  (if (> (modulo n d) 0) 0
      (+ 1 (div-count (quotient n d) d))))
 
(define (score n)
  (define (sub i sum)
    (if (> sum n) 0
        (+ 1 (sub (+ i 1) (+ sum i 1)))))
  (sub 1 1))
  
(define (div-sho n d)
  (if (> (modulo n d) 0) n
      (div-sho (quotient n d) d)))
 
(define (prime? n)
  (define (sub i)
    (if (> (* i i) n) #t
        (if (= (modulo n i) 0) #f (sub (+ i 2)))))
  (cond ((= n 1) #f)
        ((= n 2) #t)
        ((= n 3) #t)
        ((= 0 (modulo n 2)) #f)
        (#t (sub 3))))
 
(define (solve n)
  (define (sub num i)
    (cond ((= num 1) 0)
          ((= (modulo num i) 0)
           (+  (score (div-count num i)) (let ((nextnum (div-sho num i)))
                                           (if (prime? nextnum) 1 (sub (div-sho num i) (+ i 2))))));これを追加した
          (#t (sub num (+ i 2)))))
  (cond ((= n 1) 0)
        ((prime? n) 1)
        (#t (+ (score (div-count n 2)) (sub (div-sho n 2) 3)))))
 
(display (solve (read)))
(newline)

ProjectEulerをSchemeで解きまくっていたおかげか、思考をコードにするのは全く手間取らず、純粋に考える時間を多く取ることができました。
やってきてよかった。
今後はTLEになったときに上記のような判定があることも踏まえて、基本的に"大きく改善"を目指すように頑張りたい。

終わり！！！！

P.S. パフォーマンス929、新レーティングは1220(-31)