Codeforces Round #376 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Night at the Museum

ざっくりと大意

・問題文の図のようにa,b,c...y,z,aでループしているもので入力の文字列の移動距離がいくつになるか。

Python2

s=raw_input()
chk=ord('a')
ans=0
for i in s:
    tmp=abs(ord(i)-chk)
    ans+=min(tmp,26-tmp)
    chk=ord(i)
print ans

ordで各文字の相対距離で移動前と移動後の差の絶対値がz-a間のループを利用しない移動、26と左記の値の差がループを利用する移動。小さい方の距離を加算して、現在地を更新し続けていけば大丈夫そう。

B. Coupons and Discounts

ざっくりと大意

・1日でピザを2枚買うか、2日連続で1枚買うとクーポン対象になる。
・n日間のピザの買い方aが全てクーポン対象となっているか？

Python2

n=int(raw_input())
a=map(int,raw_input().split())
a.append(0)
for i in range(n):
    a[i]%=2
    a[i+1]-=a[i]
    a[i]=0
    if a[i+1]<0: break
print 'YES' if -1 not in a else 'NO'

チェック日が偶数なら0にして、奇数なら2日連続の1枚想定で1日先を-1した。完走して数列を全て0に出来ればクーポンがYESで何処かで買い足りない、-1になる日が出たらNO。

C. Socks

ざっくりと大意

・n本k色の靴下をm日間で履く予定表の\(l_i\)と\(r_i\)がある。
・l,rが色違いで履くことがないようにn本ある靴下の色を変える最小数はいくつか。
・UnionFind使うっぽい？あとで