Google의 그 것!

개요

군대 안에서 점점 머리가 굳어가는 걸 깨닫고...

머리라도 굴리자는 의미에서 혼자서 코드 재밍재밍, 달리자!

이 글을 쓰는 곳은 영내 자대이므로, 추후 시간을 들여서~~~휴가를 나와서~~~ 정리하겠습니다.

문제 풀이 자취

2009년 Round1C

문제 : https://code.google.com/codejam/contest/189252/dashboard

정황 및 느낀 점

2시간 30분에 A B 다 풀고 C-Small 풀었다. 65/100

BackTracking 참으로 오랜만에 써 봤다. 근데 O(N^N)...
C번 코드를 2개 짰다...(DC, DP) 2번째 꺼 짜고 돌렸는데 Incorrect! 보고 절망..
O(N^N) 코드는 다음부터 짜면 안되겠다. (100^100)

 C-Large 를 넣었는데, 해방자 100명! 터짐..

파이썬으로 알고리즘 처음 짜는데, 확실히 C보다 편하다.

 그럼에도 불구하고 C++을 많이 쓰는 건.. 상대적으로 2% 부족한 속도 때문인가??

소스코드

Problem A. All Your Base

for loop in xrange(int(raw_input())):
    mes = raw_input()
    dic = {}

    maxi = 0
    count=1
    for S in mes:
        if count==1:
            if dic.get(S)==None:
                dic[S]=count
                count += 1
        elif count==2:
            if dic.get(S)==None:
                dic[S]=0
                break
    for S in mes:
        if dic.get(S)==None:
            dic[S]=count
            count += 1

    result=0
    for S in mes:
        result=dic.get(S)+result*count

    print('Case #{0}: {1}'.format(loop+1,result))

Switch가 없어서 if가 많이 들어갔는데, 지금 생각해 보니, dictionary로 엄청 줄일 수 있을 것 같다.

Problem B. Center of Mass

import math

for loop in xrange(int(raw_input())):
    flycount = int(raw_input())
    flyinfo =[]
    
    for loop2 in xrange(flycount):
        flyinfo.append(raw_input().split())

    c=[0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    
    for fly in flyinfo:
        for N in xrange(6):
            c[N] += float(fly[N])
    
    x=c[0]/float(flycount)
    y=c[1]/float(flycount)
    z=c[2]/float(flycount)
    vx=c[3]/float(flycount)
    vy=c[4]/float(flycount)
    vz=c[5]/float(flycount)

    try:
        tmin = -((x*vx+y*vy+z*vz)/(vx*vx+vy*vy+vz*vz))
    except Exception:
        tmin = 0

    if tmin < 0 or tmin == -0 :
        tmin = 0
        
    dmin = math.sqrt(math.pow(x+vx*tmin,2)+math.pow(y+vy*tmin,2)+math.pow(z+vz*tmin,2))

    print('Case #'+str(loop+1)+': %(dm).8f %(tm).8f'%{"dm":dmin, "tm":tmin})

Problem C. Bribe the Prisoners

Divide&Conquer!

# -*- coding: cp949 -*-

def iinput(): return int(raw_input()) 
def inputline(typ): return map(typ, raw_input().split())

def track(start, end, po):
    if len(po)==0:
       return 0

    P1,P2 = 0,0

    cost = []
    for N in xrange(len(po)):
        P1 = track(start,po[N]-1,po[:N])
        P2 = track(po[N]+1,end,po[N+1:])
        cost.append(P1+P2)
    
    return linesize[start,end]-1+min(cost)


for loopC in xrange(iinput()):

    P,Q = inputline(int)
    points = inputline(int)

    global linesize
    linesize = {}
    
    points+=[0,P+1]
    points.sort()

    for x in points:
        for y in points:
            if x < y:
                linesize[(x+1, y-1)] = y-x-1

    points.pop(0)
    points.pop()

    result = track(1,P,points)
    print('Case #{0}: {1}'.format(loopC+1,result))

Small만 통과한 코드(..?)

# -*- coding: cp949 -*-

def iinput(): return map(int,raw_input().split())

for loopC in xrange(int(raw_input())):
    P, Q = iinput()
    Fr = iinput()

    global Size
    Size = {}

    Fr.append(0)
    Fr.append(P+1)
    Fr.sort()

    for x in xrange(Q+2):
        for y in xrange(x+1,Q+2):
            if (Fr[x],Fr[y]) not in Size:
                Size[(Fr[x]+1,Fr[y]-1)]=100000000000000000

    for x in xrange(Q+1):
        Size[(Fr[x]+1,Fr[x+1]-1)]=0

    for Diff in xrange(2,Q+2):        #간격크기!
#        print("Diff : {0}".format(Diff))
        for Seq in xrange(Q):       #Seq번째 구간!
            try:
#                print("  <<{0}~{1}>>".format(Fr[Seq]+1,Fr[Seq+Diff]-1))
                for n in xrange(1,Diff):
                    tempsize=0
                    tempsize += Size[(Fr[Seq]+1,Fr[Seq+n]-1)]
                    tempsize += Size[(Fr[Seq+n]+1,Fr[Seq+Diff]-1)]
                    tempsize += Fr[Seq+Diff]-Fr[Seq]-2
#                    print("      N:{4}   <{0}~{1}> + <{2}~{3}>".format(Fr[Seq]+1,Fr[Seq+n]-1,Fr[Seq+n]+1,Fr[Seq+Diff]-1,n))
#                    print("        Tempsize : {0}, {1}+{2}+{3}".format(tempsize, Size[(Fr[Seq]+1,Fr[Seq+n]-1)], Size[(Fr[Seq+n]+1,Fr[Seq+Diff]-1)],Fr[Seq+Diff]-Fr[Seq]-2))
                    if tempsize < Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)]:
                        Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)] = tempsize
            except Exception:
                pass
#        iinput()

    print('Case #{0}: {1}'.format(loopC+1,Size[(1,P)]))

기준을 잡기 위해서 극을 달리는 숫자를 쉽사리 안되는 이유! ~~~버그 잡으려고 print 막 넣은 거 봐..~~~

Large도 되는 코드

# -*- coding: cp949 -*-

def iinput(): return map(int,raw_input().split())

for loopC in xrange(int(raw_input())):
    P, Q = iinput()
    Fr = iinput()

    global Size
    Size = {}

    Fr.append(0)
    Fr.append(P+1)
    Fr.sort()

    for x in xrange(Q+1):
        Size[(Fr[x]+1,Fr[x+1]-1)]=0

    for Diff in xrange(2,Q+2):        #간격크기!
        for Seq in xrange(Q):       #Seq번째 구간!
            try:
                for n in xrange(1,Diff):
                    tempsize=0
                    tempsize += Size[(Fr[Seq]+1,Fr[Seq+n]-1)]
                    tempsize += Size[(Fr[Seq+n]+1,Fr[Seq+Diff]-1)]
                    tempsize += Fr[Seq+Diff]-Fr[Seq]-2

                    if (Fr[Seq]+1,Fr[Seq+Diff]-1) not in Size:
                        Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)] = tempsize
                    elif tempsize < Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)]:
                        Size[(Fr[Seq]+1,Fr[Seq+Diff]-1)] = tempsize
            except Exception:
                pass

    print('Case #{0}: {1}'.format(loopC+1,Size[(1,P)]))