TopCoder SRM 748 Div1 Medium UnreliableRover

これはまぁ普通に。
https://community.topcoder.com/stat?c=problem_statement&pm=15290

問題

グリッド上をロボットが動くことを考える。
ロボットの行動は以下のコマンドで記述される。

• 上下左右の方向(D[i])+移動マス数の最小値(min[i])・最大値(max[i])

ロボットは指定された方向に、min[i]～max[i]の間のいずれかのマスだけ移動する。

なお、一部のコマンドは方向が指定されていない。この時、min[i]=0であることが保障される。
ロボットが止まりうるマスは何通りか。

解法

コマンドの順番は関係しないので、まずは方向が指定されたコマンドをすべて処理しよう。
そうすると、移動可能範囲はある矩形になる。
例えば幅W、高さHの範囲だとする。まずこの時点でH*Wだけ止まりうるマスがある。

その後、方向が指定されていないコマンドを考える。
そのようなコマンドのmax[i]の総和をSとする。
左端からずっと左、右端からずっと右、下端からずっと下、上端からずっと上、だけ移動するケースを考えると、2*(W+H)*Sだけ移動可能な範囲が広がる。
残るケースは、右上角マスからさらに、右上方向に移動する場合と、同様にたの３つの角からその向きに進むケースである。

これはmax[i]の部分列の和をvとしたとき、右上マスの位置を(0,0)とみなすと(0,0)-(v,S-v)の範囲を移動可能なことに相当する。
よって、いくつかの矩形の和集合の範囲に移動可能ということになるので、その和を求めよう。

class UnreliableRover {
	public:
	long long getArea(string direction, vector <int> minSteps, vector <int> maxSteps) {
		ll XW=1,YW=1,S=0;
		vector<int> V;
		int i;
		FOR(i,direction.size()) {
			if(direction[i]=='?') {
				V.push_back(maxSteps[i]);
				S+=maxSteps[i];
			}
			if(direction[i]=='N' || direction[i]=='S') YW+=maxSteps[i]-minSteps[i];
			if(direction[i]=='W' || direction[i]=='E') XW+=maxSteps[i]-minSteps[i];
		}
		
		ll ret=XW*YW+2*(XW+YW)*S;
		
		vector<ll> Vs;
		for(int mask=0;mask<1<<V.size();mask++) {
			ll s=0;
			FOR(i,V.size()) if(mask&(1<<i)) s+=V[i];
			Vs.push_back(s);
		}
		sort(ALL(Vs));
		FOR(i,Vs.size()) if(i) ret+=(Vs[i]-Vs[i-1])*(S-Vs[i])*4;
		
		return ret;
		
	}
}

まとめ

本番コードはもう少し長かったけど、解法はすぐ思い浮かんだ。