10158 개미

겉으로 보기에는 쉬운 탐색문제이다 

하지만 입력범위가 무려 x, y <= 40,000 / t <= 200,000,000 이다 단순 반복으로는 풀수가 없으므로 시간을 줄이는 최적화가 필요하다

단순 이동(1칸식)으로 해결할 경우 시간복잡도가 O(t)이다. 그럼 최악의 경우 200,000,000 반복해야하므로 시간안에 풀수가 없다.

w, h = map(int, input().split())
p, q = map(int, input().split())
t = int(input())

dx, dy = 1, 1
for _ in range(t):
    p, q = p + dx, q + dy
    if p == 0:
        dx = 1
    elif p == w:
        dx = -1
    if q == 0:
        dy = 1
    elif q == h:
        dy = -1
print(p, q)

x, y 좌표를 따로따로 계산하는 규칙을 이용한 방법이다. O(t)에 비하면 훨씬 절약되지만 그래도 99%에서 시간초과가 걸린다..

w, h = map(int, input().split())
p, q = map(int, input().split())
t = int(input())

dx, dy = 1, 1
c_x, c_y = w - p, h - q
while t:
    c = min(c_x, c_y, t)
    p += c * dx
    q += c * dy
    t -= c

    if p == w:
        dx = -1
        c_x = p
    elif p == 0:
        dx = 1

    if q == h:
        dy = -1
        c_y = q
    elif q == 0:
        dy = 1

    if dx == 1:
        c_x = w - p
    elif dx == -1:
        c_x = p

    if dy == 1:
        c_y = h - q
    elif dy == -1:
        c_y = q

print(p, q)

문제를 다시 살펴보자 x, y 가 작고 t의 값이 크다면 똑같은 순환이 반드시 일어날것이다. 이를체크하여 한번만 순환하도록 만들어주면 된다.

w, h = map(int, input().split())
p, q = map(int, input().split())
t = int(input())

arr = []
setA = set()
dx, dy = 1, 1
c_x, c_y = w - p, h - q
circle = False
while t:
    c = min(c_x, c_y, t)
    p += c * dx
    q += c * dy
    t -= c
    if not circle:
        if (p, q, dx, dy, c) in setA:
            cnt = 0
            for i in range(arr.index((p, q, dx, dy, c)), len(arr)):
                cnt += arr[i][4]
            t %= cnt
            circle = True
        else:
            setA.add((p, q, dx, dy, c))
            arr.append((p, q, dx, dy, c))

    if p == w:
        dx = -1
        c_x = p
    elif p == 0:
        dx = 1

    if q == h:
        dy = -1
        c_y = q
    elif q == 0:
        dy = 1

    if dx == 1:
        c_x = w - p
    elif dx == -1:
        c_x = p

    if dy == 1:
        c_y = h - q
    elif dy == -1:
        c_y = q

print(p, q)

 순환을 체크하기 위해 list , set() 두개를 사용한 이유는 a in b 조건에서 set은 O(1)의 속도로 최적화를 할수 있기 때문에 사용하였고

 단 set 입력된 순서를 저장할수 없기에 list를 사용하였다. 지금 생각해보니 list를 굳이 안써도 최적화를 가능할거같긴한데 다음에 하는걸로..

추가 etc... ) 다른 답을 보니 x, y 좌표를 구하는 훨씬 간단학고 쉬운 방법이 있었다.. 이 방법을 이용하시길 바란다..

if ((p+t)//w)%2:p=w-(p+t)%w
else:p=(p+t)%w
if ((q+t)//h)%2:q=h-(q+t)%h
else:q=(q+t)%h