2022/06/18 ABC256C

あたしって，ほんとバカ．

ABC256 C Filling 3x3 array

atcoder.jp

3X3の各マスを安直に全探索すると，最悪30⁹回for文を回すことになってTLEする．

a	b	c
d	e	f
g	h	i

今回の問題は，a,b,d,eが決まれば，c,f,g,h,iが自動的に決まる．
c = h1 - (a + b)
f = h2 - (d + e)
g = w1 - (a + d)
h = w2 - (b + e)
i = h3 - (b + e) = w3 - (c +f)
a,b,d,eを4重のfor文で全探索して，c,f,g,hを求め，h3 - (b + e) == w3 - (c +f)を確認すればよい．計算量はO(N⁴)に削減できる．

inputs = list(map(int, input().split()))
H = inputs[:3]
W = inputs[3:]

ans = 0
for a in range(1, 31):
    for b in range(1, 31):
        for d in range(1, 31):
            for e in range(1, 31):
                c = H[0] - (a+b)
                f = H[1] - (d+e)
                g = W[0] - (a+d)
                h = W[1] - (b+e)
                i_v = W[2] - (c+f)
                i_h = H[2] - (g+h)
                if i_v == i_h and min(a,b,c,d,e,f,g,h,i_v) > 0:
                    #print(a,b,c)
                    #print(d,e,f)
                    #print(g, h, i_v)
                    ans += 1
                    #print()
print(ans)

公式解説では，for文ではなく，深さ優先探索での実装例も紹介されていた．

感想

後ですぐに参照できるように，解けなかった問題を備忘録的に残していきたい． 初めてはてなブログで文章を書いたけど，テーブルとか数式が書きづらい．