2019年10月30日水曜日

ARC 024 C - だれじゃ

ARC 024 C - だれじゃ

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

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

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


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

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

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

0-based(A0,A1,...,AN1A_0, A_1, ..., A_{N-1})で考える。

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

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

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

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

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

2019年10月26日土曜日

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

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×1054 \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)) 

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

さて、maphashだが、実装を見ればわかるように、pairsを先頭から末尾まで走査するだけだ。つまり、上のpophashは常に先頭から走査して見つけたキーを消すように動くので、全体ではO(N2){\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

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

この最大要素数はSBCL内部ではhigh-water-markと呼ばれている。こういう実装になったのはバージョン1.5.5からで、それ以前は事前に確保したサイズに対するO(N){\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が今の要素数に対するO(N){\mathcal O}(N)になるような実装って可能かな? と少し考えていたけど、とりあえず既存のエントリ全体(と消したエントリ全体)のチェインをnext-vectorとは別に持てばできそう? 定数倍が重くなるわりに、できるようになることが大したことない感じだけど……


  1. pairsの最初の2つのエントリと末尾のエントリはテーブルの管理に使われている。また、SBCLのハッシュテーブルの実装は最近変わったので、上のコードはたぶんバージョン1.5.5以降でないと動かない。 ↩︎

  2. sb-impl::hash-table-next-vectorがインデックスの管理に使われる。 ↩︎

  3. 最初は「ならしでO(1){\mathcal O}(1)」と書いたけど、よく考えるとおかしかった。アクセスが最悪ω(1)\omega (1)で償却O(1){\mathcal O}(1)にするには別の例を挙げる必要がありそう。NN個登録した後N/2N/2個消すとか? ↩︎

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

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

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

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

(2f(1)1) (2f(p1)1)(2f(p2)1)...(2f(pk)1) +(2f(p1p2)1)+(2f(p1p3)1)+...+(2f(pk1pk)1) ... +(1)k(2f(p1p2...pk)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)

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


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


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

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