問題
http://community.topcoder.com/stat?c=problem_statement&pm=12195
山登りをし、スタートの高さとゴールの高さ、ステップ数が与えられる。
１ステップごとに、１段上がるか下がるかすることができる。
また、登山の部分列が与えられる。
このとき、登山にその部分列が存在するときは”ＹＥＳ”、存在しないときは”ＮＯ”を返す。
解き方
まずはその部分列の操作をしたとき、ゴールにたどり着けるかを判定。
残りのステップ数がゴールへの距離も多い時はＮＯ。
残りのステップ数を２で割ったときの余りと、ゴールへの距離を２で割ったときの余りが一致しない場合もＮＯ．
次に、その部分列の操作をしたときに高さが０未満にならないかを判定。
まず、残りのステップ数からゴールまでのステップ数を引き、その半分は余裕がある。
また部分列の操作をしたあとに上る操作ならば最初に登っておいてもよいため、
ゴールまでのステップ数の分も余裕がある。
Challenge
登山のため、高さが０未満になることはないことに注意。
コード
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";
}
};
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";
}
};