GCJ 2010 Round 1A.

알고스팟/알고리즘 2015.04.26 18:56


1번 Rotate


비교적 간단한 기하(?), 구현 문제이다. 

  - Start -

     .......
     .......
     .......
     ...R...
     ...RB..
     ..BRB..
     .RBBR..
   - Rotate -

     .......
     R......
     BB.....
     BRRR...
     RBB....
     .......
     .......
   - Gravity -

     .......
     .......
     .......
     R......
     BB.....
     BRR....
     RBBR...

위와 같은같은 블록 상황이 주어 졌을 때, 블록판을 잡고 시계 방향으로 90도 돌린 뒤 중력이 공중에 떠있는 블록들을 아래로 잡아 당긴다고 생각한다. 이 후 변환된 블록판에서, 연속된 R혹은 B블록이 K개 있나 없나를 확인하는 문제이다. 


문제의 해결의 키는 두가지 이다.

1) 90도로 회전 후, 중력이 잡아 당기는 과정은 사실, 원래 주어진 블록을 오른쪽 끝으로 미는 과정과 동일하다. 동일하다는 말은 R, B블록의 connectiity가 보존 된다는 말이다. 


2) 연속된 K블록 구간을 찾기 위해선, 점이아닌 모든 블록에 대해 상하좌우, 4개의 대각선 8방향을 모두 체크해주면 된다. 이 때, 간단한 구현 팁은 대칭성을 이용해 4방향에 대해서만 체크해주면 된다는 것이다. 예를들어, 상, 왼쪽 대각 위, 왼쪽, 왼쪽 대각 아래, 이렇게 4방향에 대해서만 체크해도 나머지 부분들은 대칭성에 의해 검사 된다. O(n^2).


def solve(board, K):
    #N = num rows
    #M = num cols
    N, M = len(board), len(board[0])
    
    #push everything to the right.
    #this effectively takes care of the rotation.   
    for i in xrange(0, N):
        count = 0
        for j in xrange(M-1, -1, -1):
            if board[i][j] != '.':
                board[i][M-1-count] = board[i][j]
                if M-1-count != j:
                    board[i][j] = '.'
                count += 1
                
    isRed = False
    isBlue = False
    for i in xrange(0, N):
        for j in xrange(M-1, -1, -1):
            
            if board[i][j] != '.' and check(i,j,board,K):
                if board[i][j] == 'R':
                    isRed = True
                else:
                    isBlue = True
    if isRed and isBlue:
        return 'Both'
    if isRed and not isBlue:
        return 'Red'
    if not isRed and isBlue:
        return 'Blue'
    return 'Neither'    
    
    
#checks if starting at (x,y), you can find 4 'R's or 'B's in a row
def check(x,y, board, K):
    N, M = len(board), len(board[0])
    #check up
    color = board[x][y]
    #print "color is %s" % color
    isFound = False
    for i in xrange(K):
        if y-i < 0 or board[x][y-i] != color:
            break
        if i == K-1:
            isFound = True
            return isFound
    #diagnal up to the left
    for i in xrange(K):
        if y-i < 0 or x-i < 0 or board[x-i][y-i] != color:
            break
        if i == K-1:
            isFound = True
            return isFound
    #straight to the left
    for i in xrange(K):
        if x-i < 0 or board[x-i][y] != color:
            break
        if i == K-1:
            isFound = True
            return isFound
    #diagnal down to the left
    for i in xrange(K):
        if y-i < 0 or x+i > N-1 or board[x+i][y-i] != color:
            break
        if i == K-1:
            isFound = True
            return isFound
    
    return False
    

f = open("A-large-practice.in", 'r')
f2 = open("outputRotateLarge.txt", 'w') 
t = int(f.readline())
for i in xrange(t):
    s = "Case #" + str(i+1) + ": "
    
    l = map(int, f.readline().split())
    size = l[0]
    K = l[1]
    board = []
    for i in range(size):
        board.append(list(f.readline().rstrip()))
    
#   for i in board:
#       print i
#   print '--------'
    if i == t-1:
        f2.write(s+solve(board,K))
    else:
        f2.write(s+solve(board, K)+'n')

