Zenn
📖

ABC225 C - Calendar Validator C++解答例

2021/10/31に公開
C++
競技プログラミング
AtCoder
競プロ
tech

AtCoder Beginner Contest 225 C - Calendar ValidatorをC++で解きます。

問題

問題文をAtCoderのページより引用します。

問題文

10^{100}行7列の行列Aがあり、任意の整数対(i, j) (1 \leq i \leq 10^{100}, 1 \leq j \leq 7)についてその(i, j)成分は(i - 1) \times 7 + jです。
N行M列の行列Bが与えられるので、BがAの一部の矩形領域を(向きを変えずに)切り出したものであるかを判定してください。

制約

  • 1 \leq N \leq 10^4
  • 1 \leq M \leq 7
  • 1 \leq B_{i, j} \leq 10^9
  • 入力はすべて整数

解答例

各要素の法則チェックだけでは不十分

行列Aの定義より、行列Aの各要素について、隣り合う要素には次のような関係が常に成り立っていることが分かります。

  • A_{i, j} = A_{i - 1, j} + 7：一つ下のマスに行くと数値が7増える
  • A_{i, j} = A_{i, j - 1} + 1：一つ右のマスに行くと数値が1増える

従って、与えられた行列Bの各要素について、これらの法則が全て成り立っていればOK…と言いたいところですが、これだけでは不十分です。

凡例として、以下のような行列Bが考えられます。

B = \begin{pmatrix} 7 & 8 & 9 \\ 14 & 15 & 16 \end{pmatrix}

この行列Bは上に挙げた法則を全て満たしていますが、行列Aから切り出すことは決してできません。これは行列Aの形を見ると明らかです。

A = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ \ldots \end{pmatrix}

行列Aから正しく切り出したものかどうかをチェックする

行列Bが数値の法則を満たしていたとして、それが行列Aから正しく切り出せるものなのかどうかをチェックする必要があります。
チェックする方法としては、7のmodを取る方法が考えられます。

行列Aに存在する数値のうち、7で割った余りが0となる値(つまり7の倍数)が出現するのは、一番右の列のみとなります。逆に、それ以外の列には7の倍数は決して出現しません。

言い換えると、行列Aには、7の倍数の値を持つ要素より右側には要素は存在しないということになります。
そのため、もし行列Bの中に7の倍数が出現したとき、それがBの一番右の列に位置しないのであれば、それは行列Aから切り出したものではないと結論付けられます。

実装する際は、行列Bのうち一番右の列を除くすべての要素の値について7で割った余りを取り、余りが0になるような要素が1つでも存在したらNoと答えれば良いでしょう。

実装例

実装例を以下に示します。C++ではstd::vector同士の比較演算が可能なので、行列Bが法則を満たしているかどうかのチェックを等価演算子で行っています。
行列Bの一番左上の要素を基準とした、数値の法則を満たす行列Cを作っておき、BとCが等価であるかどうかをチェックすることで、Bが法則を満たしているかどうかをチェックしています。

c.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
int main() {
  int64_t N, M;
  std::cin >> N >> M;
  std::vector<std::vector<int64_t>> B(N, std::vector<int64_t>(M, -1));
  for (int64_t i = 0; i < N; i++) {
    for (int64_t j = 0; j < M; j++) {
      std::cin >> B.at(i).at(j);
    }
  }

  // 比較評価用の行列C
  std::vector<std::vector<int64_t>> C(N, std::vector<int64_t>(M, -1));
  C.at(0).at(0) = B.at(0).at(0);
  for (int64_t i = 0; i < N; i++) {
    for (int64_t j = 0; j < M; j++) {
      C.at(i).at(j) = C.at(0).at(0) + 7 * i + j;
    }
  }
 
  // Aから切りだしたものかどうかを7の余りを取ることでチェックする
  bool ok = true;
  for (int64_t i = 0; i < N; i++) {
    for (int64_t j = 0; j < M - 1; j++) {
      if (B.at(i).at(j) % 7 == 0) {
        ok = false;
      }
    }
  }
 
  // 両者を満たしているときのみYesと答える
  if (ok && B == C) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
 
  return 0;
}

実際に提出したコードはこちら。

Discussion