集合 \(A\) と整数 \(x\) に対し \(A + x\) で \( \{a + x | a \in A\}\) を表します。

以降すべて \(\mathbb{Z}/M\mathbb{Z}\) で考えます。(\(\bmod M\) で整数を同一視します。)

構成方法を実際に示します。

ある整数 \(d(0 \le d < M)\) と \(F \subset \{A_i\}, |F| = K\) であって、 \(F + d \subset \{B_i\}\) を満たす \(F\) を取ります。

\(F\) が取れることの証明と構築方法

\(d(0 \le d < M)\) に対して \(p_d = |A \cap (B - d)|\) とします。

\(d\) を動かしたとき、\(B - d\) の各要素は \(A\) の各要素と一回ずつ交わるので、\(\sum_{d = 0}^{M - 1} p_d = N^2\) がわかります。

鳩ノ巣原理より、\(p_d \ge \left\lceil\dfrac{N^2}{M} \right\rceil= K\) を満たす \(d\) が存在します。このような \(d\) を用いれば \(F\) を実際に構築できます。 これは、高速フーリエ変換を用いることで \(\mathcal{O}(M log M)\) で計算することができます。

\(C_i = F_{i} + \dfrac{d}{2} = A_{T_i} + \dfrac{d}{2} = B_{S_i} - \dfrac{d}{2}\) とします。

今、\(L_i\) と \(R_i\) を結んだグラフを考えます。

このグラフはどの頂点の次数も \(2\) であることからいくつかのサイクルに分解することができます。 サイクルが有向サイクルになるように、辺に向きを付けます。

\(X\) から \(Y\) に向かう辺があったとき、その辺に対して \(A_{T_X}\) と \(B_{S_Y}\) を割り当てればよいです。

計算量は \(\mathcal{O}(M log M + N + K)\) です。