competitive

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$ 個消すとか？ ↩︎

2019年10月16日水曜日

Maximum-Cup 2013 F - 3人の騎士と1匹の犬

問題
AC

魔力 $0$ の保有者はいかなる場合も不要なので最初に取り除き、 $M$ を $1$ 以上の魔力の保有者の総数としておく。

$N \ge M$ のケースは簡単で、マンハッタン距離をコストにして、 $M$ 個の騎士・魔力保有者のペアを作る最小重みマッチングを求めればよい。

$N < M$ のケースが難しかった。魔力保有者をあらかじめ魔力の降順にソートしておいて、上位 $N$ 人の魔力保有者とのマッチングを考えればよいのだけれど、 $\operatorname{MAGIC}_N$ とちょうど同じ魔力を持つ者が複数人いたときに誰を選ぶかが問題になる。端的には、次のようにすればよい: （ $s, t$ をフローの始点、終点とする）

$s$ から各騎士に、容量 $1$ 、コスト $0$ の辺を張る。
各魔力保有者から $t$ に、容量 $1$ 、コスト $0$ の辺を張る。
各騎士から $\operatorname{MAGIC}_N$ より大きな魔力の保有者に、容量 $1$ 、コストがマンハッタン距離 $-20000$ の辺を張る。
各騎士からちょうど $\operatorname{MAGIC}_N$ の魔力の保有者に、容量 $1$ 、コストがマンハッタン距離の辺を張る。

$\operatorname{MAGIC}_N$ より大きな魔力の保有者が必ずマッチングに含まれるようにしたいので、 $-20000$ の補正を入れている。あとは流量 $N$ の最小コストを求めて、 $20000 \times \operatorname{MAGIC}_Nより大きな魔力の保有者の数$ を足して戻せば答えになっている。

2019年10月15日火曜日

Indeedなう E - Page Rank

問題
AC

全部 $1$ のベクトルからスタートして、漸化式を1000回くらい回せば収束する。

正当性があまりわかってない。漸化式中の行列を $A$ としたとき、つまり $PR = 0.1 + A \cdot PR$ としたとき、

$A$ の列毎の絶対値の和が $1$ 未満なので $\| A \|_1 <1$ 。 $1$ ノルムについては $\|A^p\| \le \|A\|^p$ が成り立つ。したがって $\lim_{p \rightarrow \infty} A^p$ は収束するので漸化式も収束する。（本当に？）¹
収束するなら極限は漸化式の不動点になるから、漸化式を回すだけでよい。

くらいでわかった気になっておいた。

式変形で非正則な行列が出てこなければ大丈夫そう。非正則な場合は知らない。 ↩︎

2019年10月14日月曜日

KUPC 2019 D - Maximin Game

問題
AC

とりあえずDPっぽいものから考えた。カード $1$ から順にカード $N$ まで二人に配っていくとして、千咲さんに $x$ 枚、月乃瀬さんに $y$ 枚配った時点で、条件に合っているような配り方の総数を $dp[x][y]$ とする。遷移としては

$(S_x=1$ かつ $x\le y)$ または $(S_x = 0$ かつ $x > y)$ なら

$dp[x][y] += dp[x-1][y]$

$(S_y=0$ かつ $y \le x)$ または $(S_y = 1$ かつ $y > x)$ なら

$dp[x][y] += dp[x][y-1]$

で求まるが、 ${\mathcal O}(N^2)$ なので制約的に無理だし、実はメモ化再帰で枝刈りされるみたいなこともないし、うまい高速化も思いつかないし……となって困っていた。

こういう問題の言い換えとして、原点 $O$ からスタートして千咲さんがカードを取ったらベクトル $(1, 1)$ に沿って進み、月乃瀬さんが取ったらベクトル $(1, -1)$ に沿って進むというのがあったなと思い出して実験してみると、次のような性質が見える:

$O$ からスタートして $(2N, 0)$ に着く
$y$ 座標が正の時は月乃瀬さんが勝っていて、 $y$ 座標が負の時は千咲さんが勝っている。つまり、文字列 $S$ で勝ち負けが切り替わるところで $x$ 軸と交わる。

すなわち、 $S$ 中で $0$ が連続している部分では $x$ 軸の上にいなければならず（ $x$ 軸を踏んでも良い）、 $1$ が連続している部分では下にいなければならない。このパスの数え上げは有名なのがあった気がすると思ってググったらカタラン数だった。同じ要素が連続している各部分列についてカタラン数を求めてかけ合わせれば答えになっている。