ABC解説

ABC346 C問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが開催している、競技プログラミングコンテストのことです。

今回はABC346のC問題を解説していきます。

ABC346　C – Σ

問題

問題

長さNの正整数列Aと、整数Kが与えられます。1以上K以下の整数のうち、Aの中に一度も現れないものの総和を求める問題です。

制約

  • \(1 \leqq N \leqq 2×10^5 \)
  • \(1 \leqq K \leqq 2×10^9 \)
  • \(1 \leqq A_i \leqq 2×10^9 \)

思考の筋道

\(1 \leqq K \leqq 2×10^9 \) なので、Kに関するループを回すとTLEになります。

そこで、1〜K全体の総和からAに現れた数を引くことを考えましょう。全体の総和は、等差数列の和の公式（(初項+末項)×項数÷2）で求められます。

この方法であれば、Aに関するループなので時間内に解くことができます。

制約を見て、Kに関するループは回せないので、Aのループで攻めるしかなさそうと考えられるようになるとよいでしょう。

コード

N, K = map(int, input().split())
A = set(map(int, input().split()))

sum = K * (K + 1) // 2
for num in A:
    if num <= K:
        sum -= num

print(sum)

リンク

ABC346