Submission #667937
Source Code Expand
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools
import numpy
import random
import sys
DS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
H = 30
W = 30
TRIAL = 15
INF = 100000
class Solver(object):
def __init__(self, stage, deltas=DS):
self.stage = None
self.original_stage = stage.copy()
self.hands = None
self.naive_counter = 0
self.deltas = deltas[:]
self.indices = numpy.array(list(itertools.product(range(H), range(W))))
self.initialize()
def initialize(self):
self.stage = self.original_stage.copy()
self.hands = []
self.naive_counter = 0
def decrement(self, r, c):
self.hands.append((r + 1, c + 1))
self.stage[r, c] -= 1
def shuffle_indices(self):
random.shuffle(self.indices)
def naive_solution(self):
for r, c in itertools.product(range(H), range(W)):
cell = self.stage[r, c]
if cell <= 0:
continue
for _ in range(cell):
self.naive_counter += 1
self.decrement(r, c)
def search_adj(self, r0, c0):
for dr, dc in self.deltas:
(r, c) = (r0 + dr, c0 + dc)
if r < 0 or r >= H or c < 0 or c >= W:
continue
elif 0 < self.stage[r, c] == self.stage[r0, c0]:
self.decrement(r, c)
self.search_adj(r, c)
break
def use_multiple_adj_solution(self):
self.initialize()
self.shuffle_indices()
for r0, c0 in self.indices:
if self.stage[r0, c0] <= 0:
continue
self.decrement(r0, c0)
self.search_adj(r0, c0)
self.naive_solution()
def main():
sys.setrecursionlimit(10000)
stage = numpy.array([list(map(int, input().split())) for _ in range(H)])
solver = Solver(stage)
min_naive_counter = 100000
optimal_hands = None
for _ in range(TRIAL):
solver.use_multiple_adj_solution()
new_naive_counter = solver.naive_counter
if new_naive_counter < min_naive_counter:
min_naive_counter = new_naive_counter
optimal_hands = solver.hands
for r, c in optimal_hands:
print("{} {}".format(r, c))
if __name__ == '__main__':
main()
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
hamukichi |
Language |
Python (3.4.3) |
Score |
542005 |
Code Size |
2409 Byte |
Status |
AC |
Exec Time |
4614 ms |
Memory |
30952 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
55587 / 100000 |
53243 / 100000 |
54842 / 100000 |
51985 / 100000 |
54892 / 100000 |
54653 / 100000 |
53927 / 100000 |
55432 / 100000 |
53843 / 100000 |
53601 / 100000 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
4614 ms |
30952 KB |
subtask_01_02.txt |
AC |
2969 ms |
20076 KB |
subtask_01_03.txt |
AC |
2854 ms |
19936 KB |
subtask_01_04.txt |
AC |
3285 ms |
20600 KB |
subtask_01_05.txt |
AC |
3015 ms |
20228 KB |
subtask_01_06.txt |
AC |
2747 ms |
20216 KB |
subtask_01_07.txt |
AC |
3097 ms |
20216 KB |
subtask_01_08.txt |
AC |
3035 ms |
20088 KB |
subtask_01_09.txt |
AC |
2921 ms |
20108 KB |
subtask_01_10.txt |
AC |
3228 ms |
20236 KB |