SRM557 DIV1 250 FoxAndMountainEasy

SRM

nからhistory.size()を引いた残りでどう動けばいいかを決める。
重要なのは、U,Dの個数さえ決まってしまえば順番がどうであろうと結果は一緒ということ。
ただしh[i]が負の数になってはいけない。
h[i]が負にならないためにはUをh[0]側に寄せればいい。

m = n - history.size() とすると、長さmのsequenceで移動できるのは

  • m, -m+2, -m+4, ... , m-2, m 。

（例えば m = 4 のとき
　DDDD：-4
　UDDD：-2
　UUDD： 0
　UUUD：+2
　UUUU：+4
）

この範囲で全探索をして条件をみたすものがあればYES、なければNOを返す。

#include <string>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, n)
using namespace std;

class FoxAndMountainEasy {
    public:
    string possible(int N, int h0, int hn, string history)
    {
        int n=history.size();
        int dh=0;
        rep(i,n) dh+=history[i]=='U'?1:-1;
        int m=N-n;
        for(int i=-m,d=m,u=0;i<=m;i+=2,d--,u++) if(h0+i+dh==hn) {
            for(int j=0;j+n<=N;j++) {
                bool ok=true;
                int h=h0+min(u,j);
                if (h<0) ok=false;
                for(int k=0;k<n;++k) { 
                    h+=history[k]=='U'?1:-1;
                    if (h<0) ok=false;
                }
                if (ok) return "YES";
            }
        }
        return "NO";
    }
};