imported>idea0073 |
|
| (One intermediate revision by one other user not shown) |
| Line 1: |
Line 1: |
| Google의 그 것!
| | Google 코드잼 및 알고리즘 연습 겸 코드작성 연습 겸!겸!겸! |
| | https://code.google.com/codejam/ |
|
| |
|
| https://code.google.com/codejam/
| |
| = 개요 = | | = 개요 = |
| 군대 안에서 점점 머리가 굳어가는 걸 깨닫고...
| |
|
| |
|
| '''머리라도 굴리자'''는 의미에서
| | 군대 안에서 점점 머리가 굳어가는 걸 깨닫고 머리라도 굴리자는 의미에서 혼자서 달리자! |
| 혼자서 코드 재밍재밍, 달리자! | |
|
| |
|
| '''이 글의 프로그래밍 언어는 Python(2.7.8)으로 작성되었습니다.''' | | '''그리고 지금''', 퇴화한 머리 이끌고 '''다시 갑니다.''' |
|
| |
|
| __TOC__
| | 코드잼에서 지금껏 나온 문제를 다 풀고 해석하는 것을 목표로 하고 있습니다. |
| | 예전 코드는.. 지웠어요. ~~(볼 게 없어요) (진짜)~~ |
|
| |
|
| 이 글을 쓰는 곳은 영내 자대이므로, 추후 시간을 들여서~~~휴가를 나와서~~~ 정리하겠습니다.
| | 언어는 제가 할 수 있는 모든 언어로 해볼꺼에요. 코드 작성 및 구현 연습도 포함되어 있어서! |
| 자세한 풀이 방법 및 발상 등을 적을 생각입니다.
| |
|
| |
|
| 시간이 생기면 알고리즘 접근에 관련된 이야기들을 주르르륵 적을 것 같습니다.
| | __TOC__ |
| ~~~군대~~~
| |
|
| |
|
| = 문제 풀이 자취 = | | = 문제 풀이 자취 = |
| == 2009년 Round1C ==
| | 준비! |
| 문제 : https://code.google.com/codejam/contest/189252/dashboard
| |
| | |
| ** '''Solve : A-Small, A-Large, B-Small, B-Large, C-Small'''
| |
| ** '''Time'''
| |
| ** A : 30 mins
| |
| ** B : 30 mins
| |
| ** C : 1 hour 30 mins
| |
| * '''Score : 65/100'''
| |
| * '''Incorrect Count : C-Large => 2'''
| |
| * '''Mode : Practice Mode'''
| |
| | |
| * 2시간 30분에 A B 다 풀고 C-Small 풀었다.
| |
| ## 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})
| |
| map(float,raw_input().split())
| |
| 가 순간 기억이 안나서 못 썼다. 그래서 Input 후 자료처리 부분이 지저분하다.ㅜㅠ
| |
| | |
| 3D 좌표가 나오고, '''Ouput을 float로 요구'''하는 하는 바람에,
| |
| 반복문 돌려서 풀었다간 틀릴 것이다!라고 생각해서 결국 수학을 했다. 구의 방정식, 어쩌구저쩌구...
| |
| math에 pow하고 sqrt는 있겠지 하면서 임포트. 있어서 겨우 풀었다. ~~~help(math)~~~
| |
| | |
| === 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))
| |
| C-Small을 풀어낸 코드이다.
| |
| 전형적인 D&C 방식으로 흐름을 풀어냈다.
| |
| 확실히 코드 작성은 평이하지만, 시간 복잡도가 '''O(N^N)'''
| |
| 이 말도 안되는 코드가 통과할 수 있었던 것은, N<=5 였기 때문이다. ~~~max(O(N^N))<=3125~~~
| |
| 하지만 C-Large에 넣었더니 터졌다! 망...
| |
| ==== 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)]))
| |
| '''희대의 삽질'''
| |
| '''Size[(Fr[x]+1,Fr[y]-1)]=100000000000000000'''~~~Infinity Integer~~~ '''이런거 넣으시면 안됩니다.'''
| |
| ~~~버그 잡으려고 print 막 넣은 거 봐.. 결국 잡음. 100000000000000000+4~~~
| |
| 기준점을 일정한 숫자로 잡아버리는 바람에 망한 코드. 성공한 코드는 뒤쪽 참조.
| |
| ==== 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)]))
| |
| 시간이 정말 많이 걸리기는 한다. 그래도 O(N^3)까지 줄였다. '''O(N^3)<=1000000'''
| |
| Dynamic Programming으로 작성. 확실히 머리가 아프다.
| |
| 하지만 시간복잡도를 줄일 수 있다면!
| |
| 애초에 이 문제는 DP로 풀어야 했던 문제인가 보다..
| |
| | |
| == 2014년 Qualification Round ==
| |
| 문제 : https://code.google.com/codejam/contest/2974486/dashboard
| |
| | |
| ** '''Solve : A-Small, B-Small, B-Large, D-Small, D-Large'''
| |
| ** '''Time'''
| |
| ** A : 10 mins
| |
| ** B : 30 mins
| |
| ** C : 30 mins + 40 mins~
| |
| ** D : 50 mins
| |
| * '''Score : 65/90'''
| |
| * '''Incorrect Count : 0'''
| |
| * '''Mode : Practice Mode'''
| |
| | |
| * 2시간동안 A B D 다 풀고, 1시간동안 C 생각하다가 규칙 구체화 실패! 테크닉의 한계를 느끼고 빠르게 포기..
| |
| 예선인 걸 생각하면, 시간 많으니까 풀기는 했을 텐데.. 이 참에 규칙 구성에 대해서 생각해 봐야 겠다.
| |
| ## 이차함수가 머리속에서 그려진다 ..@~@.. 코드는 쉬운데, 변수가 헷갈려서 조금 해맸다.
| |
| ## Deceitful War 문제가 너무 길어서 당황스러웠는데, 손으로 끄적이다 보니 규칙이 나옴!
| |
| '''볼펜과 메모지는 필수입니다.''' 인간 == 아날로그 // 메모지 짱짱!
| |
| ## 저걸 저렇게 풀어 쓴 구글 문제 출제자 분들에게 존경을...(수학적인 것에도 존경을!)
| |
| ## 파이썬이라는 언어의 기본제공명령어를 쓰려고 노력했다.
| |
| 하지만, 그냥 노가다 하는 것 보다 체감상 속도는 조금 더 느린 것 같다.
| |
| | |
| === Problem A. Magic Trick ===
| |
| def iinputs(): return map(int,raw_input().split())
| |
| def iinput(): return int(raw_input())
| |
|
| |
| for loopC in xrange(iinput()):
| |
|
| |
| Fboard, Sboard = [],[]
| |
|
| |
| Fsel = iinput()-1
| |
|
| |
| for N in xrange(4):
| |
| Fboard.append(set(iinputs()))
| |
|
| |
| Ssel = iinput()-1
| |
|
| |
| for N in xrange(4):
| |
| Sboard.append(set(iinputs()))
| |
|
| |
| result = list(Fboard[Fsel]&Sboard[Ssel])
| |
|
| |
| if len(result)==1:
| |
| result = result[0]
| |
| elif len(result)==0:
| |
| result = 'Volunteer cheated!'
| |
| else:
| |
| result = 'Bad magician!'
| |
|
| |
| print('Case #{0}: {1}'.format(loopC+1,result))
| |
| | |
| === Problem B. Cookie Clicker Alpha ===
| |
| def tinputs(typ): return map(typ,raw_input().split())
| |
| def tinput(typ): return typ(raw_input())
| |
|
| |
| for loopC in xrange(tinput(int)):
| |
| C,F,X = tinputs(float)
| |
|
| |
| buyt, fcount = 0.0, 0
| |
| waiit = X/(F*fcount+2)
| |
|
| |
| while 1:
| |
| buyt += C/(F*fcount+2)
| |
| fcount += 1
| |
|
| |
| if buyt + X/(F*fcount+2) < waiit:
| |
| waiit = buyt + X/(F*fcount+2)
| |
| else:
| |
| break;
| |
|
| |
| print('Case #{0}: {1:.7f}'.format(loopC+1,waiit))
| |
| | |
| === Problem D. Deceitful War ===
| |
| def iinput(): return int(raw_input())
| |
| def finputs(): return map(float,raw_input().split())
| |
|
| |
| for loopC in xrange(iinput()):
| |
| count, Naolist, Kenlist = iinput(),finputs(),finputs()
| |
|
| |
| List = Naolist+Kenlist
| |
| List.sort()
| |
| Ken, Naomi = 1,0
| |
|
| |
| for N in xrange(2*count):
| |
| if List[N] in Naolist: List[N] = Naomi
| |
| else: List[N] = Ken
| |
|
| |
| List2 = [N for N in List]
| |
|
| |
| War,Dwar = count,0
| |
|
| |
| for NN in xrange(2*count):
| |
| if List[NN]==Naomi:
| |
| try:
| |
| List[NN], List[List.index(Ken,NN,)] = None, None
| |
| War -= 1
| |
| except Exception:
| |
| break
| |
|
| |
| for NN in xrange(2*count):
| |
| if List2[NN]==Ken:
| |
| try:
| |
| List2[NN], List2[List2.index(Naomi,NN,)] = None, None
| |
| Dwar += 1
| |
| except Exception:
| |
| break
| |
|
| |
| print('Case #{0}: {1} {2}'.format(loopC+1,Dwar,War))
| |
| | |
