Takahashi's Information [AtCoder Beginner Contest 088 C]を数学的に解説

問題は以下を参照
https://atcoder.jp/contests/abc088/tasks/abc088_c

概要

3×3 のグリッドがあり、上から i 番目で左から j 番目のマスを (i,j) で表すとき、マス (i,j) には数 ci,jが書かれている。
Ci,jが標準入力として与えられる。
この時以下の命題が成立するかを判定せよ。
Ci,j=ai+bj(1<=i<=3,1<=j<=3)が成り立つ定められた整数a1,a2,a3,b1,b2,b3が存在する・・・①

①が真ならばYesを偽ならばNoを出力せよ。

C1,1	C1,2	C1,3
C2,1	C2,2	C2,3
C3,1	C3,2	C3,3

a1+b1	a1+b2	a1+b3
a2+b1	a2+b2	a2+b3
a3+b1	a3+b2	a3+b3

つまり、上記の表を等しくできるようにai,bjを設定できればYes,できなければNoを出力する。

解説

①が成り立つと仮定して矛盾する場合を考える。

①が成り立つと仮定する。
1列目から2列目を引くとどの行でもb1-b2となる。
その為、C1,1-C1,2=C2,1-C2,2=C3,1-C3,2・・・②
また同様に1列目から3列目を引いてもb1-b3になることから
C1,1-C1,3=C2,1-C2,3=C1,1-C3,3・・・③
が成り立つ。
これは列だけでなく行についても同じことが言えるため、同様に
C1,1-C2,1=C1,2-C2,2=C1,3-C2,3・・・④
C1,1-C3,1=C1,2-C3,2=C1,3-C3,3・・・⑤

以上の事から、①が成り立つならば②、③、④、⑤も成り立つ。

回答としては上の②、③、④、⑤をコードにすれば十分だが漏れがないかを確認する為に下で逆も示す。

次に②、③、④、⑤が成り立つならば、①も成り立つことを示す。

②、③、④、⑤が成り立つと仮定する。
以下のように整数s,t,u,wを置く。
s=C1,2-C1,1
t=C1,3-C1,1
u=C2,1-C1,1
w=C3,1-C1,1
すると、グリッドは

C1,1	C1,1+s	C1,1+t
C1,1+u	C1,1+s+u	C1,1+t+u
C1,1+w	C1,1+s+w	C1,1+t+w

となる。

ここで、
C1,1=a1+b1
a2=a1+u
a3=a1+w
b2=b1+s
b3=b1+t
と置くと。

a1+b1	a1+b2	a1+b3
a2+b1	a2+b2	a2+b3
a3+b1	a3+b2	a3+b3

となる。 よって、②、③、④、⑤→①が示された。

以上より、①⇔②、③、④、⑤が成り立つ。

コード

dlist_input=[]
 
for i in range (0,3):
  row = list(map(int,input().split()))
  dlist_input.append(row)
 
if (dlist_input[0][0]-dlist_input[0][1]==dlist_input[1][0]-dlist_input[1][1]==dlist_input[2][0]-dlist_input[2][1])\
and (dlist_input[0][0]-dlist_input[0][2]==dlist_input[1][0]-dlist_input[1][2]==dlist_input[2][0]-dlist_input[2][2])\
and (dlist_input[0][0]-dlist_input[1][0]==dlist_input[0][1]-dlist_input[1][1]==dlist_input[0][2]-dlist_input[1][2])\
and (dlist_input[0][0]-dlist_input[2][0]==dlist_input[0][1]-dlist_input[2][1]==dlist_input[0][2]-dlist_input[2][2]):
  print("Yes")
else:
  print("No")

記事作成の理由

アルゴリズム実技検定の公式テキスト内の解説で①→②、③、④、⑤が示されていたが、
仮にも大学で4年間数学を勉強していた者からすると逆も示す必要があると思い作成した。