f.close()
f2.close()
    


2번. Make it smooth


연속된 픽셀 구간 pixel[] 이 주어 질 때, 각각의 adjacent pixel pair pixel[i], pixel[i+1] 에 대해 이 둘의 차이가 주어진 상수 M미만인 픽셀 구간을 smooth 하다고 정의한다.

이제 다음 3가지 변환 옵션이 있다.

1) pixel[i]를 지워 버린다. 지우는데 드는 비용은 고정 된 상수 D이다.

2) pixel[i]의 값 m을 m'으로 수정한다. 이때 드는 비용은 abs(m' - m)이다.

3) 아무 위치에나 어떤 임이의 값을 가진 픽셀을 삽입할 수 있다. 삽입 비용은 고정된 상수 I이다. 


이렇게 위 3가지 operations이 있을 때, 주어진 픽셀 구간 pixel[]을 스무드하게 하기 위한 최소 비용을 구하는 문제이다.


물론, Dynamic programming이다. 

다음과 같이 dp를 정의한다

dp[n][p] = 첫 1, ..., n번째 pixel을 이미 스무드하게 만들 었고 마지막 pixel의 값이 p일 때드는 최소 비용.


이제 그럼 dp[n][p]가 주어 졌을 때, n+1번째 픽셀을 어떻게 처리해야 될까? 간단하다. 

1) n+1을 지워버린다. 추가 비용 D

2) n+1을 어떤 임의의 값 p'으로 수정한다. 그럼 abs(p' - pixel[n+1])의 비용이 든다. 여기서 p'과 p의 차이가 M 이하라면 끝. M 이상 이라면, n과 n+1 사이에 최소한의 픽셀을 추가해서 스무드하게 만들어야 한다. 이 때, 추가해야 될 최소한의 픽셀 수는 (|q' - p| - 1)/ M 이다.


이걸 dp로 옮기면 아래와 같다. 

def solve(D, I, m, data):
    n = len(data)
    tab = [0] * 256
    otab = [0] * 256
    for i in xrange(n):
        otab, tab = tab, otab
        for j in xrange(256):
            cur = otab[j] + D
            base = abs(data[i] - j)
            if cur > base:
                for k in xrange(256):
                    if m == 0 and k != j:
                        continue
                    new = otab[k]
                    if k < j:
                        new += (j-k - 1) // m * I
                    elif k > j:
                        new += (k-j - 1) // m * I
                    if cur > base+new:
                        cur = base+new
            tab[j] = cur
    return min(tab[i] for i in xrange(256))


3. Number Game

두명이서 게임을 한다. 어떤 숫자 A, B가 주어졌을 때 player1이 먼저 시작한 뒤 순서를 번갈아 가며 다음 두가지 중 하나의 operation을 할 수 있다. 

1) A를 A = A - kB (k  >0)로 줄인다.

2) B를 B = B - kA (k >0)로 줄인다.




이 때, 두명의 플레이어 중 먼저 한 숫자를 0이하로 줄이는 사람이 지는 게임이다.

또한 (A, B)가 주어졌을 때, player1가 먼저 시작하여, player2가 어떻게 플레이 하든, player1이 항상 승리를 보장 받을 수 있는 (A, B)를 winning position 이라고 한다.


이런류의 게임을 게임이론에서 NIM이라고 하는데 이거에 관한 연구가 또 한무더기 있다. 누가 어떻게 플레이 해야 optimal strategy 일까등을 다루는 연구말이다.


이 문제에서는, 위와 같은 숫자게임을 정의 한 뒤, 구간 a1, a2, b1, b2가 주어 졌을 때 winning position의 수를 세는 문제이다.


Dynamic programming으로도 사실 상 풀 수 있는 문제이다. (A, B)가 winning position인지 아닌지를 푸는데, 편의상 A > B라면 (A - kB, B)만 있으면 풀 수 있기 때문이다. 하지만, 좀 더 게임이론 측면에서 접근하면 쉬운 방법이 있다.


일단 몇가지 observation을 살펴보자.



1번은 자명하다.

2번은 왜 그런지 살펴보면 쉽다. 먼저 



