competitive: 10月 2019

2019年10月30日水曜日

JOI2018 予選 F - L番目のK番目の数

問題
AC

0-based( $A_0, A_1, ..., A_{N-1}$ )で考える。

書き出した数の中に $x$ 以下の数が $f(x)$ 個あるとするとき、 $f(x) \ge L$ となるような最小の $x$ を求めればよい。この言い換えを元の数列 $(A_i)$ の言葉でさらに言い換えると、次のようになる:

$x$ 以下の数を $K$ 個以上含むような部分列 $A[l, r)$ が $L$ 個以上存在するような $x$ の中で最小のものを求めよ。

部分列 $A[l, r)$ が $x$ 以下の数を $g(l, r, x)$ 個含むとする。 $x$ を固定した時に $、g(l, r, x) \ge K$ であるような $l, r \in [0, N]$ が何組あるか数えられれば、二分探索で上の $x$ も求まりそう。具体的には次のように数える:

$g(0, i, x)$ は部分列 $A[0, i)$ の中の $x$ 以下の数の総数だから、累積和でテーブルを作っておけば任意の $i$ について $O(1)$ で求まる。そして、 $g(l, r, x) = g(0, r, x) - g(0, l, x) \ge K \Leftrightarrow g(0, r, x) \ge K+g(0, l, x)$ であり、 $l$ を固定した時にこの式を満たすような $r$ の数は二分探索で求まる。したがって、すべての $l \in [0, N]$ についてこの $r$ の数を求めて足し合わせると、それが $f(x)$ である。

あとは $f(x)$ について二分探索して、 $f(x) \ge L$ であるような最小の $x$ を求めればそれが答えになっている。計算量は ${\mathcal O}(N \log^2 N)$ 。

ARC 024 C - だれじゃ

問題
AC

「（部分列に）文字 $c$ がちょうど $x$ 個含まれること」の $26N$ 通りすべてに対して、あらかじめ乱数 $R_{c, x}$ を割り振っておく。最初の $K$ 文字のヒストグラムを作って、各文字 $c$ について該当する $R_{c, x}$ のXORを取って、最初のハッシュ値とする。

あとは、長さ $K$ の部分列をスライドさせながら各部分列のハッシュ値を求めていく。直前の部分列のハッシュ値が $V$ であったとし、文字 $c$ が加わって $c$ の数が $x$ から $x+1$ に増え、文字 $d$ が除かれて $d$ の数が $y$ から $y-1$ に減るとすると、新しい部分列のハッシュ値は $V \oplus R_{c, x} \oplus R_{c, x+1} \oplus R_{d, y} \oplus R_{d, y-1}$ になる。このハッシュ値をキーとして、部分列の開始位置を保持しておく。同じハッシュ値が再び出現した時、開始位置が $K$ 以上離れていればアナグラムダジャレが見つかったことになる。

アルファベットのサイズを $\alpha$ とするとき、計算量は ${\mathcal O}(\alpha N)$ 。

こんなことしなくても、普通にヒストグラムをキーにするだけで通った……

2019年10月26日土曜日

yukicoder No.917 - No.917 Make One With GCD

問題
AC

$A$ に登場する素因数を（重複なしで）すべて集めて $p_1, p_2, ..., p_k$ とする時、これらのどれも公約数とならないような部分列の数を求めればよい。包除を考えれば計算できそう。

正整数 $x$ が与えられたとする。 $A_1, A_2, ..., A_N$ のうち $x$ で割り切れるものの総数を $f(x)$ とするとき、 $x$ が公約数であるような部分列の数は（空の部分列を除いて） $2^{f(x)}-1$ である。したがって、求める数は包除原理に従って

$(2^{f(1)}-1) \\ \ - (2^{f(p_1)}-1) - (2^{f(p_2)}-1) - ... - (2^{f(p_k)}-1) \\ \ + (2^{f(p_1p_2)}-1) + (2^{f(p_1p_3)}-1) + ... + (2^{f(p_{k-1}p_k)}-1) \\ \ - ... \ + (-1)^k(2^{f(p_1p_2...p_k)}-1)$

