AtCoder Beginner Contest 226 B - Counting Arrays
問題の要約
1からNまでの番号のついたN個の数列が与えられる。
数列iは、長さLiでj(1<=j<=Li)番目の要素がai.jであるような数列である。
数列iと数列jは,Li=Ljかつすべてのk(1<=k<=Li)に対してai,k=aj,kが成り立つとき同じであるとみなす。
同じ数列は1種類として数えるとき,全部で何種類の数列があるか?
制約
1<=N<=2*10^5
1<=Li<=2*10^5(1<=i<=N)
0<=ai,j<=10^9(1<=i<=N,1<=j<=Li)
入力
N
L1 a1,1 a1,2 ... a1,L1
L2 a2,1 a2,2 ... a2,L2
.
.
.
LN aN,1 aN,2 ... aN,LN
考え方
1,数列の番号を1ずらす。
1<=i<=N => 0<=i<=N-1
2,各数列の要素の番号を1ずらす。
1<=j<=Li => 0<=j<=Li-1
3,何種類の数列があるか問われているので、N個の数列はソートしてよいが、数列の要素はソートしてはいけない。
4,ソートしたN個の数列から重複を削除すればよい。
5,C++には重複削除にはunique関数が使える。
実際のプログラム
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long N;
cin >> N;
vector<vector<long long>> Ls;
for(long long i = 0; i < N; i++){
long long Li;
cin >> Li;
vector<long long> L(Li);
for(long long j = 0; j < Li; j++){
cin >> L[j];
}
Ls.push_back(L);
}
sort(Ls.begin(), Ls.end());
Ls.erase(unique(Ls.begin(), Ls.end()), Ls.end());
cout << Ls.size() << endl;
return 0;
}