Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 277 D問題 Takahashi's Solitaire

AtCoder ABC277 ABC D問題 400 pts

問題

提出解答

問題の概要

$N$ 枚のカードを手札として持っており, $i$ 枚目のカードには整数 $A_i$ が書かれている.

最初, 手札から好きなカードを1枚テーブルに置く. その後, 好きな回数以下の行動を行うことができる.

最後に出したカードに書かれている整数を $X$ としたとき, 手札にある $X$ または $(X+1) \pmod{M}$ と書かれているカードをテーブルに出す.

最終的に残った手札に書かれているカードの総和の最小値を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$2 \leq M \leq 10^9$
$0 \leq A_i \lt M$

解法

最終的にカードは手札か場札になるので, 手札に書かれている整数の総和を最小にすることは場札にあるカードの整数の総和を最大にすることと同等である. 以降では場札になったカードの整数の総和の最大値を求めることにする.

(1) 任意の $0$ 以上 $M$ 未満の整数 $m$ に対して, $m$ と書かれたカードが $1$ 枚以上ある場合

次のようにして $N$ 枚のカードを全て場札にすることができる.

$0 \to 0 \to \cdots \to 0 \to 1 \to \cdots \to 1 \to 2 \to \cdots \to (M-2) \to (M-1) \to \cdots \to (M-1)$

よって, 答えは $0$ である.

(2) $0$ 以上 $M$ 未満の整数 $m$ で, $m$ と書かれたカードが手札に存在しないような $m$ が存在する場合.

$N$ 枚のカードを次のようにしてグルーピングできる.

$B_{1,1}, \dots, B_{1,r_1}$
$B_{2,1}, \dots, B_{2,r_2}$
$\vdots$
$B_{t,1}, \dots, B_{t,r_t}$

ただし,

$(B_{1,1}-1)$ と書かれたカードが手札にない. なお, $B_{1,1}=0$ のときは $B_{1,1}-1=M-1$ とする.
$i=1,2, \dots, t, j=1,2, \dots, r_i-1$ に対して, $B_{i,j+1}=B_{i,j}$ または $B_{i,j+1}=B_{i,j}+1$ . なお, $B_{i,j}=M-1$ のときは $B_{i,j}+1=0$ とする.
$i=1,2, \dots, t-1$ に対して, $B_{i,j+1} \neq B_{i,j}, B_{i,j}+1$ . なお, $B_{i,j}=M-1$ のときは $B_{i,j}+1=0$ とする.

を満たすようにする. このようにすると, $B_{i,j}$ は $i$ の入れ替えの違いを除いて一意に定まる.

このとき, 相異なるブロックにあるカードを両方場札にすることは不可能であり, $B_{i,1}, \dots, B_{i,r_i}$ の順に出すことで1つのブロックにあるカードを全て場札にすることができる.

これにより, カードに書かれた整数の総和が最大であるようなブロックにあるカードを場札にするのが最適である. つまり,

$\displaystyle \sum_{i=1}^N A_i-\max_{i=1,2, \dots, t} \sum_{j=1}^{r_t} B_{i,j}$

が答えになる.

計算量については $(B_{i,j})$ を求めるパートがボトルネックになり, 適切な観点によるソートを実行することにより, $O(N \log N)$ 時間で実行できる.