AtCoder Beginner Contest 225 C - Calendar Validator
問題の要約
10^100行7列の行列Aがあり,任意の整数対(i,j)(1<=i<=10^100,1<=j<=7)についてその成分は(i-1)*7+j。
N行M列の行列Bが与えられるので,BがAの一部の短形領域を(向きを変えずに)切り出したものであるかを判定しろ。
制約
1<=N<=10^4
1<=M<=7
1<=Bi,j<=10^9
入力
N M
B1,1 B1,2 ... B1,M
B2,1 B2,2 ... B2,M
.
.
.
BN,1 BN,2 ... BN,M
出力
BがAから一部の短形領域を切り出したものであればYesと,そうでなければNoと出力。
考え方
1,任意の整数対(i,j)のiとjを1つずらす。しかし成分はそのまま。
1<=i<=10^100,1<=j<=7 => 0<=i<=10^100-1,0<=j<=6
よって,成分はi*7+j+1となる。
2,行列Aと行列Bを比較したいが,行列Aは10^100行あるのでむり。
しかし,Bi,jが10^9までなので,この行を計算すると(10^9-1)/7=142857142である。
この数も行列同士の比較を考えると難しい。
3,どうにかしてBの行と列でBの本当の数値行列をつくりたい。これをBtrueとする。
4,まずBの列数がAの列数を超えていないか確認する。
Bの始まりの列はB0,0から(B0,0-1)%7で計算できる。これをmとおく。
m+M-1<=6ならばok,7<=n+M-1ならばng。
5,Btrueを考える。
Bから行と列の数はわかっているので,Btrueを0で初期化しておく。
Bの始まりの列は(B0,0-1)%7=m,始まりの行は(B0,0-1)/7=nとおく。
Btrueの成分はi*7+j+1で計算できる。
iはnからn+N-1まで,jはmからm+M-1までをBtrueに代入すればよい。
6,あとはBとBtrueが同じならばYes,違うならばNoを出力する。
実際のプログラム
#include<iostream>
#include<vector>
using namespace std;
int main(){
long long N,M;
cin >> N >> M;
vector<vector<long long>> B(N,vector<long long>(M));
for(long long i = 0; i < N; i++){
for(long long j = 0; j < M; j++){
cin >> B[i][j];
}
}
long long n = (B[0][0]-1)/7;
long long m = (B[0][0]-1)%7;
if(m+M-1 >= 7){
cout << "No" << endl;
return 0;
}
vector<vector<long long>> Btrue(N,vector<long long>(M));
for(long long i = n, ii=0; i <= n+N-1; i++, ii++){
for(long long j = m, jj=0; j <= m+M-1; j++, jj++){
Btrue[ii][jj] = i*7+j+1;
}
}
for(long long i = 0; i < N; i++){
for(long long j = 0; j < M; j++){
if(B[i][j] != Btrue[i][j]){
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
return 0;
}