In [79]:
1
2
3
4
5
6
7
8
import sys
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time
from utils.generator import random2D
from sys import stdin
from math import sin, cos, radians
# import numpy as np
# plot = lambda a: print(np.array(a))
테트로미노
In [80]:
1
2
3
4
5
6
stdin = open('data/tetris.txt')
input = stdin.readline
n, m = list(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(n)]
assert n >= 4 and m <= 500
# plot(grid)
In [84]:
1
2
3
4
5
6
7
8
9
10
11
12
13
def rotate(block):
def rotateOne(x, y, angle):
return int(cos(radians(angle))) * x + int(sin(radians(angle))) * y, - int(sin(radians(angle))) * x + int(
cos(radians(angle))) * y
for k, e in enumerate(block):
block[k] = rotateOne(*e, 90)
def check(i, j, block, n, m):
for x, y in block:
if not (0 <= i + x < n and 0 <= j + y < m):
return False
return True
In [85]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@logging_time
def solution(grid, blocks):
blocks = [[(0, 0), (0, 1), (0, 2), (0, 3)],
[(0, 0), (0, 1), (1, 0), (1, 1)],
[(0, 0), (1, 0), (2, 0), (2, 1)],
[(0, 0), (1, 0), (2, 0), (2, -1)],
[(0, 0), (1, 0), (1, 1), (2, 1)],
[(0, 0), (0, 1), (0, 2), (1, 1)]]
n, m = len(grid), len(grid[0])
ans = 0
for i in range(n):
for j in range(m):
for block in blocks:
for _ in range(4):
rotate(block)
if not check(i, j, block, n, m): continue
ans = max(ans, sum(grid[i + x][j + y] for x, y in block))
return ans
In [86]:
1
solution(grid, blocks, verbose=True)
1
2
WorkingTime[solution]: 10.92458 ms
1
19
Hard Coding
rotate하는 것이 overhead가 큰 관계로 hard coding하였다.
hard coding하는 과정에서 block에 대한 indices를 만드는 과정을 이 블로그 에서 따라하였다. 그림을 블로그에서 인용하였다.
그림
19가지 경우의 수가 있다.
In [87]:
1
2
n, m = 100, 200
grid = random2D(shape=(n, m), randrange=(1, 1000))
In [88]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
@logging_time
def hardcode(grid):
blocks = [[(0,1), (1,0), (1,1)],
[(0,1), (0,2), (0,3)],
[(1,0), (2,0), (3,0)],
[(0,1), (0,2), (1,0)],
[(0,1), (0,2), (-1,2)],
[(1,0), (1,1), (1,2)],
[(0,1), (0,2), (1,2)],
[(1,0), (2,0), (2,1)],
[(0,1), (1,1), (2,1)],
[(0,1), (1,0), (2,0)],
[(1,0), (2,0), (2,-1)],
[(1,0), (1,1), (2,1)],
[(0,1), (1,0), (-1,1)],
[(0,1), (1,0), (1,-1)],
[(0,1), (1,1), (1,2)],
[(0,1), (0,2), (1,1)],
[(1,0), (1,1), (1,-1)],
[(1,0), (2,0), (1,-1)],
[(1,0), (1,1), (2,0)]]
ans = 0
for i in range(n):
for j in range(m):
for block in blocks:
if not check(i, j, block, n, m): continue
ans = max(ans, grid[i][j] + sum(grid[i + x][j + y] for x, y in block))
return ans
print(hardcode(grid, verbose=True))
print(solution(grid, blocks, verbose=True))
1
2
3
4
5
WorkingTime[hardcode]: 463.20629 ms
3887
WorkingTime[solution]: 3929.22378 ms
3887
Summbited Code
solution을 함수 형식으로 만들면 overhead 때문에 LTE가 뜬다.
따라서, 다음과 같이 제출.
In [92]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from sys import stdin
stdin = open('data/tetris.txt') # 제출 시 주석처리
input = stdin.readline
n, m = list(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(n)]
# assert n >= 4 and m <= 500
# plot(grid)
blocks = [[(0,1), (1,0), (1,1)],
[(0,1), (0,2), (0,3)],
[(1,0), (2,0), (3,0)],
[(0,1), (0,2), (1,0)],
[(0,1), (0,2), (-1,2)],
[(1,0), (1,1), (1,2)],
[(0,1), (0,2), (1,2)],
[(1,0), (2,0), (2,1)],
[(0,1), (1,1), (2,1)],
[(0,1), (1,0), (2,0)],
[(1,0), (2,0), (2,-1)],
[(1,0), (1,1), (2,1)],
[(0,1), (1,0), (-1,1)],
[(0,1), (1,0), (1,-1)],
[(0,1), (1,1), (1,2)],
[(0,1), (0,2), (1,1)],
[(1,0), (1,1), (1,-1)],
[(1,0), (2,0), (1,-1)],
[(1,0), (1,1), (2,0)]]
def check(i, j, block, n, m):
for x, y in block:
if not (0 <= i + x < n and 0 <= j + y < m):
return False
return True
ans = 0
for i in range(n):
for j in range(m):
for block in blocks:
if not check(i, j, block, n, m): continue
ans = max(ans, grid[i][j] + sum(grid[i + x][j + y] for x, y in block))
print(ans)
1
2
19
Leave a comment