competitive

2019年7月24日水曜日

TDPC F - 準急

問題
AC

駅 $1, ..., i$ までの停車駅の組み合わせを $f(i)$ 通りとする。 $K-1$ 駅目までは止まるかどうか自由に選べるので

$f(i) = 2f(i-1) \qquad (2 \le i < K)$

である。 $K$ 駅目以降は、すでに $K-1$ 駅連続で止まっている場合に停車できないため、このパターンを数えて $2f(i-1)$ から引かなくてはいけない。端的に言うと、 $f(i-1)$ 通りの組み合わせの中で $i$ 駅目に停車できないのは（停車を○、通過を✕で表すと）


駅	1	…	i-k-1	i-k	i-(k-1)	…	i-1	i
停車				✕	○	…	○

というパターンのみである。したがって、

$f(i) = 2f(i-1) - f(i-k-1) \qquad (K \le i < N)$

という漸化式が立つ。

最後に、 $N$ 駅目には必ず止まるので特別扱いして

$f(N) = f(N-1) - f(N-k-1)$

となる。

さて、大枠はこれでよさそうなのだが、境界ケースについて考えてみる必要がある。まず、 $K$ 駅目に停車できないのは1パターンのみなので、 $K<N$ なら $f(K) = 2f(K-1)-1$ 。また、 $K+1$ 駅目には必ず止まれる¹ので $f(K+1) = 2f(K)$ である。上の漸化式と比較すると、 $f(0)=0, f(-1)=1$ とするとつじつまがあっていることがわかる。

1駅目に必ず止まるという条件による。 ↩︎

2019年7月23日火曜日

define-source-transform

sb-c:define-source-transformの使い方について。

例えば、動的なmodに対しての掛け算mod*を定義したいとする:

(declaim ((unsigned-byte 32) *modulus*))
(defvar *modulus*)

(defun mod* (&rest args)
  (reduce (lambda (x y) (mod (* x y) *modulus*))
          args
          :initial-value 1))

（ここでは演算の性質は問題にしない。）この mod*はどんな引数に対してもいちいちreduceを呼ぶし、modや*も引数の型に特定化されないのであまり効率が良くない。多くの場合、このような問題はインライン宣言で解決する。しかしこの場合については、mod*をインライン化することでargsの長さなどがコンパイル時に確定できても、*とmodを使ったフォームに展開されたりはしない。SBCLのreduceには何のコンパイル時変換も定義されていないためだ。こういう時にはdefine-compiler-macroが使える:

(define-compiler-macro mod* (&rest args)
  (if (null args)
      1
      (reduce (lambda (x y) `(mod (* ,x ,y) *modulus*)) args)))

こうすれば、(mod* a b c)は(MOD (* (MOD (* A B) *MODULUS*) C) *MODULUS*)のように展開されることになる。

しかし、コンパイラマクロによる変換には本質的な制約がある: コンパイラマクロはあらゆる定数伝搬の前に展開される。例えば、三乗を求める関数cubeがあったとする:

(declaim (inline cube))
(defun cube (operator x)
  (funcall operator x x x))

(defun test (x)
  (declare (optimize (speed 3)))
  (cube #'mod* x))
  
; disassembly for TEST
; Size: 36 bytes. Origin: #x1007F7EB96
; 96: 840425F8FF1020   TEST AL, [#x2010FFF8]        ; no-arg-parsing entry point
                                                    ; safepoint
; 9D: 488BD0           MOV RDX, RAX
; A0: 488BF8           MOV RDI, RAX
; A3: 488BF0           MOV RSI, RAX
; A6: 488B059BFFFFFF   MOV RAX, [RIP-101]           ; #<SB-KERNEL:FDEFN MOD*>
; AD: B906000000       MOV ECX, 6
; B2: FF7508           PUSH QWORD PTR [RBP+8]
; B5: FF6009           JMP QWORD PTR [RAX+9]
; B8: CC0F             BREAK 15                     ; Invalid argument count trap

test内でcubeがインライン展開されるが、そのインライン展開の中でさらにmod*が展開されたりはしない。コンパイラマクロが展開されるタイミングを考えれば当然ではある。

さて、このような制約からか、SBCL内部のコード変換にはdefine-compiler-macroはほとんど使われていない。SBCLの標準の関数の多くは、これに似ているがより強力なsb-c:define-source-transformで変換されている。^[1]

define-source-transformの使い方とコンパイラマクロとの違い

sb-c:define-source-transformの使い方はdefine-compiler-macroとほとんど同じである。

;; コンパイラマクロ付きのmod*
(defun mod*-with-compiler-macro (&rest args)
  (reduce (lambda (x y) (mod (* x y) *modulus*))
          args
          :initial-value 1))

(define-compiler-macro mod*-with-compiler-macro (&whole whole &rest args)
  (print whole)
  (if (null args)
      1
      (reduce (lambda (x y) `(mod (* ,x ,y) *modulus*)) args)))

