問題一覧 > 通常問題

No.1470 Mex Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 182
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi nok0nok0
5 ProblemId : 5724 / 出題時の順位表
問題文最終更新日: 2021-04-09 23:36:51

問題文

$N$ 個の $1$ 以上の整数からなる数列 $A_1 , A_2 , \cdots , A_N$ が与えられます。

また $\mathrm{mex} (i,j)$ を $1$ 以上の整数で $i$ でも $j$ でもないもののうち最小のものとします。

$1 \leq i < j \leq N$ を満たす全ての整数対 $(i,j)$ に対し、 $\mathrm{mex} (A_i,A_j)$ を足し合わせた値を求めてください。

入力

$N$
$A_1\ \ A_2\ \ \cdots\ \ A_N$

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9(1 \leq i \leq N)$
  • 入力は全て整数

出力

$1 \leq i < j \leq N$ を満たす全ての整数対 $(i,j)$ に対し、 $\mathrm{mex} (A_i,A_j)$ を足し合わせた値を出力し、最後に改行してください。

サンプル

サンプル1
入力
3
2 1 1
出力
8

$1 \leq i < j \leq N$ を満たす整数対は $(1,2),(1,3),(2,3)$ の $3$ つです。

  • $\mathrm{mex} (A_1,A_2)= \mathrm{mex} (2,1)=3$
  • $\mathrm{mex} (A_1,A_3)= \mathrm{mex} (2,1)=3$
  • $\mathrm{mex} (A_2,A_3)= \mathrm{mex} (1,1)=2$

であるので、答えは $3+3+2=8$ です。

サンプル2
入力
5
1 1 1 1 1
出力
20

$1 \leq i < j \leq N$ を満たす全ての整数対に対し、 $\mathrm{mex} (A_i,A_j)=2$ となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。