D - Takahashi's Solitaire

コンテスト時間: 2022-11-12(土) 12:00 ~ 2022-11-12(土) 13:40 (100分) AtCoderホームへ戻る

D - Takahashi's Solitaire 解説

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $400$ 点

問題文

高橋君は $N$ 枚のカードを手札として持っています。 $i = 1, 2, \ldots, N$ について、 $i$ 番目のカードには非負整数 $A_i$ が書かれています。

高橋君は、まず手札から好きなカードを $1$ 枚選んで、テーブルの上に置きます。その後、高橋君は好きな回数（ $0$ 回でも良い）だけ、下記の操作を繰り返します。

最後にテーブルの上に置いたカードに書かれた整数を $X$ とする。手札に整数 $X$ または整数 $(X+1)\bmod M$ が書かれたカードがあれば、そのうち好きなものを $1$ 枚選んで、テーブルの上に置く。ここで、 $(X+1)\bmod M$ は $(X+1)$ を $M$ で割ったあまりを表す。

最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値を出力してください。

制約

$1 \leq N \leq 2 \times 10^5$
$2 \leq M \leq 10^9$
$0 \leq A_i \lt M$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

出力

答えを出力せよ。

入力例 1 Copy

Copy

9 7
3 0 2 5 5 3 0 6 3

出力例 1 Copy

Copy

高橋君が、まず $4$ 番目のカード（書かれた整数は $5$ ）をテーブルの上に置き、その後、以下の手順で操作を行う場合を考えます。

$5$ 番目のカード（書かれた整数は $5$ ）をテーブルの上に置く。
$8$ 番目のカード（書かれた整数は $6$ ）をテーブルの上に置く。
$2$ 番目のカード（書かれた整数は $0$ ）をテーブルの上に置く。
$7$ 番目のカード（書かれた整数は $0$ ）をテーブルの上に置く。

このとき、最終的に手札に残ったカードは、 $1, 3, 6, 9$ 枚目のカードであり、それらに書かれた整数の総和は $3 + 2 + 3 +3 = 11$ です。これが、最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値です。

入力例 2 Copy

Copy

1 10
4

出力例 2 Copy

Copy

入力例 3 Copy

Copy

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

出力例 3 Copy

Copy

Score : $400$ points

Problem Statement

Takahashi has $N$ cards in his hand. For $i = 1, 2, \ldots, N$ , the $i$ -th card has an non-negative integer $A_i$ written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

Let $X$ be the integer written on the last card put on the table. If his hand contains cards with the integer $X$ or the integer $(X+1)\bmod M$ written on them, freely choose one of those cards and put it on the table. Here, $(X+1)\bmod M$ denotes the remainder when $(X+1)$ is divided by $M$ .

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

$1 \leq N \leq 2 \times 10^5$
$2 \leq M \leq 10^9$
$0 \leq A_i \lt M$
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $M$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

Output

Print the answer.

Sample Input 1 Copy

Copy

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1 Copy

Copy

Assume that he first puts the fourth card ( $5$ is written) on the table and then performs the following.

Put the fifth card ( $5$ is written) on the table.
Put the eighth card ( $6$ is written) on the table.
Put the second card ( $0$ is written) on the table.
Put the seventh card ( $0$ is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is $3 + 2 + 3 +3 = 11$ . This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2 Copy

Copy

1 10
4

Sample Output 2 Copy

Copy

Sample Input 3 Copy

Copy

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

Sample Output 3 Copy

Copy