이러한 k를 찾았다고 하자. 먼저 A - kB가 losing position 이라면 (A - kB, B)를 만든 뒤 player2에게 넘겨주면 게임이 끝나버리니 승리한다. 만약 A - kB가 winning position이라면 (A - (k-1)B, B)를 만든 뒤 턴을 넘겨주면 player2는 A - (k-1)B에서 B를 한번 더 빼는 방법 말고는 수가 없기 때문에 그 다음턴에 우리가 이길 수 있다. 이렇듯 어떻게 하든 A, B는 위닝 포지션인 것이다.


이걸 좀 더 확장해보면 아주 우아한 알고리즘에 다다를 수 있다. 


1) 먼저 A, B가 주어졌을 때, 

A >= 2B인지를 체크한다. 이 조건이 만족 된다면 바로 winning position임을 리턴한다. A < 2B라면, 우리가 할 수 있는 옵션은 (A-B, B)으로 만든 뒤 턴을 넘기는 것이다. 


2) 재귀적으로 B >= 2(A-B) 조건을 체크한다. 이게 만족 된다면 (A-B, B)는 losing position이다. losing position임을 알리고 리턴한다. 그렇지 않다면 (A-B, B - (A-B)) = (A-B, 2B -A)를 만들고 턴을 넘긴다.


3) 다시 반복해서 승리조건을 체크한다.

4) (A, A)가 나올때 까지...무수히 반복.


자세히 살펴보면, 두 수의 GCD를 구하는 Euclidean 알고리즘과 매우 유사하다. 어떤 두 수의 GCD는 (a-b ,b)의 GCD와 같다는 알고리즘이다. 유클리디안 알고리즘은 recursion depth가 O(logN)이다. 마찬가지로 이 문제도 O(logN)안에 종료 됨을 알 수 있다.


근데 승리 조건을 자세히 살펴보면 처음엔 2/1, 3/2, 5/3, 8/5... 등과 같이 피보나치 수열의 연속된 항들과 같음을 알 수 있다! 근데 피보나치 수열의 연속된 항들의 비율은 우아한 황금비율에 수렴한다는 사실 또한 위키피디아가 알려주었다! 


!! 이제 이걸 조금만 더 확장해보면, 

Theorem: (A, B) is a winning position if and only if A ≥ φ B.

이라는 결론에 다다른다.

우아하지 않는가?.. 

사실 조금 지렸다. 이맛에 PS하나 싶다. 혹은 수학. 

이제 실제 문제에 대한 답을 구하려면 B를 고정해 놓고, 위 조건을 만족 시키는 A의 수를 바로 더해주면 된다. 우아하다. 또한 python은 arbitrary length floating point 연산을 지원함으로..바로 위 조건을가지고 승리 조건에 이용해도 큰 수의 (A, B)에 대해 precision을 잃지 않고 올바르게 계산 할 수 있다.



import math

#so elegant.
def solveSingle(A, B):
    if B == 0: return True
    if A >= 2*B: return True
    return not solveSingle(B, A-B)
    

def solveBatch(a1, a2, b1, b2):
    ans = 0
    goldenRatio = (1+ math.sqrt(5))/(2.0)
    
    for i in xrange(b1, b2+1):
        threshHold = goldenRatio * i
        threshHold = int(math.ceil(threshHold))
        if threshHold > a2:
            continue
        if threshHold < a1:
            ans += (a2 - a1 + 1)
            continue
        else:
            num = a2 - threshHold + 1
            ans += num
    return ans

    

f = open("C-large-practice.in", 'r')
f2 = open("outputNimLarge.txt", 'w')    
t = int(f.readline())
for i in xrange(t):
    s = "Case #" + str(i+1) + ": "
    
    l = map(int, f.readline().split())
    a1, a2, b1, b2 = l[0], l[1], l[2], l[3]
    ans = solveBatch(a1,a2,b1,b2) + solveBatch(b1,b2,a1,a2)
    
    if i == t-1:
        f2.write(s+str(ans))
    else:
        f2.write(s+str(ans)+'\n')

f.close()
f2.close()


설정

트랙백

댓글