ABC161D - Lunlun Numberを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 161 D - Lunlun NumberをCommon Lispで解いてみました。

問題文には特に難しいことは書いていません。
簡単に思いつく解き方としては、1から順番にルンルン数かどうかを判定していく方法があります。
しかし、入力例4で$K$が最大のときに$10^9$を超えるので間に合いません。他の解き方を考えます。

入力例1のルンルン数を眺めていると、親子関係があることに気が付きました。親が$1$、個が$10$と$11$、孫が$100$、$101$、$110$、$111$、$112$ということです。

親を元に子のルンルン数を追加する計算量は$O(1)$なので、間に合います。

(let* ((k (read))
       (lunlun (make-array (1+ k))))

  ;; ルンルン数の1~9を埋める
  (loop for i from 1 to (min k 9)
        do (setf (aref lunlun i) i))

  (when (> k 9)
    ;; ルンルン数の10~Kを埋める
    (loop with parent = 1
          with child  = 10
          while (<= child k)
          for lunlun-parent = (aref lunlun parent)
          for lunlun-parent-1 = (mod lunlun-parent 10)
          do (when (> lunlun-parent-1 0)
               ;; 親ルンルン数の1桁目が0より大きいとき
               (setf (aref lunlun child) (+ (* lunlun-parent 10)
                                            (1- lunlun-parent-1)))
               (incf child))

             (when (<= child k)
               (setf (aref lunlun child) (+ (* lunlun-parent 10)
                                            lunlun-parent-1))
               (incf child))

             (when (and (< lunlun-parent-1 9)
                        (<= child k))
               ;; 親ルンルン数の1桁目が9より小さいとき
               (setf (aref lunlun child) (+ (* lunlun-parent 10)
                                            (1+ lunlun-parent-1)))
               (incf child))
             ;; 次の親ルンルン数に進む
             (incf parent)))

  (format t "~A~%" (aref lunlun k)))
  

AtCoder Beginner Contest 483に参加しました

40代文系社内SEがAtCoder Beginner Contest 483に参加し、AB2完でした。

A - Double-Sided Printing

小数点切り上げの割り算の問題でした。

B - Flip Card Stack

カード枚数が$1 \le N \le 100$と小さいので、愚直に実装することで解けました。
裏向きの表現に少し戸惑いましたが、出力するときに負の数に変換するように指示されていたので、それを採用しました。

C - Second Choice Election

解けませんでした。

$k = 1, 2, 3, \ldots, N$ごとに得票数をカウントするのは計算量が$O(NM)$になり、間に合わないというところはわかりました。

誰も棄権しない場合の得票数から、棄権した場合の差分だけ計算する方向で考察を進めましたが、回答までたどり着けず。

コンテスト終了後に解説を見ると、考察の方向は間違っていなかったようです。誰も棄権しない状態で得票数2位の候補者を考慮に入れるところが、思いつきませんでした。

最近ブログに記事を投稿しているので成果が出ると嬉しかったのですが、まだまだ実力が足りないようです。

ABC165C - Many Requirementsを全探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 165 C - Many RequirementsをCommon Lispで解いてみました。

この問題で難しいところは、計算量を求めるところと数列を列挙するところです。

まず、計算量については$2 \le N \le 10$と、$1 \le M \le 10$から、最大$10^10$に見えますが、実はそこまで大きくなりません。数列の条件として昇順に並ぶことが記載されているため、先頭が$10$のときはすべて$10$の1通りになります。
具体的には重複組み合わせを使って数列のパターン数を求めることができ、最大$92378$通りとなります。

次に数列を列挙する処理については、以下のように実装します。

1. 数列の末尾が$M$未満なら加算する
2. 数列の末尾が$M$なら先頭に向かって$M$未満を検索する
3. $M$未満が見つかったらそれを加算し、末尾に向かってコピーする
4. すべてが$M$になったら終了する

毎回終了条件をチェックするので、数列1パターンあたりの計算量は$O(N)$です。

得点の計算を含めた計算量の最大値は$O(92378 \times 10 \times 50)$となり、間に合います。

