実装でよくつまづいているポイントをメモ。
二乗すると$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))とする。