;; source-transform付きのmod*
(defun mod*-with-source-transform (&rest args)
  (reduce (lambda (x y) (mod (* x y) *modulus*))
          args
          :initial-value 1))

(sb-c:define-source-transform mod*-with-source-transform (&whole whole &rest args)
  (print whole)
  (if (null args)
      1
      (reduce (lambda (x y) `(mod (* ,x ,y) *modulus*)) args)))

(defun test (x)
  (declare (optimize (speed 3))
           ((unsigned-byte 32) x))
  (let ((*modulus* 10007))
    (funcall #'mod*-with-compiler-macro x x x)               ; 1
    (funcall #'mod*-with-source-transform x x x)             ; 2
    (multiple-value-call #'mod*-with-compiler-macro x x x)   ; 3
    (multiple-value-call #'mod*-with-source-transform x x x) ; 4
    (apply #'mod*-with-compiler-macro (list x x x))          ; 5
    (apply #'mod*-with-source-transform (list x x x))        ; 6
    (cube #'mod*-with-compiler-macro x)                      ; 7
    (cube #'mod*-with-source-transform x)                    ; 8
))

testの中には三乗を計算する同等のフォームが8つ並べてある。上のコンパイラマクロとsource-transformにはprintを付けてあるので、testをコンパイルすると&whole引数を束縛しているフォームが次にようにいくつか出力される。（数字が抜けている部分は展開されなかったということである。）

1: (FUNCALL #'MOD*-WITH-COMPILER-MACRO X X X) 
2: (#<SB-C::GLOBAL-VAR
   :%SOURCE-NAME MOD*-WITH-SOURCE-TRANSFORM
   :TYPE #<SB-KERNEL:BUILT-IN-CLASSOID FUNCTION (read-only)>
   :DEFINED-TYPE #<SB-KERNEL:FUN-TYPE (FUNCTION * (VALUES T &OPTIONAL))>
   :WHERE-FROM :DEFINED
   :KIND :GLOBAL-FUNCTION {1003DB5963}>
 X X X) 
4: (MOD*-WITH-SOURCE-TRANSFORM #:G34 #:G35 #:G36) 
6: (MOD*-WITH-SOURCE-TRANSFORM #:G47 #:G48 #:G49) 
8: (MOD*-WITH-SOURCE-TRANSFORM #:G78 #:G79 #:G80)

以下、コンパイラマクロとの差異について。

コンパイラマクロは定数伝搬の前の展開しかできないが、source-transformは後にも適用される。8を見ればわかるように、インライン展開されたcubeの中のoperatorが#'mod*-with-source-transformであると推論されたあとに展開が起きている。コンパイラマクロではこのようなことはできない。（とはいえ、この種の最適化が常に完璧に行われるわけではないので過度に期待してはいけない。）
1と2の違いからわかるように、(funcall <function> <args>*)形式のフォームが渡されたとき、コンパイラマクロは&wholeをそのままのフォームに束縛するが、source-transformは(<function> <args>*)形式に直して束縛する。
3-6で示されるように、コンパイラマクロはmultiple-value-callで呼び出される関数を変換できない。source-transformは（引数の数が決定できれば）変換できる。applyも同様。^[2]

コンパイラマクロでマクロ展開を放棄したい時は&wholeを束縛しているフォームをそのまま返せばよい。しかし、source-transformで同様のことをすると、返したフォームに同じsource-transformが無限に適用されてSBCLが落ちてしまう。代わりに、source-transformでは2つ目の返り値でnon-nilを返すことによりこの変換を適用しないことを通知する:

;; 展開を放棄する場合の書き方
(define-compiler-macro foo (&whole form arg) form) ; OK
(sb-c:define-source-transform foo (&whole form arg) form) ; NG
(sb-c:define-source-transform foo (&whole form arg) (values nil t)) ; OK

source-transformのラムダリストは、元の関数のラムダリストと正確に一致している必要はない。例えば、mod*に引数が1つの場合のためのsource-transformを定義しても問題ない: (sb-c:define-source-transform mod* (x) x)。この場合、source-transformは引数が1つとわかっているケースでのみ呼び出される。この挙動の利用例はSBCLのソースにも見つかるので、想定された使い方だと思われる。ただし、source-transformは（deftransformと違って）1つの関数につき1つしか定義できないため、複数定義して引数の数でディスパッチするようなことはできない。そのような分岐は1つのsource-transformの中で行う必要がある。例えばgcdなどのsource-transformが参考になる。^[3]

source-transformは、コンパイラマクロと違ってマクロには定義できない。もっとも、コンパイラマクロをマクロに定義する例はほとんどないようなので、重要ではなさそう。
source-transformによる変換はnotinlineで阻止できる。これはコンパイラマクロと同じ。
define-source-transformで定義される展開器は(sb-int:info :function :source-transform <symbol>)で得ることができて、compiler-macro-functionなどと同じように使える。
source-transformの展開をREPLで確認したい場合はg000001さんの記事の通りにすれば良い。ただ、記事が書かれた時とはsource-transformの仕様が変わっているようなので（source-transformが必ずenvironmentを引数に取るようになっている？）SBCL1.4.14で使える形をメモしておく:

(defun source-transform-expand (form &optional (env (sb-kernel:make-null-lexenv)))
  (if (and (consp form)
           (symbolp (car form))
           (not (special-operator-p (car form))) )
      (let ((sb-c::*lexenv* env))
        (or (and (fboundp (car form))
                 (multiple-value-bind (fun win)
                     (sb-int:info :function :source-transform (car form))
                   (and win (funcall fun form env))))
            (values form T)))
      (values form T)))

(source-transform-expand '(apply #'+ (list a b c)))
;; |-> (MULTIPLE-VALUE-CALL #'+ (VALUES-LIST (LIST A B C)))

define-source-transform（からマクロ展開されたフォーム）はコンパイル時に評価されるわけではない。必要ならeval-whenを使う。

もっとも、コメントを読む限りではsource-transformがそのために作られたわけではなさそうだ。 ↩︎
なお、SBCLでは(apply <function> <list>)自体がsource-transformで(multiple-value-call <function> (values-list <list>))に変換される。 ↩︎ ↩︎
gcdのsource-transformは(gcd a b)のような2引数のケースでは変換しないようになっている。これも、(gcd a b)に対して(gcd a b)を返すと無限に展開されてしまうためである。 ↩︎

2019年7月22日月曜日

AGC 036 B - Do Not Duplicate

問題
AC

$s$ を操作していく中で、 $s$ の先頭の数と同じ数が現れたとき、またその時に限ってすべての数が消えることに注目する。

数列 $A := (3, 2, 4, 3, 4, 1)$ を例にとって考える。 $s$ の先頭が $A_0(=3)$ である場合、 $A_1(=2)$ である場合、…の $n$ 通りについて、 $A$ を右にひとつつなげた時に、数が全部消えて次に始まる位置を考える:

~~3 2 4 3~~ ~~4 1 | 3 2 4~~ 3 4 1
X ~~2 4 3 4 1 | 3 2~~ 4 3 4 1
X X ~~4 3 4~~ ~~1 | 3 2 4 3 4 1~~
X X X ~~3 4 1 | 3~~ 2 4 3 4 1
X X X X ~~4 1 | 3 2 4~~ 3 4 1
X X X X X ~~1 | 3 2 4 3 4 1~~

つまり、 $A$ をひとつ追加すると先頭の位置は

$0 \mapsto 3 \\ 1 \mapsto 2 \\ 2 \mapsto 6 \\ 3 \mapsto 1 \\ 4 \mapsto 3 \\ 5 \mapsto 6$

と変化していることになる。ここで位置 $6$ が登場しているが、つまり、先頭が存在しない場合も扱う必要があった。すなわち

X X X X X X | 3 2 4 3 4 1

も追加して

$0 \mapsto 3 \\ 1 \mapsto 2 \\ 2 \mapsto 6 \\ 3 \mapsto 1 \\ 4 \mapsto 3 \\ 5 \mapsto 6 \\ 6 \mapsto 0$

が完全な対応である。この写像を $K-1$ 回合成すれば、そこからはシミュレーションで間に合う。合成にはダブリングが使える。

開始位置を $n$ 通りではなくて $n+1$ 通り考える必要がある、という部分を明確にできなくてコンテスト中には書けなかった。

あと、写像を作る部分を ${\mathcal O}(N)$ で実装するのに時間がかかった。こういうのは問題数をこなすしかなさそう。

2019年7月19日金曜日

天下一プログラマーコンテスト2016本戦 C - たんごたくさん

$S := a_0a_1...,a_{n-1}$ の連続部分列 $a_la_{l+1}...a_{r-1}$ を $S[l, r)$ と書くことにする。文字列 $S[i, n)$ に対して問題の操作を行った時の最大値を $f(i)$ とするとき、

$f(i) = \max_{i < k \le 200} \bigr(S[i, k)の重さ + f(k) \bigl)$

だから、DPして $f(0)$ を求めればそれが答えである。（ただし、 $P$ に含まれない単語の重さは $0$ とする。） $S[i, k)$ の重さを求める部分で、部分列が $P$ に含まれているかを素朴に判定すると間に合わないので、Trieやローリングハッシュを使う。

Trieの例題として解いたのだが、よく見るとローリングハッシュでも問題なかった。ただ、後者はかなり重い。

2019年7月15日月曜日

AGC 012 B - Splatter Painting

問題
AC

クエリを逆順に処理し、頂点の色が最初に塗った色に固定される問題に変える。頂点 $v$ から処理した最大の深さを $\operatorname{depth}[v]$ 、頂点 $v$ に塗った色を $\operatorname{color[v]}$ （どちらも初期値 $0$ ）として、クエリ毎にDFSで更新していく。 $\operatorname{depth}[v]$ 以下の深さの更新は影響しないので、枝刈りしてよい。

各頂点 $v$ について $\operatorname{depth}[v]$ の更新は最大で $\max d_i$ 回しか起こらず、したがって $v$ の隣接頂点が走査される回数も高々 $\max d_i$ 回である。クエリをすべて処理した時、前者の合計は ${\mathcal O}(N\max d_i)$ で後者の合計は ${\mathcal O}(M\max d_i)$ なので、計算量は ${\mathcal O}(Q+(N+M)\max d_i)$ である。

隣接頂点が走査される回数がなぜか ${\mathcal O}(|V|^2)$ な気がして困っていた。

ABC 132 E - Hopscotch Addictで失敗した記憶が頭にあったせいかも。いちおう整理しておくと、 $N(x):=\{(u, v) \in V^2 \:|\: uとvの最短距離がx\}$ とするとき、当然 $|N(1)| = {\mathcal O}(|E|)$ であるが、 $N(2), N(3), ...$ の大きさは ${\mathcal O}(|E|)$ とは限らず¹、一般に ${\mathcal O}(|V|^2)$ である。

例えばスターグラフは $|E|= \Theta(|V|)$ だが $N(2) = \Theta(|V|^2)$ になる。 ↩︎

2019年7月11日木曜日

(count 1 simple-bit-vector)を高速に扱えるのはstart, endが指定されていない場合だけ

Counting 1’s

ビット列を部分的に反転させたり、立っているビットを数えたりする問題。セグメント木などで解ける典型問題¹だが、 $10^{10}$ くらいなので、愚直シミュレーションをワードサイズ高速化しても十分間に合いそう。ANSI CLには十分な機能がないので、実装して通した。

その後でSBCLのソースを眺めていると、どうやらcountにはsimple-bit-vector用のトランスフォームが定義されているらしい。これなら自分の実装はいらなかったなと思ったが、コードをよく見ると、引数にstartとendがなく、ベクタ全体を数える場合にだけ適用されるdeftransformだった。範囲指定がある場合は通常通り1ビットずつ数えるので、まったく間に合わないようだ。

あと、logcountがpopcntになるのはバージョン1.2.8以降らしい。AtCoder以外のコンテストサイトのSBCLは確認できる限りすべて1.3.0以降なので、AtCoderのSBCLが新しくなれば考慮する必要がなくなりそう。

とりあえず平衡二分木で通したのはこれ ↩︎

2019年7月10日水曜日

ARC 073 F - Many Moves

問題
AC

クエリ $x_i$ を処理した際に、動かさなかったほうのコマが位置 $y$ にある場合の最短時間を $dp[i][y]$ とせよ。この時、コマは位置 $x_i$ と $y$ にある。ここからクエリ $x_{i+1}$ を処理するとき、コマを $x_i$ → $x_{i+1}$ と移動させ、 $y$ のコマを動かさないなら

$dp[i+1][y] = dp[i][y] + |x_{i} - x_{i+1}| \qquad (1)$

$y$ → $x_{i+1}$ と移動させ、 $x_{i}$ のコマを動かさないなら

$dp[i+1][x_i] = \min_y (dp[i][y] + |y - x_{i+1}|) \qquad (2)$

これで計算できる形になっているので、初期化を $dp[1][B] := |x_1 - A|, dp[1][A] := |x_1-B|$ 、それ以外は $+\infty$ としてDPすれば答えは求まる。ただ、このままでは間に合わないので遷移を工夫する必要がある。

$(2)$ の右辺は、次のように絶対値を外して書ける:

$dp[i+1][x_i] := \min \begin{cases} \min_{y \ge x_{i+1}} (dp[i][y]+y)-x_{i+1} \\ \min_{y < x_{i+1}} (dp[i][y]-y)+x_{i+1}\end{cases}$

それぞれの $\min$ はたぶんセグメント木等で得られる形になっているので、 $dp$ を1次元のセグメント木にして ${\mathcal O}(\log N)$ で遷移できそう。具体的には、

$T := \min \begin{cases} \min_{y \ge x_{i+1}} (dp[y]+y)-x_{i+1} \\ \min_{y < x_{i+1}} (dp[y]-y)+x_{i+1}\end{cases} \qquad (3)$

を求めたあと、 $dp$ 全体に $|x_i - x_{i+1}|$ を加算し、最後に $dp[x_i] := T$ と更新し直せばよい。

悩んだのは $(3)$ の計算をどう実現するかで、テクニックを知らなかったのでもっとも直接的な扱い方をした:

セグメント木の元を $((y^+, d^+), (y^-, d^-))$ と４値で持ち、演算を

$((y^+_1, d^+_1), (y^-_1, d^-_1)) \oplus ((y^+_2, d^+_2), (y^-_2, d^-_2)) \\ = ((y^+_1, d^+_1)と(y^+_2, d^+_2)のうちy^+_1+d^+_1, y^+_2+d^+_2の小さいほう,\\ \qquad (y^-_1, d^-_1)と(y^-_2, d^-_2)のうちy^-_1-d^-_1, y^-_2-d^-_2の小さいほう)$

で定める。値 $\Delta$ の区間加算は
$((y^+, d^+), (y^-, d^-)) \mapsto ((y^+ +\Delta, d^+), (y^- + \Delta, d^-))$

でよい。

これでACできたが、素朴すぎて定数倍がかなり重かった。¹

skyさんの解説にもっとスマートな方法が載っていた。最初から $dpl [y] := dp[y] + N - y, dpr[y] := dp[y] +y$ みたいに補正したものを用意すればよいらしい。なるほど……

そもそもコンパイル時間だけで700ms消費している。 ↩︎

登録: 投稿 (Atom)