概要

与えられた花の品種番号のリストから、初めて出現した品種のみを選んでその個数と合計を求める問題。

考察

この問題では、各品種番号について「すでに見たことがあるか」を効率よく管理する必要があります。
例えば、花の品種番号が [1, 3, 1, 2, 3] のように与えられたとき、図鑑に載せるのは「最初に登場した品種」である [1, 3, 2] です。
このとき、枚数は \(3\) 枚、合計は \(1 + 3 + 2 = 6\) となります。

素朴な方法として、「今見ている花の品種が、それ以前に出現しているか」を毎回調べるという方法があります。しかし、これは最悪の場合、各要素に対して過去すべての要素を確認する必要があり、時間計算量が \(O(N^2)\) になってしまいます。制約では \(N\) が最大で \(2 \times 10^5\) なので、これでは間に合いません（TLE）。

そこで、各品種が「すでに見たことがあるか」を高速に判定する方法が必要になります。このために使えるのが 集合（set） です。集合は要素の存在確認や追加が平均的に \(O(1)\) で行えるので非常に効率的です。

アルゴリズム

1. 入力として花の品種番号のリストを受け取る。
2. 「すでに見た品種」を記録するための集合 seen を用意する。
3. 図鑑に載せる花の枚数 count と品種番号の合計 total を初期化する。
4. 各花の品種番号に対して以下を行う：
   • その品種が seen に含まれていない場合：
     • seen に追加
     • count を1増やす
     • total にその品種番号を加える
5. 最後に count と total を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （品種番号の種類数は最大で100なので、setのサイズも定数扱いできる）

実装のポイント

• Pythonの set を使うことで、要素の存在確認と追加を高速に行う。
• 品種番号の範囲が \(1\) 〜 \(100\) と小さいため、空間計算量も実質的に定数となる。

## ソースコード

```python
N = int(input())
S = list(map(int, input().split()))

seen = set()
count = 0
total = 0

for s in S:
    if s not in seen:
        seen.add(s)
        count += 1
        total += s

print(count, total)

この解説は qwen3-coder-480b によって生成されました。