AtCoderログ：0077 - ABC 088 C

問題

問題文

$3 \times 3$ のグリッドがあります. 上から $i$ 番目で左から $j$ 番目のマスを $(i,j)$ で表すとき, マス $(i,j)$ には数 $c_{i,j}$ が書かれています.高橋君によると, 整数 $a_1, a_2, a_3, b_1, b_2, b_3$ の値が決まっており, マス $(i,j)$ には数 $a_i+b_j$ が書かれているらしいです.

高橋君の情報が正しいか判定しなさい.

制約

・$c_{i,j}~(1 \le i \le 3, 1 \le j \le 3)$ は $0$ 以上 $100$ 以下の整数

収録されている問題セット

• AtCoder に登録したら次にやること (第08問類題)

回答

回答1 (AC)

できることがたくさんあって、逆に何をしたらよいかがわかりにくい問題です。この問題のポイントは、変数 $a_1,a_2,a_3,b_1,b_2,b_3$ の値を求めることが出来ない点に尽きます。6個の変数の和 $a_i+b_j$ は9種類あるので、個々の変数の値が求められそうなものですが、以下の考察により無理であることがわかります：3個の変数$a_1,a_2,a_3$ の値は無関係なので、一列目に並んでいる3種類の変数の和 $a_1+b_1$, $a_2+b_1$, $a_3+b_1$ の値も無関係である。また、3個の変数$b_1,b_2,b_3$ の値は無関係なので、一行目に並んでいる3種類の変数の和 $a_1+b_1$, $a_1+b_2$, $a_1+b_3$ の値も無関係である。よって5種類の変数の和 $a_1+b_1$, $a_2+b_1$, $a_3+b_1$, $a_1+b_2$, $a_1+b_3$ の値は無関係である。逆に、これ以外の4種類の変数の和 $a_2+b_2$, $a_3+b_2$, $a_2+b_3,a_3+b_3$ は他の変数の和と関係を持っている、つまり他の変数の和から計算することが出来る。例えば $a_2+b_2=(a_1+b_2)+(a_2+b_1)-(a_1+b_1)$ と変形できるので、変数の和 $a_2+b_2$ は3種類の変数の和 $a_1+b_2$, $a_2+b_1$, $a_1+b_1$ から計算できます。

コードを作成する上では、1行目と1列目の5種類の値が正しいと仮定して、残りの4種類の値がつじつまにあっているかを確認すれば良いでしょう。例えば列ごとに見ると、、各列の1行目と2行目の差は常に $S=a_2-a_1$、2行目と3行目の差は常に $T=a_3-a_2$ になるはずです。そこで具体的な変数の値 $c_{i,j}$ に対し、1列目から $S,T$ を求め、2列目と3列目において差が $S,T$ になっているかをチェックすれば良いでしょう。コードは以下のようになりました。

abc088c-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<vector<int>> c(3, vector<int>(3));
  for ( int i=0; i<3; i++ ) {
    for ( int j=0; j<3; j++ ) {
      cin >> c.at(i).at(j);
    }
  }

  int s = c.at(1).at(0)-c.at(0).at(0);
  int t = c.at(2).at(0)-c.at(1).at(0);
  string answer = "Yes";
  if ( c.at(1).at(1)-c.at(0).at(1)!=s ) {
    answer = "No";
  } else if ( c.at(2).at(1)-c.at(1).at(1)!=t ) {
    answer = "No";
  } else if ( c.at(1).at(2)-c.at(0).at(2)!=s ) {
    answer = "No";
  } else if ( c.at(2).at(2)-c.at(1).at(2)!=t ) {
    answer = "No";
  }

  cout << answer << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

$a_1,a_2,a_3$ をループで変化させ、関係式から $b_1,b_2,b_3$ を求め、残りの関係式のつじつまがあっているかをチェックする解法です。

AtCoder の解説 → コンテスト全体の解説

$a_1=0$ とおくことで他の変数の値を確定させ、残りの関係式のつじつまがあっているかをチェックする解法です。

リンク

前後の記事

• 前の記事 → AtCoderログ：0076 - ABC 214 に参加しました
• 次の記事 → AtCoderログ：0078 - ABC 214 A