のようになる。素数の数が奇数なら引いて偶数なら足せばよい。ただし、登場する素数の総数 $k$ はだいぶ大きくなることがあるので、上の式の $2^k$ 項全部を計算していては間に合わない。 $10^8$ を超えるものを枝刈りすれば間に合う。

これ、計算量がわからない。正整数 $A$ と素数列のprefix $\{2, 3, 5, 7, ..., p_k\}$ が与えられたとき、prefixの部分集合で総積が $A$ を超えないようなものが何通りあるか？という問題に帰着しそうだけど……

50
97132843 98363449 89581363 82864427 98796221 99147481 74352463 99477713 93924871 65541251 99070949 98476523 99270979 99661321 99880747 98045347 99838183 98904791 99582083 89757337 99752171 98440403 99331283 98037839 99472123 98862697 99813167 99238807 99743993 99408347 99727399 97821397 99594503 98248609 98207933 99677881 90900499 81927497 68034287 54143561 90426598 35950241 73138803 82613935 68388971 92946349 33984931 12780049 64097801 1062347

最悪っぽいケースを作ってみたらだいぶ時間が怪しかった。

maphashによる各エントリへのアクセスはO(1)とは限らない

SBCLのハッシュテーブルについて。

ハッシュテーブルのキーをなんでもいいから1つ消したいとする。ANSI CLのハッシュテーブルに該当する機能はない。しかし、そういう関数を定義するのは特に難しくなさそう:

(defun pophash (hash-table)
  (maphash (lambda (key _)
             (remhash key hash-table)
             (return-from pophash key))
           hash-table))

maphashの中で受け取ったエントリを消去するのは許されているので、pophashは意図通り動作する。しかし……

(defun test-pophash (size)
  (let ((table (make-hash-table :size size)))
    (dotimes (i size)
      (setf (gethash i table) t))
    (dotimes (i size)
      (pophash table))))

(time (test-pophash 200000))
;; Evaluation took:
;;   15.268 seconds of real time
;;   15.265625 seconds of total run time (15.265625 user, 0.000000 system)
;;   99.99% CPU
;;   38,084,922,378 processor cycles
;;   5,848,704 bytes consed

たった $4 \times 10^5$ 回の操作に時間が掛かりすぎである。

もちろん、次のようにremhashするだけなら計算量の問題はない。

(defun test-pophash2 (size)
  (let ((table (make-hash-table :size size)))
    (dotimes (i size)
      (setf (gethash i table) t))
    (dotimes (i size)
      (remhash i table))))

(time (test-pophash2 200000))

;; Evaluation took:
;;   0.016 seconds of real time
;;   0.015625 seconds of total run time (0.015625 user, 0.000000 system)
;;   100.00% CPU
;;   37,052,672 processor cycles
;;   5,848,704 bytes consed

そもそもchainingによるハッシュテーブルがキーをどう管理するか考えてみると、pophashがだめなのはそれはそうという感じだった。以下、手短に動作を見てみる:

CL-USER> (let ((table (make-hash-table)))
	   (setf (gethash 3 table) 8
		 (gethash 5 table) 32
		 (gethash 7 table) 128)
	   (print (sb-impl::hash-table-pairs table))
	   (remhash 5 table)
	   (print (sb-impl::hash-table-pairs table))
	   (setf (gethash 11 table) 2048)
	   (print (sb-impl::hash-table-pairs table)))

#(3 0 3 8 5 32 7 128 #<unbound> #<unbound> ... #<unbound>
  #(0 60102308 60102306 60102304 0 0 0 0 0 0 0 0 0 0 0)) 
;; キー5を消す
#(3 0 3 8 #<unbound> #<unbound> 7 128 #<unbound> #<unbound> ... #<unbound>
  #(0 60102308 60102306 60102304 0 0 0 0 0 0 0 0 0 0 0)) 
;; キー11を追加する
#(3 0 3 8 11 2048 7 128 #<unbound> #<unbound> ... #<unbound>
  #(0 60102308 60102317 60102304 0 0 0 0 0 0 0 0 0 0 0))

