概要

与えられた \(N\) 個の品種番号の中から重複を除き、「何種類の品種があるか」と「それらの品種番号の合計」を求める問題です。

考察

この問題のポイントは、「同じ品種番号が複数回現れたとき、2回目以降を無視する」というルールです。これは言い換えると、与えられた数値の集合から重複を取り除いて一意な値（ユニークな値）だけを取り出す操作になります。

例えば、入力が 1, 2, 1, 3, 2 だった場合： - 1番目の 1: 初めてなので採用 - 2番目の 2: 初めてなので採用 - 3番目の 1: すでに出ているので除外 - 4番目の 3: 初めてなので採用 - 5番目の 2: すでに出ているので除外

最終的に図鑑に載るのは {1, 2, 3} の 3 枚で、合計は \(1 + 2 + 3 = 6\) となります。

制約に注目すると、花の数 \(N\) は最大 \(2 \times 10^5\) と比較的大きいですが、品種番号 \(S_i\) は \(1\) から \(100\) という非常に狭い範囲に収まっています。そのため、重複を効率的に管理すれば制限時間内に十分間に合います。

アルゴリズム

重複を管理するために、プログラミング言語の標準機能である「集合（set）」というデータ構造を利用するのが最も効率的です。

1. 空の集合（set）を用意します。
2. 与えられた \(N\) 個の品種番号を順番に確認し、集合に追加していきます。
   • 集合は同じ値を複数保持しない性質があるため、自動的に重複が排除されます。
3. すべての品種番号を確認した後：
   • 枚数: 集合に含まれる要素の数
   • 合計: 集合に含まれる要素の総和 を計算して出力します。

また、品種番号が 100 までと小さいため、長さ 101 の配列（バケツ）を用意して、出現した番号のインデックスにチェックを入れる方法でも同様に解くことができます。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を読み込み、集合に追加する操作は平均して \(O(1)\) で行えるため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\) または \(O(\max(S_i))\)
  • 入力データをすべて保持する場合は \(O(N)\)、集合や配列に格納されるユニークな品種数のみを考慮する場合は \(O(\max(S_i))\) です。今回の制約ではどちらも十分にメモリに収まります。

実装のポイント

• 効率的な入力: \(N\) が \(2 \times 10^5\) と大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込む方が実行速度が速くなります。

• setの活用: set(s_values) と記述するだけで、リストから重複を削除した集合を簡単に作成できます。

• 合計の算出: 集合に対しても sum() 関数を適用できるため、簡潔に合計を求めることができます。

  ソースコード

import sys

def main():
    # 入力をすべて読み込み、空白で分割してリスト化する
    # Nが大きくても効率的に処理するために sys.stdin.read を使用
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    # 1つ目の要素は N (花の個数)
    # n = int(input_data[0])
    
    # 2つ目以降の要素は品種番号 S_i
    # set を使用することで重複を除去し、各品種の最初に見つけたものだけを管理する
    s_values = map(int, input_data[1:])
    unique_species = set(s_values)
    
    # 図鑑に載せる花の枚数は、一意な品種番号の個数
    count = len(unique_species)
    
    # 品種番号の合計を計算
    total_sum = sum(unique_species)
    
    # 結果をスペース区切りで出力
    print(f"{count} {total_sum}")

if __name__ == "__main__":
    main()

この解説は gemini-3-flash-preview によって生成されました。