https://rubikun.hatenablog.jp/entry/2026/01/22/210040

問題

解法

N 通り試す方法は理解しているものとします。

適当に rotate して min ( A[0], A[1], ..., A[N-1] ) >= max ( A[N], A[N+1], ..., A[N+N-1] ) にできるので、しておく。B と C もソートしておく。

(これさえできれば A の条件もう少し弱くても O(NlogN) になると思っています。)

B と C を swap して 2 回解くとして、0 <= s < N なる s を用いて、[s, s+N) を B と、[s+N , s+N+N) を C とマッチさせるものについて調べる。

このとき、 s を increment すると、B の各要素のマッチ相手の値は単調減少、C の各要素のマッチ相手の値は単調増加する。

s を固定したときの B のマッチ相手を X , C のマッチ相手を Y とする。(どちらも長さ N のソートされた配列)

| x - y | = max ( x - y , y - x ) を用いると、疲労度は

max ( B[i] - X[i] , X[i] - B[i] , C[i] - Y[i] , Y[i] - C[i] )

= max ( max( B[i] - X[i] , Y[i] - C[i] ) , max ( X[i] - B[i] , C[i] - Y[i] ) )

と書ける。

s を increment すると、max 内の 1 個目の max は単調増加、2 個目の max は単調減少になるため、1 個目 - 2 個目 >= 0 となるギリギリの s を二分探索で求めれば良い。

X, Y の取得は単調列 2 個のマージなので O(N) でできて、トータル O(NlogN) で解けた。

提出 (fastest)