実装方法の逆引き

実装でよくつまづいているポイントをメモ。

二乗すると$n$以上になるような最小の自然数

$\lfloor \sqrt{n} \rfloor$は(isqrt n)で求まる。$\lceil \sqrt{n} \rceil$には対応する関数がないが、やはりisqrtが使える:

(+ 1 (isqrt (- n 1)))

ただし$n=0$の時に壊れているので注意。（SBCL x86-64では、速度が必要な場合にはsqrtを使ったほうがよい。）

$2^k \ge n$であるような最小の整数$k$

$n \in {\mathbb N}$が与えられたとき、$2^k \ge n$であるような最小の$k \in {\mathbb N}$は$\lceil \log_2 n \rceil$と書ける。計算の際は

(integer-length (- n 1))

とするのがよい。同様に、$2^k \le n$であるような最大の$k \in {\mathbb N}$、つまり$\lfloor \log_2 n \rfloor$は

(- (integer-length n) 1)

で得られる。

ちなみに、$n$以上であるような最小の$2$の累乗が欲しい場合は、(ash 1 (integer-length (- n 1)))だが、これはsb-int:power-of-two-ceilingとしてSBCLにあったりする。

$p$で割ると$q$あまる整数で$x$以上/以下のもの

$p$で割ると$q$あまる整数で$x$以上の最小のものは$p \lceil (x-q)/p \rceil + q$。あるいは、位相の差を足すと考えて$x + (q-x) \% p$のほうがわかりやすい？

$p$で割ると$q$あまる整数で$x$以下の最大のものは$p \lfloor (x-q)/p \rfloor + q$。同様に、$x - (x-q) \% p$でもよい。

$n$以下の$k$の正の倍数の総数

$n$以下の$k$の正の倍数の総数は$\lfloor n/k \rfloor$である。

$n$以下の、$k$を法として$a \in \{0,1,...,k−1 \}$と合同な正の整数の数は

$$\Bigl \lfloor \frac{n+(k-a)\%k}{k} \Bigr \rfloor$$

がいちばんシンプル？ （ただし、$\%$はあまりを求める演算とする。）非負整数を数える場合は$\%k$をしなければよい。

$n$以下の$k$の正の倍数の総和

$n$以下の$k$の正の倍数の総和は

$$\frac{1}{2}k \Bigl \lfloor \frac{n}{k} \Bigr \rfloor \Bigl( 1+\Bigl \lfloor \frac{n}{k} \Bigr \rfloor \Bigr)$$

である。ただ、等差数列の和が両端の和に長さ/2を掛けたものであることがわかっていれば、確認しなくても問題なさそう。

自然数をできるだけ等分する

$n$個のものを$k$人に配る際にできるだけ等分になるようにすると、$\lfloor n/k \rfloor + 1$個を$n \%k$人に、$\lfloor n/k \rfloor$個を$k-n \%k$人に配ることになる。ちょうど割り切れる時は大きいほうがが$0$個、小さいほうが$k$個になっていることに気を付ける。

$\lfloor x/k \rfloor$が一定であるような区間

$n, k \in {\mathbb N}$が与えられたとき、$\lfloor x/k \rfloor = \lfloor n/k \rfloor$であるような$x$の区間は

$$\Bigl [ \Bigl \lfloor \frac{n}{k} \Bigr \rfloor \cdot k, \: \Bigl \lceil \frac{n+1}{k} \Bigr \rceil \cdot k -1\Bigr ]$$

であり、$\lceil x/k \rceil = \lceil n/k \rceil$であるような$x$の区間は

$$\Bigl [ \Bigl \lfloor \frac{n-1}{k} \Bigr \rfloor \cdot k + 1, \: \Bigl \lceil \frac{n}{k} \Bigr \rceil \cdot k \Bigr ]$$

である。

TZCNT

tzcnt (trailing zero count) はLSBからの連続する0の数を数える命令である（例: $00101000 \mapsto 3$）。これを実現する効率の良い書き方は

(- (integer-length (logand x (- x))) 1)

だろう。SBCLならinteger-lengthはbsr命令に落ちる。 xが0の時に-1が返ることに注意。

integer-lengthの代わりにlogcountを使って

(logcount (- (logand x (- x)) 1))

と書いても良い。こちらは$x$が0の時に0が返るという違いがある。logcountはSBCL （バージョン1.2.8以降）ではpopcnt命令になり、だいたい上と同程度の効率になる。

2の累乗かどうか判定する

(= 1 (logcount x))や(zerop (logand x (- x 1)))など。後者は$0$でも真になることに注意。