(defun score (va q a b c d)
  (loop for i from 0 below q
        for ai = (aref a i)
        for bi = (aref b i)
        for ci = (aref c i)
        for di = (aref d i)
        when (= (- (aref va bi) (aref va ai)) ci)
          sum di))

(let* ((n (read))
       (m (read))
       (q (read))
       (a (make-array q))
       (b (make-array q))
       (c (make-array q))
       (d (make-array q))
       (va (make-array (1+ n) :initial-element 1)))

  ;; a, b, c, dを読み込む
  (loop for i from 0 below q
        do (setf (aref a i) (read)
                 (aref b i) (read)
                 (aref c i) (read)
                 (aref d i) (read)))
  (loop with ans = 0
        while (not (= n (count m va :start 1)))
        do (setf ans (max ans (score va q a b c d)))
             
           (if (< (aref va n) m)
               (incf (aref va n))
                 
               ;; 繰り上がり処理
               (let* ((i (position-if #'(lambda (ai) (< ai m))
                                      va
                                      :from-end t))
                      (vai (aref va i)))
                 (loop for j from i to n
                       do (setf (aref va j) (1+ vai)))))
        finally
           (format t "~A~%" (max ans (score va q a b c d)))))
  

解法やアルゴリズムで分類した、解いてみたリストはこちらです。
AtCoder Beginner Contestを解いてみたリスト

AtCoder Beginner Contest 482にUnratedで参加しました

40代文系社内SEが1時間遅れでAtCoder Beginner Contest 482に参加し、AB2完でした。
C問題も間に合わなかったものの、ACできました。

A - Nigiri

文字列中の文字を数え、偶数奇数の判定で解けました。

B - Blank Bingo

ビンゴになるタテヨコナナメについて愚直に調べて解けました。
実装が煩雑な問題でした。

C - Band Count

区間の個数を数える問題なので、まず二次元累積和が思い浮かびました。
しかし、$1 \le H,W \le 10^9$なのでTLEしそうです。

次に考えたのが、二分探索です。「クエリといえば二分探索」は自分の中のパターンの一つです。
クエリで指定されるのが、行番号と列番号なので、それらで二分探索できるように考えます。
行番号($R$)と列番号($C$)をそれぞれ配列に保存し、二分探索で下限と上限を求めることで解けました。

半年くらい参加していなかったのですが、参加者が4000人くらい減っていますね。

ABC088D - Grid Repaintingを幅優先探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 088 D - Grid RepaintingをCommon Lispで解いてみました。

この問題は、けぬす君がスタートからゴールまでたどり着けるかという迷路と、スコアを最大化するという二段構えになっています。

まず、迷路を解かなければならないので、深さ優先探索か幅優先探索が使えそうだと考えました。

次にスコアの最大化について考えると、幅優先探索を選択するべきだと考えました。
通過しなくてよいマスを白から黒に塗り替えることでスコアが得られ、それが最大になるのは最短経路を残して塗り替えたときだからです。
計算量は$O(HW)$です。

以上より、以下の手順で解きます。

1. 幅優先探索でスタートからゴールまでたどる。このときにスタートから各マスまでの移動回数を記録する。
2. ゴールまでたどり着けないときは、$-1$を出力して処理を終了する。
3. ゴールまでたどり着けたときは、グリッド全体の白マスをカウントし、ゴールまでの移動回数を引いた値を出力する。

(require :sb-concurrency)

