問題はこちら。

ゲームの盤面が少ないので全探索できる。先手後手のスコアの和が一定ということに気が付かなかったのと再帰関数を使う発想が出てこなかったのでダメだった。そして解き方が分かったうえで実装が大変だった。

盤面をbitで表現すればもうちょっと効率が良くなると思うしdictも使わなくていいが、何位のbitが盤面のどこに対応してるのかとか考えるのが嫌だったのでやらなかった。

今年度中に1000問解きたかったけど忙しくて無理かも。

import sys
readline = sys.stdin.readline
INF = float('inf')


def init(b, c, score):
 for i in range(1 << 9):
   if bin(i).count('1') != 4:
     continue
   board = [[None] * 3 for _ in range(3)]
   for j in range(9):
     board[j // 3][j % 3] = i >> j & 1
   board = tuple(map(tuple, board))
   score[board] = 0
   for h in range(2):
     for w in range(3):
       if board[h][w] == board[h + 1][w]:
         score[board] += b[h][w]
       else:
         score[board] -= b[h][w]
   for h in range(3):
     for w in range(2):
       if board[h][w] == board[h][w + 1]:
         score[board] += c[h][w]
       else:
         score[board] -= c[h][w]


def solve(marker, mut_board, score):
 board = tuple(map(tuple, mut_board))
 if marker == 0:
   tmp = -INF
 else:
   tmp = INF
 for i in range(3):
   for j in range(3):
     if mut_board[i][j] == None:
       mut_board[i][j] = marker
       tmp_board = tuple(map(tuple, mut_board))
       if not tmp_board in score:
         solve(1 - marker, mut_board, score)
       if marker == 0:
         tmp = max(tmp, score[tmp_board])
       else:
         tmp = min(tmp, score[tmp_board])
       mut_board[i][j] = None
 score[board] = tmp


def main():
 b = [list(map(int, readline().split())) for _ in range(2)]
 c = [list(map(int, readline().split())) for _ in range(3)]
 
 score = {}
 init(b, c, score)
 
 board = [[None] * 3 for _ in range(3)]
 solve(0, board, score)
 total = sum(map(sum, b)) + sum(map(sum, c))
 diff = score[tuple(map(tuple, board))]
 print((total + diff) // 2, (total - diff) // 2, sep='\n')


if __name__ == "__main__":
 main()