Codeforces #821 : Div2 E. Conveyor

割とすんなり解けた。
https://codeforces.com/contest/1733/problem/E

問題

120*120のグリッドが与えられる。
以下に答えよ。

各セルには、初期状態で右向きの矢印が書かれている。
また左上のマスにはボールが置かれている。

毎秒以下が行われる。

• ボールが置かれたマスは、矢印の向きにそってボールが隣接マスに移動する。
• 移動後、そのマスの矢印は右向きと下向きが反転する。
• 左上マスに新たなボールが置かれる。

T秒後、セル(X,Y)にボールがあるかどうか答えよ。

解法

T秒後にセル(X,Y)に行くボールは、T-(X+Y)秒に左上マスに置かれたボールということになる。
そこでT-(X+Y)秒後までに、各マスに何回ボールが来たかをカウントしよう。
これはDPで容易に求められる。

この時の各マスに至るボールの回数の偶奇で、矢印の向きが決まる。
あとはT-(X+Y)秒に左上マスに置いたボールがどう移動するかシミュレートすればよい。

int Q;
ll T,X,Y;

ll F[122][122];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>T>>Y>>X;
		T-=X+Y;
		if(T<0) {
			cout<<"NO"<<endl;
			continue;
		}
		ZERO(F);
		F[0][0]=T;
		FOR(y,121) FOR(x,121) {
			F[y][x+1]+=(F[y][x]+1)/2;
			F[y+1][x]+=(F[y][x])/2;
		}
		int cx=0,cy=0;
		int ok=0;
		while(cx<120&&cy<120) {
			if(cx==X&&cy==Y) ok=1;
			if(cx>X||cy>Y) break;
			if(F[cy][cx]%2==0) cx++;
			else cy++;
		}
		
		if(ok) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
		
	}
	
	
}

まとめ

2750ptの割には簡単？