(let* ((h (read))
       (w (read))
       (s (make-array h))
       (visiting (sb-concurrency:make-queue))
       (dist (make-array (list h w) :initial-element nil)))

  (loop for i from 0 below h
        do (setf (aref s i) (read-line)))

  (labels ((bfs ()
             (when (not (sb-concurrency:queue-empty-p visiting))
               (let ((current (sb-concurrency:dequeue visiting)))
                 (loop for direction in '((0 . 1) (1 . 0) (0 . -1) (-1 . 0))
                       for next = (cons (+ (car current) (car direction))
                                        (+ (cdr current) (cdr direction)))
                       when (and (<= 0 (car next) (1- h))
                                 (<= 0 (cdr next) (1- w))
                                 (char= (char (aref s (car next)) (cdr next)) #\.)
                                 (null (aref dist (car next) (cdr next))))
                         do (setf (aref dist (car next) (cdr next))
                                  (1+ (aref dist (car current) (cdr current))))
                            (sb-concurrency:enqueue next visiting))
                 (bfs)))))
    
    (setf (aref dist 0 0) 0)
    (sb-concurrency:enqueue (cons 0 0) visiting)
    (bfs)

    (let ((count-. (loop for si across s sum (count #\. si)))
          (dist-goal (aref dist (1- h) (1- w))))
      (format t "~A~%" (if (null dist-goal) 
                           -1
                           (- count-. (1+ dist-goal)))))))

解法やアルゴリズムで分類した、解いてみたリストはこちらです。
AtCoder Beginner Contestを解いてみたリスト

ABC177C - Sum of product of pairsを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 177 C - Sum of product of pairsをCommon Lispで解いてみました。

まず問題文を見ます。
数列$A$から数を2つ選んで掛け算をしてその合計を$10^9+7$で割った余りを求める問題です。
問題がシンプルで、計算量が$O(N^2)$になる全探索しかないように見えます。
$N \le 10^3$であれば間に合いますがどうか。

次に制約を見ます。
$N \le 2 \times 10^5$なので全探索では間に合いません。他の方法を考える必要があります。

出力例1の下にある式を眺めていると、式を変形できそうなことに気が付きました。
$A_i$でまとめると、以下のようになります。

$1 \times (2 + 3) + 2 \times (3)$

これは、$A_i \times A_{i+1}からA_Nまでの合計$になっています。
$A_{i+1}からA_Nまでの合計$は、最初に$A$全体の合計を計算しておき、そこから$A_i$を引くことで計算量$O(1)$で求められます。

以上より、以下の手順で解きます。

1. $A$の合計を計算する
2. $A$の合計から$A_1$を引く
3. $A_1$に$A$の合計をかけたものを答えに足す
4. 2、3を$A_{N-1}$まで繰り返す
5. 答えの剰余を計算して出力する

(let* ((n (read))
       (a (make-array n)))

  (loop for i from 0 below n
        do (setf (aref a i) (read)))

  (loop with sum-a = (reduce #'+ a)
        with answer = 0
        for i from 0 below (1- n)
        for ai = (aref a i)
        do (decf sum-a ai)
           (incf answer (mod (* ai sum-a) (+ (expt 10 9) 7)))
        finally
           (format t "~A~%" (mod answer (+ (expt 10 9) 7)))))
  

式を変形できることに気づいたことで解くことができました。

ABC146C - Buy an Integerを二分探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 146 C - Buy an IntegerをCommon Lispで解いてみました。

まず問題文を見ます。
1以上10の9乗以下の整数のうち、$A \times N + B \times d(N) \le X$を満たす最大の数$N$を求める問題です。
問題文の時点で1から順番に試していく方法は使えないことがわかります。
二分探索であれば、$O(\log N)$で間に合うので二分探索を使う方向で考えます。

次に制約をみますが、特に方針に影響はなさそうです。

問題文の式から、整数が大きくなると値段も高くなることがわかります。
整数をひとつも買えないときは$0$を返すというところを少し読み替えて、商品に$0$を追加し、常に購入できるとします。
また、絶対に購入できない数として$10^9+1$を商品に追加します。
こうすることで、途中で条件を満たさなくなる単調性のある数列を用意できました。

あとは二分探索で答えを求めます。

(let* ((a (read))
       (b (read))
       (x (read)))

  (labels ((cost (n)
             ;; 代金を計算する
             (+ (* a n)
                (* b (length (format nil "~A" n)))))

           (bsearch (min max)
             ;; 購入できる最大の整数を二分探索する
             (if (= (1+ min) max)
                 min
                 (let ((mid (+ min (floor (- max min) 2))))
                   (if (<= (cost mid) x)
                       (bsearch mid max)
                       (bsearch min mid))))))

    (format t "~A~%" (bsearch 0 (1+ (expt 10 9))))))
  

AtCoder Beginner Contestを解いてみたリスト