BLOG ARTICLE codejam | 4 ARTICLE FOUND

  1. 2010.05.09 Codejam 2010 시작 1
  2. 2009.09.05 Codejam 2009 - Qualification Round
  3. 2009.08.22 Train Timetable 1
  4. 2009.08.21 Saving the Universe 1

Codejam 2010 시작

잡담 2010. 5. 9. 11:30
어제 오전 8시, Codejam 2010 Qualification round가 시작되었습니다.

Qualification round는 24시간 내에 1문제만 풀면 되기 때문에 그리 어려운 편은 아니지만, 어제는 어버이날이고 아점부터 약속이 3건이나 있기도 하고, 다음 라운드에서도 잘 해내려면 속도가 좀 붙어야 하기 때문에 일단 2시간 30분 내에 다 풀기로 작정하고 8시에 일어나자마자 ㄱㄱ!

영어권이 아니라는 비애를 몸소 체험하며, 문제이해가 역시 가장 어렵다는 것을 또다시 느꼈습니다. 문제 풀이 시간의 반 이상이 문제를 이해하는게 걸린것 같네요. 하여간, 이번 round에서 가장 아쉬웠던 건 large set을 별 생각없이 제출해서 기회를 박탈당한게 제일 컸습니다. 문제가 쉬워서 거의 동일한 알고리즘으로 해도 되었는데, 예외처리를 안해서 fail난 것도 있고 안습이었네요.

이번 대회 우리나라 참가자들 목록 및 스코어는 다음 링크를 보면 알 수 있습니다.
http://www.go-hero.net/jam/10/regions/South%20Korea

유명한 분들도 좀 보이고, 아는 사람들도 보이네요.
평소에 쓰던 아이디를 안써서 아는 사람인지 아닌지 헷깔리는 사람도 있구요 ㅎㅎ.

다들 화이팅입니다.
즐거운 주말 보내세요~
AND

Codejam 2009 - Qualification Round

개발/기타 2009. 9. 5. 00:07


어제 짬짬히 구글코드잼 2009 에 참가해서 문제를 풀었는데, 2문제 밖에 못 풀었네요. 머리가 엄청 굳었나 봅니다. 늦게 풀기 시작한데다가 중간에 병원 갔다오고 잡무를 처리했는데도, 시간 카운트를 다 하네요 ㅎㅎ

33점만 넘으면 Qualification Round는 통과하니 별 문제 없겠지만, 이 다음 round 부터 통과하려면 2시간 내에 풀 수 있는 문제와 없는 문제를 후딱 선별해서 푸는 능력이 필요할 듯 합니다.

누구나 다 그렇겠지만, 코딩보다는 문제해석과 적당한 알고리즘을 선택하는게 시간이 걸리네요. 특히 전 문제해석이 너무 오래 걸리는 것 같아요. 이번에 1번과 3번 문제를 풀었는데, 1번은 금새 풀었지만 3번 문제를 특히나 아주 살짝 잘못 이해해서 왜 오답이 나오는지 모르고 오답 제출을 8번이나 하는 추태를 보였답니다 ㅠㅜ; 이 다음 목표는 round 1 통과인데, 과연 잘 되려나 모르겠네요 ^^;
AND

Train Timetable

개발/python 2009. 8. 22. 01:03
이번에는 두번째 문제인 기차시간표입니다.

문제는 다음과 같습니다.


제일 가까운 기차들을 모두 이어주고,
앞뒤로 이어지지 않은 기차들을 카운트해주면 됩니다.

