SRM 557 DIV1 Easy - MergersDivOne (復習×)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=12195

山登りをし、スタートの高さとゴールの高さ、ステップ数が与えられる。
1ステップごとに、1段上がるか下がるかすることができる。
また、登山の部分列が与えられる。
このとき、登山にその部分列が存在するときは”YES”、存在しないときは”NO”を返す。

解き方


まずはその部分列の操作をしたとき、ゴールにたどり着けるかを判定。
残りのステップ数がゴールへの距離も多い時はNO。
残りのステップ数を2で割ったときの余りと、ゴールへの距離を2で割ったときの余りが一致しない場合もNO.

次に、その部分列の操作をしたときに高さが0未満にならないかを判定。
まず、残りのステップ数からゴールまでのステップ数を引き、その半分は余裕がある。
また部分列の操作をしたあとに上る操作ならば最初に登っておいてもよいため、
ゴールまでのステップ数の分も余裕がある。

Challenge
登山のため、高さが0未満になることはないことに注意。

コード


class FoxAndMountainEasy {

public: string possible(int n, int h0, int hn, string history) {
int x=h0,m=history.size();

FORE(i,0,history.size()){
if(history[i]=='U')x++;
else x--;
}
int d=hn-x;
if(d<0)d=-d;
if(n-m<d)return "NO";
if((n-m)%2!=d%2)return "NO";

int up=(n-m-d)/2;
if(x<hn)up+=hn-x;
x=h0+up;

FORE(i,0,history.size()){
if(history[i]=='U')x++;
else x--;
if(x<0)return "NO";
}
return "YES";
}

};
このエントリーをはてなブックマークに追加