概要

見つけた順に並ぶ花の品種番号列から、各品種について「最初に出てきた1回だけ」を採用し、採用枚数と品種番号の合計を求めます。

考察

この問題で必要なのは「その品種番号をすでに図鑑に載せたかどうか」の判定です。
同じ品種が何回出ても、最初の1回だけ数え、以降は無視します。

例えば、\(S = [3, 1, 3, 2, 1]\) のとき
- 3（初登場）→採用
- 1（初登場）→採用
- 3（2回目）→不採用
- 2（初登場）→採用
- 1（2回目）→不採用
なので、採用枚数は \(3\)、合計は \(3+1+2=6\) です。

素朴に「今まで採用した品種のリストに含まれるか」を毎回線形探索すると、最悪で \(O(N^2)\) になり \(N \le 2 \times 10^5\) では間に合いません。
そこで、「品種番号は \(1 \sim 100\) と小さい」ことを利用し、配列で出現済み管理をすれば各回 \(O(1)\) で判定できます。

アルゴリズム

1. 長さ \(101\) の真偽配列 seen を用意し、すべて False にする（seen[x] が「品種 \(x\) を採用済みか」を表す）。
2. cnt = 0（採用枚数）, total = 0（合計）で初期化する。
3. 入力列を先頭から順に見て、品種番号を \(x\) とする。
   • もし seen[x] が False なら初登場なので採用し、seen[x]=True、cnt += 1、total += x。
   • そうでなければ既に採用済みなので何もしない。
4. 最後に cnt と total を出力する。

計算量

• 時間計算量: \(O(N)\)（各要素を1回ずつ、\(O(1)\) 判定）
• 空間計算量: \(O(1)\)（seen はサイズ \(101\) の固定配列）

実装のポイント

• 品種番号が \(1 \sim 100\) なので、seen = [False] * 101 のように固定長配列で管理すると簡単・高速です（添字をそのまま品種番号に対応させる）。

• 入力が大きいので、Pythonでは sys.stdin.buffer.read() を使ってまとめて読み込むと安定して高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    s = data[1:1+n]

    seen = [False] * 101
    cnt = 0
    total = 0
    for x in s:
        if not seen[x]:
            seen[x] = True
            cnt += 1
            total += x

    print(cnt, total)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。