소스코드는 다음과 같습니다.

  1. import sys
  2. import datetime
  3.  
  4. class train:
  5.   def __init__(self, row, dir):
  6.     st = row.split(' ')[0]
  7.     end = row.split(' ')[1]    
  8.     self.start = datetime.datetime( 2009,1,1, int(st.split(':')[0]), int(st.split(':')[1]) )
  9.     self.end = datetime.datetime( 2009,1,1, int(end.split(':')[0]), int(end.split(':')[1]) )
  10.     self.dir = dir
  11.     self.reserved1 = 0
  12.     self.reserved2 = 0
  13.  
  14. def asc_start(a,b):
  15.   if a.start < b.start:
  16.     return -1
  17.   else:
  18.     return 1
  19.  
  20. def desc_end(a,b):
  21.   if a.end < b.end:
  22.     return 1
  23.   else:
  24.     return -1
  25.  
  26. if __name__=="__main__":
  27.   if len(sys.argv)>1:
  28.     inp = sys.argv[1]
  29.   else:
  30.     print "append an input file param"
  31.     sys.exit()
  32.  
  33.   f = open( inp, 'rt' )
  34.   nTC = int( f.readline() )
  35.   print 'the number of tc :', nTC
  36.  
  37.   output_file = inp.split('.')[0]+"_output.txt"
  38.   fout = open( output_file, 'wt')
  39.  
  40.   for i in range(0,nTC):
  41.     turnaround = int( f.readline() )
  42.    
  43.     NA_NB = f.readline()
  44.     NA = int( NA_NB.split(' ')[0] )
  45.     NB = int( NA_NB.split(' ')[1] )
  46.    
  47.     trains = []
  48.     for n in range(0,NA):
  49.       row = f.readline()
  50.       trains.append( train( row, 'A' ) )
  51.     for n in range(0,NB):
  52.       row = f.readline()
  53.       trains.append( train( row,'B') )
  54.  
  55.     trains.sort(desc_end)
  56.    
  57.     #process
  58.     ta = datetime.timedelta( 0, turnaround*60 )
  59.    
  60.     for t1 in trains:
  61.       if t1.reserved2>0: continue
  62.       cands = []
  63.       for t2 in trains:
  64.         if t2.reserved1>0: continue
  65.          
  66.         if ( t1.end + ta <= t2.start ) and (t1.dir != t2.dir):
  67.           cands.append( t2 )
  68.          
  69.       if cands:
  70.         cands.sort( asc_start )
  71.         min = cands[0]
  72.         #print t1.start, t1.end, t1.dir
  73.         #print '\t',min.start, min.end, min.dir
  74.        
  75.         t1.reserved2 = min.reserved1 = 1
  76.  
  77.     NA = NB = 0
  78.     for t in trains:
  79.       if t.reserved1==0:
  80.         if t.dir=='A':
  81.           NA+=1
  82.         else:
  83.           NB+=1
  84.  
  85.     # result
  86.     print 'Case #'+str(i+1)+':' ,NA, NB
  87.     fout.write( 'Case #'+str(i+1)+': ' +str(NA) + ' '+str( NB)+'\n')
  88.  
  89.   f.close()
  90.   fout.close()


실행결과는 다음과 같으며, 모두 Correct입니다.


AND

Saving the Universe

개발/python 2009. 8. 21. 01:48
요즘 기분이 꿀꿀해서 CodeJam 2008 Qualification Round 문제 중 하나인, 'Saving the Universe'를 풀어봤습니다.

1번 문제(Saving the Universe)는 다음과 같습니다.
문제링크 : http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGI36AQw#

그냥 간단하게 검색엔진 list를 둬서 카운트 하다가 꽉차면 다시 비우고를 반복하면 끝입니다.
파이썬 코드는 다음과 같습니다. (2.5.4버전으로 했음)

  1. import sys
  2.  
  3. def isAllChecked(d):
  4.   ret = True
  5.   for k in d.keys():
  6.     if d[k]<1:
  7.       ret = False
  8.   return ret
  9.  
  10. if __name__=="__main__":
  11.   if len(sys.argv)>1:
  12.     inp = sys.argv[1]
  13.   else:
  14.     print "append an input file param"
  15.     sys.exit()
  16.  
  17.   f = open( inp, 'rt' )
  18.   nTC = int( f.readline() )
  19.   print 'the number of tc :', nTC
  20.  
  21.   output_file = inp.split('.')[0]+"_output.txt"
  22.   fout = open( output_file, 'wt')
  23.  
  24.   for i in range(0,nTC):
  25.     nEngine = int( f.readline() )
  26.     engines = []
  27.     for e in range(0,nEngine):
  28.       engine = f.readline()
  29.       engines.append( engine )
  30.     nKeyword = int( f.readline() )
  31.     keywords = []
  32.     for k in range(0,nKeyword):
  33.       keyword = f.readline()
  34.       keywords.append( keyword )
  35.    
  36.     # process
  37.     dEngine = {}
  38.     for e in engines:
  39.       dEngine[e]=0
  40.     nCount = 0
  41.     for k in keywords:
  42.       if k in dEngine.keys():
  43.         dEngine[k] += 1
  44.         if isAllChecked(dEngine):
  45.           for e in engines:
  46.             dEngine[e] = 0
  47.           nCount += 1
  48.           dEngine[k] += 1
  49.          
  50.     # result
  51.     print 'Case #' + str(i+1)+': '+str( nCount )
  52.     fout.write( 'Case #' + str(i+1)+': '+str( nCount ) + '\n' )
  53.      
  54.   f.close()
  55.   fout.close()

실행결과는 다음과 같으며, 둘다 Correct 입니다.


AND

티스토리툴바