きままにものづくり

日々の気付いたことなんかを書いてます。

SRM557Div1Easy

問題

隣り合う要素の差分が1である長さnの数列を考える。はじめの要素h0と最後の要素hnが与えられる。差分を示す文字列historyが与えられた時、そのhistoryを実現できるかを判定せよ。historyの要素はUかDのどちらかで、Uはh[i+1]-h[i]=1、Dはh[i+1]-h[i]=-1を示す。数列の各要素は必ず0以上である。

解法

h0からhistoryを始め、その時の最小値を求める。最小値分だけh0に足し合わせ、常に0以上になるようにする。historyと最小値の分を引き、あまりの要素の数を求める。その要素とhnとh0の差分を求め、それが0以上かつ偶数ならば"YES"を返し、それ以外なら"NO"を返す。

計算量

 O(N)

コード