E - 放課後

Contest Duration: 2019-04-30(Tue) 04:00 - 2019-04-30(Tue) 09:00 (local time) (300 minutes) Back to Home

E - 放課後 Editorial

Time Limit: 1 sec / Memory Limit: 256 MB

配点: $300$ 点

この問題の解説はこちら。

問題文

※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。

きたむーは高校の競技プログラミング部に所属し、放課後も熱心にプログラミングに取り組んでいた。しかし最近、きたむーには彼女ができたようだ。

デートがしたい！　デートがしたい！　デートがしたい！

デートに着実に蝕まれていくプログラミング学習の時間。このままではきたむーのレートが落ちてしまうことに危機感を覚えたあなたは、彼の放課後のスケジュールを管理してあげることにした。

あなたは以下の点に配慮して明日以降の $N$ 日分のスケジュールを立てることにした。

きたむーそれぞれの日の放課後に「デート」「競プロ」のうちいずれか片方の行動をとる。

きたむーは $A$ 日以上デートできないと、愛が足りずに動けなくなってしまうので、 $A$ 日に一度は必ずデートする。

このカップルには明日から $N$ 日以内に $B$ 回の記念日があり、それぞれ $D_1,D_2,\cdots,D_B$ 日後である。この日には必ずデートを行う。 $D_i$ は互いに異なる。

なお、きたむーは今日デートしており、彼の高校に休日はないものとする。

あなたはきたむーが競プロに取り組む日数を最大化したい。

制約

入力される値はすべて整数である
$1 \leq N \leq 10^{18}$
$1 \leq A \leq N$
$0 \leq B \leq min(N,2 \times 10^5)$
$1 \leq D_i \leq N$ $(1 \leq i \leq B)$
$D_i \neq D_j$ $(1 \leq i,j \leq B$ かつ $i \neq j)$
入力はすべて整数

入力

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

 $N$   $A$   $B$ 
 $D_1$   $D_2$   $\cdots$   $D_B$

出力

きたむーにプログラミング学習をさせることができる日数の最大値を $1$ 行で出力せよ。

入力例 1Copy

Copy

10 4 2
4 6

出力例 1Copy

Copy

明日から $10$ 日間のスケジュールを考えるが、 $4$ 日以上競プロが連続してはならず、 $4$ 日後、 $6$ 日後の $2$ 日の記念日がある。競プロをP、デートをDと表記するなら、例えば、PPPDPDPPPDとスケジュールを組むことで $7$ 日競プロに取り組ませることができる。

入力例 2Copy

Copy

10 1 0

出力例 2Copy

Copy

寂しがりすぎ。

入力例 3Copy

Copy

5 2 5
1 2 3 4 5

出力例 3Copy

Copy

記念日多すぎ。

入力例 4Copy

Copy

10 5 3
4 3 7

出力例 4Copy

Copy

入力例 5Copy

Copy

100 16 11
90 98 88 82 40 16 32 45 87 67 48

出力例 5Copy

Copy