う〜ん、難しい。 考え方ミスって沼にハマったので復習。
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
|
#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さんありがとうございました。