yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

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;
}