765-1e8STARS

解説

方針（概要）

• 各日ごとに観測できた星の番号が与えられる。
• 目的は 「異なる星の個数」（重複を 1 つと数える）の算出。
• 観測した番号をすべて 1 本の列に集め、重複を除いた要素数を数えればよい。

$S_{i,j}$ の範囲は $[1, 765 \times 10^8]$ と大きいが、必要なのは「出現した番号の集合の大きさ」だけであるため、集合型（set など）に入れてサイズを取るのが最短。

計算量

• $1 ≤ N ≤ 39$、各日 $1 ≤ K_i ≤ 39$ より、総観測数 $M = \sum_{i=1}^{N} K_i \leq 39 \times 39 = 1521$ と小さい。
  • set を使えば $O(M)$ 程度で間に合う。
  • たとえ set を使わず $O(M^2)$ の素朴な重複チェックでも十分間に合う。

実装例は以下のようになります。