実数$r$より小さい/大きいもっとも近い整数

実数$r$より小さいもっとも大きな整数は$\lceil r \rceil -1$。$r = a/b \ (b >0)$なら$\lfloor (a-1)/b \rfloor$でもよい。

実数$x$より大きいもっとも小さな整数は$\lfloor r \rfloor + 1$。$r=a/b \ (b > 0)$なら$\lceil (a+1)/b \rceil$でもよい。

$x$以上/以下の偶数/奇数

• 偶数の場合だけ1足す。つまり、$x$以上の奇数にする: (logior 1 x)
• 奇数の場合だけ1足す。つまり、$x$以上の偶数にする: (logand -2 (+ x 1))
• 偶数の場合だけ1引く。つまり、$x$以下の奇数にする: (logior 1 (- x 1))
• 奇数の場合だけ1引く。つまり、$x$以下の偶数にする: (logand -2 x)

区間の重なり

2つの半開区間$[l_1, r_1), [l_2, r_2)$が重なっている必要十分条件は$l_1 < r_2$かつ$l_2 < r_1$であること。 2つの閉区間$[l_1, r_1], [l_2, r_2]$が重なっている必要十分条件は$l_1 \le r_2$かつ$l_2 \le r_1$であること。

区間の入れ替え

隣り合った区間$[a, b], [b, c]$を長さを保つように入れ替えると、新しい切れ目の位置は$a+c-b$になる。

lower_boundとupper_bound

upper_boundとlower_boundを使った添え字の処理のまとめ

列が昇順にソートされている場合

• $x$以上でもっとも左にある数の位置: lower_bound(x)
• $x$以下でもっとも右にある数の位置: upper_bound(x)-1
• $x$より大きいもっとも左にある数の位置:: upper_bound(x)
• $x$より小さいもっとも右にある数の位置: lower_bound(x)-1
• $x$以上の数の総数: N - lower_bound(x)
• $x$以下の数の総数: upper_bound(x)
• $x$より大きい数の総数: N - upper_bound(x)
• $x$より小さい数の総数: lower_bound(x)
• ちょうど$x$に等しい数の総数: upper_bound(x) - lower_bound(x)
• $x$に等しい数の存在する区間: [lower_bound(x), upper_bound(x))

整数列に対して有理数（割り算の結果）で評価する場合、floorやceilで考えたいかもしれない。その場合の書き方:

