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

A. Memory and Crow

ざっくりと大意

・長さnの数列bを入力で与えられる数列aから再現する。
・サンプル1でa[0]が6なのは、b[0]-b[1]+b[2]-b[3]+b[4]の結果が6だから。a[1]が-4なのはb[1]-b[2]+b[3]-b[4]の結果が-4だから。

Python2

n=int(raw_input())
b=[]
e=o=0
a=map(int,raw_input().split())
for i,j in enumerate(a[::-1]):
    if i%2==0:
        tmp=j-(e-o)
        e+=tmp
    else:
        tmp=j-(o-e)
        o+=tmp
    b.append(str(tmp))
print ' '.join(b[::-1])

コンテスト参加当時も思ったけど末尾から以外に数を決められない気がする。末尾からみればnの偶奇に関わらずa[n-1]とb[n-1]が等しいし、b[n-2]はa[n-2]+b[n-1]と等しいので決められる。以降は1つ進むごとに使い方の正負が入れ替わるのでbに入るものを末尾から変数を2つに分けて和を求めておく。和だけわかっていれば1つ進むごとに正負の反転を入れ替えて計算すればよい。

B. Memory and Trident

ざっくりと大意

・移動情報LRUDの最小で何箇所を書き換えると初期位置に戻って終わりになるか。
・サンプル1のRRUは初期位置に戻って終る形にはならないので-1、サンプル2はLDUR(多分UDUDでも良い気がする)の1箇所書き換えが解になる。

Python2

s=raw_input()
x=y=0
for i in s:
    if i=='R':
        x+=1
    elif i=='U':
        y+=1
    elif i=='D':
        y-=1
    else:
        x-=1
print (abs(x)+abs(y))/2 if len(s)%2==0 else -1

文字列が奇数個だとどうやっても無理なので-1になる。UDとLRに分けて初期位置からの離れを+-で加減して最後に絶対値の和を2で割る。例えばULで初期位置から2離れている場合にRLやUDとすると初期位置に戻る。2つ差があるものを1つ相殺するように書き換えると2つ縮むのである、多分。そのために最後に2で割ります。