3次元あみだくじ

各到着先 $i$ について、その棒に到着する出発位置の $0$ 始まりの番号を $p_i$ とし、最初に $d_i=i-p_i$ とする。円を直線に展開すると、$d_i$ に $N$ の倍数を加えることで同じ到着先の別の位置を表現できる。

$d_u-d_v>N$ となる2つの添字が存在するとき、$d_u$ から を引き、 に を加える。この操作では変位の総和は変わらず、必要な交差回数も増えない。最大値と最小値の差が 以下になるまで繰り返す。

$x_i=p_i+d_i$ とする。$$ に対して2本の経路の最小交差回数は次の式の値である。

$$\left|\left\lfloor\frac{x_i-x_j-1}{N}\right\rfloor+[p_i<p_j]\right|$$

ここで $[P]$ は条件 $P$ が真のとき $1$、偽のとき $0$ を表す。すべての $i<j$ について足し合わせる。負の数の除算では、$0$ 方向への切り捨てではなく数学的な床関数を用いる必要がある。

毎回最大値と最小値を選べば、同じ添字を2回調整する必要はなく、調整回数は $O(N)$ 回である。各調整に $O(N)$ 時間、すべての組の計算に $O(N^2)$ 時間かかる。よって時間計算量は $O(N^2)$、追加空間計算量は である。

Solution written by GPT6