C - Calendar Validator 解説 by en_translator
One can observe by explicitly writing down the matrix that the elements of \(A\) are pairwise distinct, that is, if \((i,j) \neq (k,l)\) then \(A_{i,j} \neq A_{k,l}\) is satisfied.
Therefore, given an element of \(A\), one can uniquely determine which column and row the element belongs. Specifically, denoting the value by \(x\), it belongs in the \(\left(\frac{x-1}{7}\right)\)-th row, rounded up, and in the (remainder of \((x-1)\) by \(7\), plus \(1\))-th column.
Therefore, it is sufficient to determine for each element of \(B\) which row and column it belongs, and check if they form a rectangular region.
Sample code (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M; cin >> N >> M;
vector<vector<int>> B(N,vector<int>(M));
for(int i=0; i<N; i++){
for(int j=0; j<M; j++) cin >> B[i][j];
}
vector<vector<int>> x(N,vector<int>(M)),y(N,vector<int>(M));
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
x[i][j] = (B[i][j]+6)/7;
y[i][j] = (B[i][j]-1)%7+1;
}
}
string ans = "Yes";
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(0 < i && x[i][j] != x[i-1][j]+1) ans = "No";
if(0 < j && y[i][j] != y[i][j-1]+1) ans = "No";
if(0 < j && x[i][j] != x[i][j-1]) ans = "No";
if(0 < i && y[i][j] != y[i-1][j]) ans = "No";
}
}
cout << ans << endl;
}
投稿日時:
最終更新: