Google의 그 것!
개요 ¶
2.1.1. 정황 및 느낀 점 ¶
2시간 30분에 A B 다 풀고 C-Small 풀었다. 65/100
1. BackTracking 참으로 오랜만에 써 봤다. 근데 O(N^N)...
2. C번 코드를 2개 짰다...(DC, DP) 2번째 꺼 짜고 돌렸는데 Incorrect! 보고 절망..
3. O(N^N) 코드는 다음부터 짜면 안되겠다. (100^100)
2. C번 코드를 2개 짰다...(DC, DP) 2번째 꺼 짜고 돌렸는데 Incorrect! 보고 절망..
3. O(N^N) 코드는 다음부터 짜면 안되겠다. (100^100)
C-Large 를 넣었는데, 해방자 100명! 터짐..
4. 파이썬으로 알고리즘 처음 짜는데, 확실히 C보다 편하다.그럼에도 불구하고 C++을 많이 쓰는 건.. 상대적으로 2% 부족한 속도 때문인가??
2.1.2.1. 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로 엄청 줄일 수 있을 것 같다.
지금 생각해 보니, dictionary로 엄청 줄일 수 있을 것 같다.
2.1.2.2. 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})
2.1.2.3.1. 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))
2.1.2.3.2. 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 막 넣은 거 봐..~
~
2.1.2.3.3. 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)]))
