概要

見つけた花の中から、各品種について最初に見つけたものだけを選び、その枚数と品種番号の合計を求める問題です。

考察

この問題のポイントは「同じ品種番号の花が複数回出てきたとき、最初の1回だけを採用する」という点です。

例えば、花の品種番号が [3, 1, 2, 1, 3, 4] の順で見つかった場合を考えてみましょう： - 1番目: 品種3 → 初めて見た → 採用 - 2番目: 品種1 → 初めて見た → 採用 - 3番目: 品種2 → 初めて見た → 採用 - 4番目: 品種1 → 既に見た → 除外 - 5番目: 品種3 → 既に見た → 除外 - 6番目: 品種4 → 初めて見た → 採用

結果：枚数は \(4\) 枚、品種番号の合計は \(3 + 1 + 2 + 4 = 10\) となります。

なぜ集合(set)を使うのか？

「既に見たかどうか」を効率的に判定する必要があります。

• 素朴な方法（リストで管理）: 毎回リストを全て走査して確認 → 1回の判定に \(O(N)\) かかり、全体で \(O(N^2)\)
• 集合(set)を使う方法: 集合への追加・検索は平均 \(O(1)\) → 全体で \(O(N)\)

\(N\) が最大 \(2 \times 10^5\) なので、\(O(N^2)\) では間に合わない可能性がありますが、\(O(N)\) なら十分高速です。

アルゴリズム

1. 「既に見た品種番号」を管理するための集合 seen を用意する
2. 花の枚数をカウントする変数 count と、品種番号の合計を保持する変数 total を \(0\) で初期化
3. 花を見つけた順に1つずつ処理：
   • その品種番号が seen に含まれていなければ：
     • seen にその品種番号を追加
     • count を \(1\) 増やす
     • total にその品種番号を加える
   • 既に seen に含まれていれば何もしない（重複なので除外）
4. 最終的な count と total を出力

計算量

• 時間計算量: \(O(N)\)
  • 各花について、集合への追加・検索は平均 \(O(1)\) で行える
  • \(N\) 個の花を順番に処理するので、全体で \(O(N)\)
• 空間計算量: \(O(\min(N, 100))\)
  • 集合 seen には最大でも100種類（品種番号は1〜100）しか入らない
  • 実質的には \(O(1)\)（定数）とも言える

実装のポイント

• Pythonの set は、要素の追加（add）と存在確認（in）が平均 \(O(1)\) で行えるため、このような「重複を除く」処理に最適

• if s not in seen: で「まだ見ていない品種か」を判定し、条件を満たす場合のみカウントと合計を更新する

• 品種番号の範囲が1〜100と小さいため、配列（サイズ101のリスト）を使って seen[s] = True のように管理する方法でも実装可能

  ソースコード

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)

---

この解説は claude4.5opus によって生成されました。