上のように¹、ハッシュテーブルの中身は単に配列に並んでいて、remhashによって消されるとそこが消えるだけである。unboundになったインデックスはうまく連鎖的に管理されていて、次に追加する時にはそこが埋まるようになっている。²

さて、maphashだが、実装を見ればわかるように、pairsを先頭から末尾まで走査するだけだ。つまり、上のpophashは常に先頭から走査して見つけたキーを消すように動くので、全体では ${\mathcal O}(N^2)$ になってしまう。

また、同じような理由で次のコードも計算量の問題がある:

(defun test-maphash (size)
  (let ((table (make-hash-table :size size))
        (sum 0))
    (dotimes (i size)
      (setf (gethash i table) t))
    (dotimes (i (- size 1))
      (remhash i table))
    (dotimes (i size)
      (maphash (lambda (x _) (incf sum x)) table))
    sum))

(time (test-maphash 200000))
;; Evaluation took:
;;   34.567 seconds of real time
;;   34.562500 seconds of total run time (34.562500 user, 0.000000 system)
;;   99.99% CPU
;;   86,197,938,782 processor cycles
;;   5,848,704 bytes consed

ハッシュテーブルに $200000$ 個のキーを登録したあと $1$ 個まで減らし、そのテーブルに対してmaphashを $200000$ 回適用している。これも、同じ原理で ${\mathcal O}(N^2)$ になる。maphashによる走査は確かに ${\mathcal O}(N)$ だけれど、テーブルの今の要素数に対する ${\mathcal O}(N)$ ではなく、過去に到達した最大要素数に対する ${\mathcal O}(N)$ なので、各エントリへのアクセスが ${\mathcal O}(1)$ になるとは限らないのだった。³

この最大要素数はSBCL内部ではhigh-water-markと呼ばれている。こういう実装になったのはバージョン1.5.5からで、それ以前は事前に確保したサイズに対する ${\mathcal O}(N)$ だったようだ。該当コミットはこれ。次のコードで違いがわかる:

(defun test-maphash2 (size)
  (let ((table (make-hash-table :size size))
        (sum 0))
    (setf (gethash 0 table) t)
    (dotimes (i size)
      (maphash (lambda (x _) (incf sum x)) table))
    sum))

(time (test-maphash2 200000))
;; SBCL 1.5.8, O(n)
;; Evaluation took:
;;   0.016 seconds of real time
;;   0.015625 seconds of total run time (0.015625 user, 0.000000 system)
;;   100.00% CPU
;;   16,126,752 processor cycles
;;   5,848,704 bytes consed
  
;; SBCL 1.4.14, O(n^2)
;; Evaluation took:
;;   47.615 seconds of real time
;;   47.625000 seconds of total run time (47.625000 user, 0.000000 system)
;;   100.02% CPU
;;   118,798,016,334 processor cycles
;;   8,497,264 bytes consed

ハッシュテーブルの要素数が大きくなるかもしれない場合に、リハッシュの回数を減らそうとして最初に:sizeを大きめに取っておくという発想は普通っぽい感じだけど、1.5.5より前のバージョンでは逆に遅くなる可能性がある。

maphashが今の要素数に対する ${\mathcal O}(N)$ になるような実装って可能かな？と少し考えていたけど、とりあえず既存のエントリ全体（と消したエントリ全体）のチェインをnext-vectorとは別に持てばできそう？定数倍が重くなるわりに、できるようになることが大したことない感じだけど……

pairsの最初の2つのエントリと末尾のエントリはテーブルの管理に使われている。また、SBCLのハッシュテーブルの実装は最近変わったので、上のコードはたぶんバージョン1.5.5以降でないと動かない。 ↩︎
sb-impl::hash-table-next-vectorがインデックスの管理に使われる。 ↩︎
最初は「ならしで ${\mathcal O}(1)$ 」と書いたけど、よく考えるとおかしかった。アクセスが最悪 $\omega (1)$ で償却 ${\mathcal O}(1)$ にするには別の例を挙げる必要がありそう。 $N$ 個登録した後 $N/2$ 個消すとか？ ↩︎