Contest Duration: ~ (local time) (120 minutes) Back to Home

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 2015-06-27 23:19:36+0900 C - 双子と○×ゲーム sash Python (2.7.3) 100 1622 Byte AC 103 ms 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