最後に残る数 2

答えは $\min(A_1,\ldots,A_N)+N-1$ である。

ある操作の直前の最小値を $m$、取り除く値を $x$ とする。残る値 $y$ には次の二通りがある。

• $y\le x$ の場合、$y+1\ge m+1$ となる。
• $y>x$ の場合、値は変わらない。整数であり なので、 が成り立つ。

したがって最小値は毎回少なくとも1増える。操作回数はちょうど $N-1$ 回なので、最後の値は初期最小値に $N-1$ を足した値以上になる。

この下限を達成するには、毎回現在の最大値を一つ取り除けばよい。残るすべての値は取り除いた値以下なので、それぞれ1増える。最小値は少なくとも一つ残る。最大値の削除が最小値の削除でもあるなら、すべての値が等しく、別の最小値が残るからである。よって毎回最小値がちょうど1増え、下限を達成できる。

$N=1$ なら操作はなく、同じ式が成り立つ。単一サブタスクの想定解は入力を読みながら最小値だけを保存する。時間計算量は $O(N)$、追加領域は $O(1)$。

素朴解法は毎回最大値を探して削除し、残る値を一つずつ更新する。正しいが時間計算量は $O(N^2)$、領域計算量は $O(N)$ となり、最大入力では時間制限を超える。

各整数が増える回数は最大 $N-1$ 回なので、答えもシミュレーション中の値も最大 $10^9+200\,000-1=1\,000\,199\,999$ である。すべての整数計算は符号付き64ビットの範囲内に収まる。

Solution written by GPT6