This page looks best with JavaScript enabled

ABC088C - Takahashi's Information

 ·   ·  ☕ 3 min read  ·  ✍️ reud · 👀... views

う〜ん、難しい。 考え方ミスって沼にハマったので復習。

C - Takahashi’s Information

考えた事

$c_{i,j}=a_{i}+b_{j}$であることを考える。

以下の9つについて式が成り立つ。

$c_{1,1}=a_{1}+b_{1}$

$c_{1,2}=a_{1}+b_{2}$

$c_{1,3}=a_{1}+b_{3}$

$c_{2,1}=a_{2}+b_{1}$

$c_{2,2}=a_{2}+b_{2}$

$c_{2,3}=a_{2}+b_{3}$

$c_{3,1}=a_{3}+b_{1}$

$c_{3,2}=a_{3}+b_{2}$

$c_{3,3}=a_{3}+b_{3}$

この9つの式を全て足し合わせると以下が成立する。

$<全てマスの和>=3(a_{1}+a_{2}+a_{3}+b_{1}+b_{2}+b_{3})$

このことから、前マスの和が3の倍数ならYesそうでないならNoを出力すれば良い。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    int sum = 0;
    REP(i,9) {
        int a;
        cin >> a;
        sum+=a;
    }
    cout << ((sum%3 == 0) ? "Yes" : "No") << endl;


    return 0;
}

結果

提出 #10247170 - AtCoder Beginner Contest 088

どうして。 反例が思いつく方は@reudasasにご連絡下さい・・・・

正しい解法

$(a_1,a_2,a_3,b_1,b_2,b_3) = (p_1,p_2,p_3,q_1,q_2,q_3)$が成り立つ場合(Yesになる場合)、

任意の整数xに対して、

$a_i+b_j=(p_i+x)+(q_j-x)$が成り立つので、

$(a_1,a_2,a_3,b_1,b_2,b_3) = (p_1+x,p_2+x,p_3+x,q_1-x,q_2-x,q_3-x)$

となる。

このことからxを適切な値にすることで$a_1$を0にすることが出来る。

あとは$b_1,b_2,b_3$を求めてそこから$a_2,a_3$を求めて、求め終わったら、$c_{i,j} = a_i + a_j$が成立しているか確認すれば良い。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    vector<int> a(3,0);
    vector<int> b(3,0);

    vector<vector<int>> c(3,vector<int>(3));
    REP(i,3) {
        REP(j,3) {
            cin >> c[i][j];
        }
    }

    // a_1 = 0からb_1,b_2,b_3を出す。
    b[0] = c[0][0];
    b[1] = c[0][1];
    b[2] = c[0][2];
    // a_2,a_3を出す
    a[1] = c[1][0]-b[0];
    a[2] = c[2][0]-b[0];

    REP(i,3) {
        REP(j,3) {
            if (c[i][j] != (a[i]+b[j])) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;


    return 0;
}

提出 #10255411 - AtCoder Beginner Contest 088

解法の納得はできるけど自分の解法のミスがワカンねぇ・・・

追記

同級生のtunehiraさん (@2nehira) / Twitterから助け舟が

せっかくですので、成り立たないことを確認してみます。

$2 = a_{1}+b_{1} \tag{1}$

$2 = a_{2}+b_{2} \tag{2}$

$2 = a_{3}+b_{3} \tag{3}$

$a_1 = 0$ としてみる。

(1)から、$ b_1 = 2 $ になるので、 $ a_2 = -2 $, $ a_3 = 0$。

求めた$a_2$,$a_3$を(2)(3)に入れて、

$b_2 = 4$,$b_3=2$.

全部求まったので検証してみましょう。

ここで、$c_{1,3} = a_{1}+b_{3}$ですが、$c_{1,3} = 0$,$a_{1} = 0,b_{3}=2$なので満たすことが出来ません。

よって答えはNoです。

これにより反例となります。

tunehiraさんありがとうございました。

Share on

reud
WRITTEN BY
reud
Stundent