[ABC346 C] Σ

https://atcoder.jp/contests/abc346/tasks/abc346_c

1..K から配列 A の要素を除いた合計を求める問題。

要点

• 計算順序を入れ替えてみる
• 1..N の合計は(奇数偶数の区別なく) N * (N + 1) / 2 で求まる

[*1..100].sum        # => 5050
100 * (100 + 1) / 2  # => 5050

[*1..101].sum        # => 5151
101 * (101 + 1) / 2  # => 5151

解法1. 配列同士で減算 (TLE)

N, K = gets.split.collect(&:to_i)  # => [4, 5]
A = gets.split.collect(&:to_i)     # => [1, 6, 3, 1]
p ([*1..K] - A).sum                # => 11

最初に実装したのは入力例3でフリーズした。

解法2. 減算の替わりに 0 で埋める (TLE)

N, K = gets.split.collect(&:to_i)  # => [4, 5]
A = gets.split.collect(&:to_i)     # => [1, 6, 3, 1]
b = [*0...K.next]                  # => [0, 1, 2, 3, 4, 5]
A.find_all { |e| e <= K }.each { |e| b[e] = 0 }
p b.sum                            # => 11

途中で配列のリサイズが起きているのではないかと考えて、削除の替わりに 0 を埋めてみたがとくに効果はなかった。

解法3. 合計から減算 (AC)

N, K = gets.split.collect(&:to_i)       # => [4, 5]
A = gets.split.collect(&:to_i)          # => [1, 6, 3, 1]
t = K * (K + 1) / 2                     # => 15
a = A.find_all { |e| e <= K }.uniq.sum  # => 4
p t - a                                 # => 11

極端に考えて K が 2000000000 で A が空だとすると 2000000000 回足し算をすることになるので 1..K の合計を先に計算した方がいいのでは？ となってやっと見えた。なお uniq は to_set でもいい。