Official

B - Counting Arrays Editorial by Nyaan


問題文の指示通りに配列の個数を数えればよいですが、重複する列を取り除く部分のどのように実装するのかがこの問題のポイントです。

まずいのは「配列を入力するたびに、以前の配列をすべて走査して同じ配列が無いのか確認する」というやり方で、これでは配列 を \(1\) 個入力するたびに要素数を \(n\) として \(\mathrm{O}(n)\) の計算量が掛かってしまうため、全体で \(\mathrm{O}(N^2)\) の計算量となり TLE してしまいます。

これを回避するためには集合を管理するデータ構造を使うのが簡明です。たとえば C++ では std::set を利用すれば、要素の重複無しでの追加を O(log n) 要素数を \(n\) として \(\mathrm{O}(\log n)\) 回の配列の比較で行うことができるので、全体で O(N log N) \(\mathrm{O}( (N+ \sum_i L_i) \log N)\) に改善できて AC することができます。

C++ による実装例は以下の通りです。

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
  int N;
  cin >> N;
  set<vector<int>> st;
  for(int i = 0; i < N; i++) {
    int L;
    cin >> L;
    vector<int> v(L);
    for (auto& x : v) cin >> x;
    st.insert(v);
  }
  cout << st.size() << "\n";
}

posted:
last update: