Official
B - Discord Editorial by m_99
すべての \((x,y)\) の組に対して、\(M\) 回の撮影の中に \(x\) と \(y\) が連続しているものがあるかどうかを調べればよいです。
\(x, y\) の順番を入れ替えたものは区別しないため、たとえば \(x \lt y\) というルールの下で数えたり、\(x \neq y\) というルールの下で数えた上で求められた答えを \(2\) で割ることで \(x\lt y\) の場合と \(y\lt x\) の場合でのダブルカウントを考慮する必要があります。実装例では外側から \(2\) 番目のループの添え字の初期値を工夫することで \(x \lt y\) というルールの下で数えています。
実装例(C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int N,M;
cin>>N>>M;
vector a(M,vector<int>(N));
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cin>>a[i][j];
}
}
int ans = 0;
for(int i=1;i<=N;i++){
for(int j=i+1;j<=N;j++){
bool flag = false;
for(int k=0;k<M;k++){
for(int l=0;l<N-1;l++){
if(a[k][l]==i&&a[k][l+1]==j)flag = true;
if(a[k][l]==j&&a[k][l+1]==i)flag = true;
}
}
if(!flag)ans++;
}
}
cout<<ans<<endl;
return 0;
}
posted:
last update: