Submission #434421


Source Code Expand

Copy
b = []
c = []
b.extend(map(int, raw_input().split()))
b.extend(map(int, raw_input().split()))
c.extend(map(int, raw_input().split()))
c.extend(map(int, raw_input().split()))
c.extend(map(int, raw_input().split()))

point_sum = sum(b) + sum(c)
pow3 = [pow(3, pos) for pos in xrange(9)]
cho_list = [-1 for _ in xrange(pow(3, 9)+1)]
ys = [0, 1, 3, 4, 6, 7]

def calc_id(map_id, pos, turn):
    return map_id + pow3[pos] * turn

def point(map_id):
    maps = [0 for _ in xrange(9)]
    tmp_map_id = map_id
    for i in xrange(9):
        maps[i] = tmp_map_id % 3
        tmp_map_id /= 3
    cho = 0
    for x in xrange(6):
        if maps[x+3] == maps[x]:
            cho += b[x]
        y = ys[x]
        if maps[y+1] == maps[y]:
            cho += c[x]
    return cho

def put(map_id, pos):
    return (map_id / pow3[pos]) % 3 != 0

# turn=1: chokudai, 2: naoko
def search(map_id, turn, num_put):
    if cho_list[map_id] > -1:
        return cho_list[map_id]
    if num_put == 9:
        cho_list[map_id] = point(map_id)
        return cho_list[map_id]
    cho_score = 0 if turn == 1 else 10000
    for pos in xrange(9):
        if put(map_id, pos):
            continue
        next_map_id = calc_id(map_id, pos, turn)
        cho = search(next_map_id, 3 - turn, num_put+1)
        if turn == 1:
            if cho_score < cho:
                cho_score = cho
        elif turn == 2:
            if cho_score > cho:
                cho_score = cho
    cho_list[map_id] = cho_score
    return cho_list[map_id]

cho = search(0, 1, 0)
print cho
print point_sum - cho

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User sash
Language Python (2.7.3)
Score 100
Code Size 1622 Byte
Status
Exec Time 103 ms
Memory 3636 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 100 / 100 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 99 ms 3632 KB
sample-02.txt 98 ms 3628 KB
test-01.txt 97 ms 3636 KB
test-02.txt 99 ms 3628 KB
test-03.txt 98 ms 3628 KB
test-04.txt 103 ms 3564 KB
test-05.txt 97 ms 3628 KB
test-06.txt 99 ms 3628 KB
test-07.txt 97 ms 3628 KB
test-08.txt 99 ms 3624 KB
test-09.txt 97 ms 3632 KB
test-10.txt 99 ms 3616 KB
test-11.txt 98 ms 3628 KB
test-12.txt 97 ms 3628 KB
test-13.txt 97 ms 3556 KB
test-14.txt 99 ms 3628 KB
test-15.txt 97 ms 3624 KB
test-16.txt 98 ms 3628 KB
test-17.txt 97 ms 3624 KB
test-18.txt 97 ms 3620 KB
test-19.txt 99 ms 3628 KB
test-20.txt 100 ms 3628 KB