• $x$以上でもっとも左にある数の位置: lower_bound(ceil(x))
• $x$以下でもっとも右にある数の位置: upper_bound(floor(x))-1
• $x$より大きいもっとも左にある数の位置:: upper_bound(floor(x))
• $x$より小さいもっとも右にある位置の数: lower_bound(ceil(x))-1
• $x$以上の数の総数: N - lower_bound(ceil(x))
• $x$以下の数の総数: upper_bound(floor(x))
• $x$より大きい数の総数: N - upper_bound(floor(x))
• $x$より小さい数の総数: lower_bound(ceil(x))
• ちょうど$x$に等しい数の総数: max(0, upper_bound(floor(x)) - lower_bound(ceil(x)))
• $x$に等しい数の存在する区間: [lower_bound(ceil(x)), upper_bound(floor(x)) ただし、無効な区間は空とする。
• $x \in [L, R]$であるような$x$の総数: upper_bound(floor(R)) - lower_bound(ceil(L))
• $x \in [L, R)$であるような$x$の総数: lower_bound(ceil(R)) - lower_bound(ceil(L))
• $x \in (L, R]$であるような$x$の総数: upper_bound(floor(R)) - upper_bound(floor(L))
• $x \in (L, R)$であるような$x$の総数: lower_bound(ceil(R)) - upper_bound(floor(L))

1-basedで$k$番目に小さい数が$x$ということは、$t$以下の数が$k$個存在するような最小の$t$が$x$に等しいということなので、upper_bound(t)で$t$以下の数の総数を求めてupper_bound(t) >= kになるような最小の$t$を求めればよい。列全体をいくつかの（昇順の）部分列にわけて、upper_boundをそれぞれに対して計算して総和を取ることも可能。

1-basedで$k$番目に大きい数が$x$ということは$t$以上の数が$k$個存在するような最大の$t$が$x$に等しいということなので、N - lower_bound(t)で$t$以上の数の総数を求めてN - lower_bound(t) >= kになるような最大の$t$を求めればよい。列全体をいくつかの（昇順の）部分列にわけて、N-lower_bound(t)をそれぞれに対して計算して総和を取ることも可能。

列が降順にソートされている場合

• $x$以下でもっとも左にある数の位置: lower_bound(x)
• $x$以上でもっとも右にある数の位置: upper_bound(x)-1
• $x$より小さいもっとも左にある数の位置: upper_bound(x)
• $x$より大きいもっとも右にある位置の数: lower_bound(x)-1
• $x$以下の数の総数: N - lower_bound(x)
• $x$以上の数の総数: upper_bound(x)
• $x$より小さい数の総数: N - upper_bound(x)
• $x$より大きい数の総数: lower_bound(x)
• ちょうど$x$に等しい数の総数: upper_bound(x) - lower_bound(x)
• $x$に等しい数の存在する区間: [lower_bound(x), upper_bound(x))

累積和上のDP

元のDP配列$f$上の$\operatorname{f}[y] \mathrel{{+}{=}} \operatorname{f}[x]$という操作が、累積和$S$上では$\operatorname{S}[y] \mathrel{{+}{=}} S[x]$, $\operatorname{S}[y+1] \mathrel{{-}{=}} S[x]$に対応することを覚えておく。$S$の先頭に$0$を追加せず、$S[0] = f[0]$としたほうがわかりやすいことが多いと思う。

$S[x] = f[0] + ... + f[x]$とする。たとえば$x$を$[x+l, x+r)$に足す、つまり$f[x] = f[x-l] + ... + f[x-(r-1)]$という漸化式がなりたっている場合、もらうDPで考えると

$$\begin{aligned} S[0] &= f[0] \\ S[x] & = S[x-1] + f[x] \\ & = S[x-1] + f[x-l] + ... f[x-(r-1)] \\ & = S[x-1] + S[x-l] - S[x-r] \end{aligned}$$

配るDPで実装する場合、$S[x + l] \mathrel{{+}{=}} S[x], S[x+r] \mathrel{{-}{=}} S[x], S[x+1] \mathrel{{+}{=}} S[x]$と遷移すればいいことになる。

平方分割

バケットサイズを$B$とする。区間$[l, r)$を処理するときは$b_l = \lceil l/B \rceil, b_r = \lfloor r/B \rfloor$として

• $b_l > b_r$:
  • 区間$[l, r)$を処理
• $b_l \le b_r$:
  • 区間$[l, b_lB)$を処理
  • バケット列上の区間$[b_l, b_r)$を処理
  • 区間$[b_rB, r)$を処理

する。

引き算ができる場合は$[0, l), [0, r)$を処理するほうが簡単か。

巡回置換を戻す

巡回置換$(p_1, p_2, ..., p_k)$が配列上の部分列として現れている場合に、その部分を恒等に戻したい場合、$p_1とp_2$を交換して$p_2$と$p_3$を交換して……$p_{k-1}$と$p_{k}$を交換する。一般に$(p_1 p_2 ... p_k) = (p_{k-1}p_k)...(p_2p_3)(p_1p_2)$（操作としては左から右に適用することに注意）なので、その逆をやればよいということになる。

配列上の操作としては、配列$A$における$p_i$の初期位置を$v_i$として、$A[v_1]$と$A[v_2]$をスワップして$A[v_1]とA[v_3]$をスワップして……$A[v_1]$と$A[v_k]$をスワップすればよい。

2次元配列の回転

高さ$H$, 幅$W$の行列$A$を反時計回りに回転する。回転後の行列を$A'$とすると。添え字を0-basedとして

• 90°の回転: $A[i][j]:=A'[W−1−j][i]$
• 180°の回転: $A[i][j]:=A'[H−1−i][W−1−j]$
• 270°の回転: $A[i][j]:=A'[j][H−1−i]$

転置

• 左上-右下の対角線に関する転置: $A[i][j] = A'[j][i]$
• 左下-右上の対角線に関する転置: $A[i][j] = A'[W-1-i][H-1-j]$

グリッド上の正方形

グリッド上の正方形$S = \{0, 1, ..., N-1\}^2$について。

$S$上の点$(a, b)$を通る傾き-1の直線$x+y = a+b$は$S$上のマスを$\min(a+b+1, 2N - (a+b+1))$個含む。また、$(a,b)$を通る傾き1の直線$x-y=a-b$は$S$上のマスを$\min(N, |a-b|)$個含む。

$S$上の点$(a, b)$を通る直線$x-y=a-b$は、直線$x+y=|a-b|, x+y=2N - 2 - |a-b|$のそれぞれと正方形の端で交わる。

極座標と直交座標

complexに対する極座標はabsとphaseで求まる。逆に極座標からcomplexを得たい場合は(* scale (cis radian))とする。