Googleì˜ ê·¸ 것! https://code.google.com/codejam/ = 개요 = 군대 안ì—서 ì ì 머리가 굳어가는 걸 ê¹¨ë‹«ê³ ... '''머리ë¼ë„ 굴리ìž'''는 ì˜ë¯¸ì—서 혼ìžì„œ 코드 재ë°ìž¬ë°, 달리ìž! '''-ì´ ê¸€ì˜ í”„ë¡œê·¸ëž˜ë° ì–¸ì–´ëŠ” Python으로 작성ë˜ì—ˆìŠµë‹ˆë‹¤.-''' [[TableOfContents]] ì´ ê¸€ì„ ì“°ëŠ” ê³³ì€ ì˜ë‚´ ìžëŒ€ì´ë¯€ë¡œ, 추후 ì‹œê°„ì„ ë“¤ì—¬ì„œ~~~휴가를 나와서~~~ ì •ë¦¬í•˜ê² ìŠµë‹ˆë‹¤. ìžì„¸í•œ í’€ì´ ë°©ë²• ë° ë°œìƒ ë“±ì„ ì ì„ ìƒê°ìž…니다. = ë¬¸ì œ í’€ì´ ìžì·¨ = == 2009ë…„ Round1C == ë¬¸ì œ : https://code.google.com/codejam/contest/189252/dashboard === ì •í™© ë° ëŠë‚€ ì === * 2시간 30ë¶„ì— A B 다 í’€ê³ C-Small 풀었다. '''65/100''' C-Large ë¹¼ê³ Incorrect! 본 ì 없다. ë¬¼ë¡ , Practice Modeë¼ì„œ ì‹¤ì œí•˜ê³ í‹€ë¦´ 것 같다. 1. BackTracking 참으로 ì˜¤ëžœë§Œì— ì¨ ë´¤ë‹¤. ê·¼ë° O(N^N)... 2. C번 코드를 2ê°œ 짰다...(DC, DP) 2번째 꺼 ì§œê³ ëŒë ¸ëŠ”ë° Incorrect! ë³´ê³ ì ˆë§.. 3. O(N^N) 코드는 다ìŒë¶€í„° 짜면 안ë˜ê² 다. (100^100) C-Large 를 넣었는ë°, '''í•´ë°©ìž 100명!''' í„°ì§.. 4. 파ì´ì¬ìœ¼ë¡œ ì•Œê³ ë¦¬ì¦˜ ì²˜ìŒ ì§œëŠ”ë°, 확실히 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으로 작성. 확실히 머리가 아프다. 하지만 시간복잡ë„를 ì¤„ì¼ ìˆ˜ 있다면! 그것 ë§Œìœ¼ë¡œë„ ê°ì‚¬í•˜ë‹¤.