読者です 読者をやめる 読者になる 読者になる

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

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を満たしたりすると調査候補から外す。