AtCoder Beginner Contest 205に出ました - プログラミングを上達させたい

少し間が空きましたが、Ratedなコンテストに出ました。
atcoder.jp
典型90問を少しずつ解いていますが、今はまだ「自分のレベルで考えたら解けるもの」しか解いていません(といっても数十分考えたりはする)。
よって、ややこしく大きめなコードを書くスピードは少し上がったものの、解ける問題が本質的に増えたかというと微妙な感じです。
そんななか向かえたBeginner Contest。どうなるのか。
速く解くしかない。

→結果、4完(33分)でした。A〜D解いたあとにE問題に取り組むもオーダーを落とす方法が分からず・・・悔しい。
というわけで、コードおよび考え方を書いていきます。
全てScheme(racket)で解きました。最近、2次元配列が出てこない限りはSchemeが一番書きやすいという状態です。

A問題

かけ算と割り算をして、ちゃんと小数で出しましょうという問題。
普通に / で割り算するとSchemeの場合は分数になってしまうので、exact->inexact で小数に変換します。

#lang racket
(define A (read))
(define B (read))
(display (exact->inexact (* B (/ A 100))))
(newline)

B問題

N個の数からなる数列の中に、1〜Nが1個ずつ入ってるか確認する問題。

#lang racket
(define N (read))
(define NUMS (make-vector N 0))
(define (readN n)
  (if (= n 0) '()
      (let ((ele (- (read) 1)))
        (cons ele (readN (- n 1))))))
(define (update numlist)
  (if (null? numlist) #t
      (let* ((nownum (car numlist))
            (nowcount (vector-ref NUMS nownum)))
        (if (> nowcount 0) #f
            (begin
              (vector-set! NUMS nownum 1)
              (update (cdr numlist)))))))
(display (if (update (readN N)) "Yes" "No"))
(newline)

C問題

Cが偶数の場合は絶対値で、Cが奇数の場合はA,Bの大小をそのままでOKな問題。
ビビってCが奇数のときはなぜか A^3 と B^3を比較するコードにしました。コーナーケースありそうすぎて怖かったです。

#lang racket
(define A (read))
(define B (read))
(define C (read))
(display
 (let* ((absA (abs A))
        (absB (abs B))
        (A3 (* A A A))
        (B3 (* B B B)))
   (if (= 0 (modulo C 2));C=even
       (cond ((> absA absB) ">")
             ((< absA absB) "<")
             (#t "="))
       (cond ((> A3 B3) ">")
             ((< A3 B3) "<")
             (#t "=")))))
(newline)

D問題

数列の長さは10^5まであるものの、「数列に出現しないうちK番目の数」を出せというKは10^18までという問題。
数列に出現しない数たちを、数列の長さにのみ依存する形で保持したいです。
ここで、("出現しない数A" "Aから何個分連続で出現しないか" "これまで見てきた出現しない数の合計")という数字3つ組でデータを保持することを考えます。
つまり
数列→(4,6)
出現しない数の列→(1,2,3,5,7,8,9,10,,,,,,,)
保持の仕方→( (1 3 3) (5 1 4) (7 大きな数大きな数) )
ということです。
このように保持し、i番目のものを求めるときには数字3つ組の3番目に注目して二分探索を行うことで、Q * log N で計算できます。

#lang racket
(define N (read))
(define Q (read))
(define (readN n)
  (if (= n 0) '()
      (let ((ele (read)))
        (cons ele (readN (- n 1))))))
(define INP (list->vector (readN N)))
(define QUERY (readN Q))
 
(define (make-nouse-list)
  (define (sub start sum index)
    (if (>= index N) (list (list start 1000000000000000000 200000000000000000))
        (let ((usenum (vector-ref INP index)))
          (if (= start usenum)
              (sub (+ start 1) sum (+ index 1))
              (cons (list start (- usenum start) (+ sum (- usenum start)))
                    (sub (+ usenum 1) (+ sum (- usenum start)) (+ index 1)))))))
  (sub 1 0 0))
(define NOUSES (list->vector (cons (list 0 0 0) (make-nouse-list))));(display NOUSES)
(define NOUSESLEN (vector-length NOUSES))
(define (search ith)
  (define (sub left right)
    (if (= (- right left) 1)
        (let ((before-sum (third (vector-ref NOUSES left)))
              (newstart (car (vector-ref NOUSES right))))
          (+ newstart (- ith (+ before-sum 1))))
        (let* ((center (quotient (+ left right) 2))
               (centersum (third (vector-ref NOUSES center))))
          (if (<= ith centersum)
              (sub left center)
              (sub center right)))))
  (sub 0 (- NOUSESLEN 1)))
(define (solve q)
  (if (null? q) (display "")
      (begin
        (display (search (car q)))
        (newline)
        (solve (cdr q)))))
 
(solve QUERY)

4問目まではそこそこなスピードで解けましたが、果たしてパフォーマンスはどれくらいか・・・
あと、5問目の解説を見ると、上手な考察ができればスパッと解けていたようで、とても悔しいです・・・(といってもそれを思いつくのが簡単なわけではないですが)

解ける問題を増やすべく、典型90問の★5を一旦クリアするのを目標にします。
オーディションやらなんやらもあるけど、なんとか時間確保して頑張るぞー