Submission #4049304


Source Code Expand

from collections import deque


def calc(state, B, C):
    score = 0
    total = 0
    for i in range(2):
        for j in range(3):
            if state[i*3+j] == state[(i+1)*3+j]:
                score += B[i][j]
            total += B[i][j]
    for i in range(3):
        for j in range(2):
            if state[i*3+j] == state[i*3+(j+1)]:
                score += C[i][j]
            total += C[i][j]
    return score


def simulate(state, turn, memo, B, C):
    if state in memo:
        return memo[state]
    if 0 not in state:
        return calc(state, B, C)
    next_turn = 3-turn
    if turn == 1:
        score = 0
    else:
        score = float("inf")
    for i in range(9):
        if state[i] == 0:
            next_state = list(state)
            next_state[i] = turn
            next_state = tuple(next_state)
            next_score = simulate(next_state, next_turn, memo, B, C)
            if turn == 1:
                score = max(score, next_score)
            else:
                score = min(score, next_score)
    memo[state] = score
    return score


def main():
    B = [list(map(int, input().split())) for _ in range(2)]
    C = [list(map(int, input().split())) for _ in range(3)]
    memo = {}
    state = (0, 0, 0, 0, 0, 0, 0, 0, 0)
    score = simulate(state, 1, memo, B, C)
    total = sum(map(sum, B)) + sum(map(sum, C))
    print(score)
    print(total-score)


if __name__ == "__main__":
    main()

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User blcn
Language PyPy3 (2.4.0)
Score 100
Code Size 1491 Byte
Status AC
Exec Time 371 ms
Memory 54876 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 24
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
sample-01.txt AC 349 ms 54620 KB
sample-02.txt AC 365 ms 54364 KB
test-01.txt AC 354 ms 54620 KB
test-02.txt AC 345 ms 53724 KB
test-03.txt AC 343 ms 53980 KB
test-04.txt AC 351 ms 54876 KB
test-05.txt AC 371 ms 54364 KB
test-06.txt AC 348 ms 54620 KB
test-07.txt AC 336 ms 53980 KB
test-08.txt AC 341 ms 53724 KB
test-09.txt AC 339 ms 53852 KB
test-10.txt AC 350 ms 54364 KB
test-11.txt AC 342 ms 53084 KB
test-12.txt AC 353 ms 54492 KB
test-13.txt AC 342 ms 53852 KB
test-14.txt AC 350 ms 54364 KB
test-15.txt AC 345 ms 53980 KB
test-16.txt AC 340 ms 53724 KB
test-17.txt AC 355 ms 53724 KB
test-18.txt AC 348 ms 53980 KB
test-19.txt AC 353 ms 54236 KB
test-20.txt AC 347 ms 53980 KB