Codeforces Beta Round #4 (Div. 2 Only)
はい。
A. Watermelon
ざっくりと大意
・Pete and Billyは真夏のめっさ暑い日にスイカを買う。
・2つに分けられて・割りきれて、かつそれぞれの重さが分けた個数以上でなければならない??
方針のようなもの
重さが2で割りきれて、かつ重さが2ではないことでYES判定にした。
自然数の2で割り切れる数で2ではないものは4以上しかない(と思う)。4以上であれば2つに分けて重さが2以上になる。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math start = time.clock() w=sys.stdin.readline() #print 'NO' if int(w)%2==1 or int(w)==2 else 'YES' print 'YES' if int(w)%2==0 and int(w)!=2 else 'NO'
B. Before an Exam
ざっくりと大意
・d日間でsumtime時間丁度勉強しなければならない。 ・その日によって勉強できる時間が違う。 ・勉強に割く最小時間と最大時間が与えられる。
方針のようなもの
・最小の合計と最大の合計の間でなければNOになる。 ・ぴったり最小or最大の合計と同じならそのまま出力 ・最小に近ければ1ずつ加算、最大に近ければ1ずつ減算 下記にまだエラー出て書き途中コード
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math start = time.clock() (d,s)=map(int, raw_input().split()) l,m,ans=[],[],[] for n in range(d): i,a=[int(x) for x in sys.stdin.readline().split()] l.append(i) m.append(a) if sum(l)<=s<=sum(m): print 'YES' #最小か最大と同じならそのまま if sum(l)==s: print ' '.join(map(str, l)) elif sum(m)==s: print ' '.join(map(str, m)) else: #最小値よりなら最小値合計リストを加算 #最大値よりなら最大値合計リストを減算 if s-sum(l) < sum(m)-s: ans=l for i in range(len(ans)): if sum(ans)==s: print ' '.join(map(str, ans)) break else: while ans[i]<m[i] and sum(ans)!=s: ans[i]+=1 else: ans=m for i in range(len(ans)): if sum(ans)==s: print ' '.join(map(str, ans)) break else: while ans[i]>l[i] and sum(ans)!=s: ans[i]-=1 else: print 'NO'
C. Registration system
binary search,data structures,hashing,implementation,sortings
ざっくりと大意
なんか名前をたくさん登録する。 初なら'OK'、2つ目以降は'名前1'、'名前2'とナンバリングされていく。
方針のようなもの
最初はリストで適当にやったらTLEで時間が全然足りなかった。 辞書を使うとすごく早くなった。 http://qiita.com/oyakata@github/items/94238e542eaeb643ad12 が詳しく書かれてる。 下は私が提出したものから使わなかった行など省いたもの。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math start = time.clock() #l=[] l={} n=int(raw_input()) for x in xrange(n): i=sys.stdin.readline().strip() if i in l: l[i]+=1 sys.stdout.write(i+str(l[i])+'\n') else: sys.stdout.write('OK'+'\n') l[i]=0
他の人
v = {} for i in [0]*input(): q = raw_input() if q in v:v[q]+=1; print q+`v[q]` else: print 'OK'; v[q] = 0
d={} for _ in xrange(input()): s=raw_input() n=d.setdefault(s,0) d[s]+=1 print s+`n` if n else 'OK'
``で囲うとstrでキャストと同等っぽいようだ。 setdefaultも便利ぽい。 一旦ここまで