AtCoder ABC #221 : G - Jumping sequence

なるほど…。
https://atcoder.jp/contests/abc221/tasks/abc221_g

問題

N要素の正整数列Dが与えられる。
2次元座標上(0,0)にある駒を、i回目のステップではD[i]だけ上下左右のいずれかに移動するものとする。
最終的に(A,B)に移動する手順があるか。あるならそれを示せ。

解法

座標を45度回転した座標系を考える。
元の座標で(x,y)であった点が(p,q)に移動するとき、p=x+y, q=x-yに遷移するとする。
こうすると、元の座標で

• 上または右に移動するとpがD[i]、下または左に移動すると-D[i]増える。
• 下または右に移動するとqがD[i]、上または左に移動すると-D[i]増える。

元の座標だとX座標かY座標どちらかだけ増減するので扱いにくいが、回転後の座標だとp,qそれぞれ必ず増減し、かつp,qバラバラに考えられるので少し簡単になる。
さらに座標を少し変形し、

• 上または右に移動するとpがD[i]、下または左に移動すると0増える。
• 下または右に移動するとqがD[i]、上または左に移動すると0増える。

というようにすると、負の値が消えさらに容易になる。(負の値があってもアルゴリズム上別に困らないが、後に出るbitsetでTLEする)

この座標系で、最終的にp=(sum(D)+A+B)/2、q=(sum(D)+A-B)/2に移動できれば、元の座標系で(A,B)に移動できることになる。
そこで、p,qについて独立にbitsetを使い移動先を総当たりしつつ、DP復元をして移動経路を求めよう。

int N,A,B;
int D[2020];

bitset<1800*2008> dp[2010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	int S=0;
	FOR(i,N) {
		cin>>D[i];
		S+=D[i];
	}
	if(abs(A)+abs(B)>S) return _P("No\n");
	
	vector<int> T[2];
	FOR(y,2) {
		dp[0].reset();
		dp[0][0]=1;
		FOR(i,N) dp[i+1]=dp[i]|(dp[i]<<D[i]);
		x=(S+A+(y==0?B:-B));
		if(x%2) return _P("No\n");
		x/=2;
		if(dp[N][x]==0) return _P("No\n");
		for(i=N-1;i>=0;i--) {
			assert(dp[i+1][x]);
			if(dp[i][x]) {
				T[y].push_back(0);
			}
			else {
				T[y].push_back(1);
				x-=D[i];
			}
		}
		assert(x==0);
	}
	reverse(ALL(T[0]));
	reverse(ALL(T[1]));
	string ret;
	FOR(i,N) {
		if(T[0][i]==0&&T[1][i]==0) ret+="L";
		if(T[0][i]==0&&T[1][i]==1) ret+="D";
		if(T[0][i]==1&&T[1][i]==0) ret+="U";
		if(T[0][i]==1&&T[1][i]==1) ret+="R";
	}
	cout<<"Yes"<<endl;
	cout<<ret<<endl;
	
	
}

まとめ

このアルゴリズムだと言語によってはMLE解決ができなさそう。