IndiaHacks 2016 - Online Edition (Div.1 + Div.2)
はい。
http://codeforces.com/contest/653
A. Bear and Three Balls
ざっくりと大意
・n個のボールのサイズがそれぞれtである。
・n個の中から3個選んでプレゼントするのに同じサイズの重複がないように、差は最大で2以内に抑えられるか??
Python2
n=int(raw_input()) #n,k=map(int,raw_input().split()) t=set([i for i in map(int,raw_input().split())]) t=list(t) t.sort() tmp=len(t) for i in range(2,tmp): if t[i]==t[i-1]+1==t[i-2]+2: print 'YES' exit() print 'NO'
setで重複排除して、listにしてソートして3連番があるかを探した。
B. Bear and Compressing
ざっくりと大意
・熊はa,b,c,d,e,fしかわからない。熊は2文字のアルファベットを圧縮して1文字にする(\(a_i\)が\(b_i\)になる)。
・長さnの文字列を左からq回の圧縮作業でにaにしたい。
・サンプル1では4パターンある。例えば初期の文字列がabbだと左1,2文字目のabを圧縮するとaになる。New1文字目のaと作業前は3文字目だったbと並んでabになる。abは圧縮するとaになる。
Python2
n,q=map(int,raw_input().split()) d={} ans=chk=0 l=[] for i in range(q): a,b=map(str,raw_input().split()) d[a]=b if b=='a': l.append([a[0],2]) while 1: if len(l)==0: break tmp=l.pop() if tmp[1]==n: ans+=1 continue for i in d: if d[i]==tmp[0]: cnt=tmp[1]+1 if cnt==n: ans+=1 elif cnt<n: p=i[0] l.append([p,cnt]) print ans
最終形のaから伸ばしていってn文字に出来るかを調べた。圧縮前の2文字の文字列1文字目と圧縮後の文字が一致するのが伸ばす先になると思う。伸ばす先がなかったり、長さnを満たしたりすると調査候補から外す。