Official

C - Calendar Validator Editorial by penguinman


実際に紙に書き出してみると分かりますが、\(A\) の要素は互いに異なる、すなわち \((i,j) \neq (k,l)\) ならば \(A_{i,j} \neq A_{k,l}\) が満たされます。

故に \(A\) のある要素が与えられたとき、それが何行目何列目の要素なのかは一意に定まります。具体的にはその値を \(x\) とした場合、その行数は \(\frac{x-1}{7}\) の小数点以下切り上げとなり、またその列数は \(x-1\)\(7\) で割ったあまりに \(1\) を足したものになります。

よって \(B\) の各要素についてそれが本来 \(A\) の何行目何列目に存在しているかを求め、それらが矩形領域を成しているかを判定すればよいです。

実装例 (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;
}

posted:
last update: