# ARC201-D Match, Mod, Minimize

https://atcoder.jp/contests/arc201/tasks/arc201_d

## 問題文

長さ $N$ の整数列 $\{A_i\},\{B_i\}$ と正整数 $M$ が与えられる。

$A$ を自由に並び替えて $\max_i ((A_i+B_i) \bmod M)$ を最小化せよ。

## 考察

答え $x$ を決め打ち、$\forall i,((A_i+B_i) \bmod M) \leq x$ と出来るか考える。

$C_i := (M-A_i) \bmod M$ と置くと条件は $C_i \leq B_i \leq C_i+x$ 、つまり円環上の区間内に含まれることと言い換えられる。

Hallの定理から、任意の添え字集合 $S \subset [n]$ に対し $|S| \leq \#\{j \colon \exists i \in S, C_i \leq B_i \leq C_i+x\}$ が成り立てばよい。

ここで、一般的なテクとして $C_i\ (i \in S)$ を全て含む集合 $X$ をいくつかの円環上の区間のunionで表したとき、$S$ が条件を満たさないならば、構成する区間の中にinvalidなものが存在する。よって、$X$ として考えるべきは円環上の区間だけで良くなる。

また、端点が $C_i$ でない値のときは $|S|$ を減らさずに区間を縮められるので、 $X=[C_i,C_j]$ のような形のみを考えればよいことになる。

結局、この判定は次の部分問題に帰着される。

- 円環上の区間 $[L,R]$ であって、$[L,R]$ に含まれる $C_i$ の個数の方が $[L,R+x]$ に含まれる $B_i$ の個数より多いものが存在するか判定せよ。

これは、前者-後者を累積和の形で書くと変数分離が出来るので、$R=C_j$ を全探索することで解くことが出来る。計算量は $O(N \log N \log M)$ となる (おそらく $O(N\log N+N \log M)$ に落とすことも可能)。

## 実装

https://atcoder.jp/contests/arc201/submissions/67026219