yukicoder : No.1055 牛歩

こっちは逆に★4のままでもいい気がした。
https://yukicoder.me/problems/no/1055

問題

N個のマスが左右に並んでおり、M個のコマの位置が与えられる。
ここで、Q個のクエリが与えられる。
クエリではコマの番号が指定されるので、左右いずれか1マス動かす。
ただし、Nマスの外に出たり、他のコマとぶつからないようにしたい。

そのような移動方法はあり得るか判定せよ。

解法

初期状態で一番左にいるコマから順に考える。
このコマは、できるだけ左に移動し、これ以上左に行くと外にはみ出る場合のみ右に動かすのが最適である。
さて、左からi番目のコマの移動経路が決まると、(i+1)番目のコマは、i番目のコマにぶつからない範囲でできるだけ左に動かすのが良いことになる。

ここまでわかると、左から順に時間毎の位置をどん欲に求めていけばよい。
基本的には、p回目のクエリで(i+1)番のコマをどう動かそうか考えるとき、次にそのコマを動かすタイミングがq回目のクエリとする。

• i番目のコマがp～q回目のクエリの間にどこにいるかを考えると、(i+1)番目のコマはその間のi番目のコマの最も右の位置より右にいなければならない。
• 加えて、(i+1)番のコマは、p回目以前のクエリの後の位置と、q回目以降のクエリの後の位置から1だけ動いた場所にしか移動できない。

上記を両方満たす場所のうち、一番左に移動するようにしよう。ダメなら移動方法はない、が答え。

int N,M,Q;
int A[202020];
vector<pair<int,int>> T[202020];
vector<int> ev[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i];
		A[i]--;
		T[i].push_back({0,0});
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>x;
		T[x-1].push_back({i+1,0});
	}
	FOR(i,M) {
		int cur=A[i];
		if(i==0) {
			T[0][0].second=A[0];
			FOR(x,T[i].size()) if(x) {
				T[i][x].second=T[i][x-1].second;
				if(T[i][x].second>0) T[i][x].second--;
				else T[i][x].second++;
				if(T[i][x].second>=N) return _P("NO\n");
			}
		}
		else {
			x=0;
			y=0;
			T[i][0].second=A[i-1];
			while(x<T[i].size()-1||y<T[i-1].size()-1) {
				if(x<T[i].size()-1&&y<T[i-1].size()-1) {
					if(T[i][x+1].first<T[i-1][y+1].first) x++;
					else y++;
				}
				else if(x<T[i].size()-1) {
					x++;
					
				}
				else {
					y++;
				}
				T[i][x].second=max(T[i][x].second,T[i-1][y].second);
			}
			FOR(x,T[i].size()-1) T[i][x+1].second=max(T[i][x+1].second,T[i][x].second-1);
			for(x=T[i].size()-2;x>=0;x--) T[i][x].second=max(T[i][x].second,T[i][x+1].second-1);
			cur=A[i];
			FORR(t,T[i]) {
				if(t.first>0) {
					if(t.second<cur-1) cur--;
					else cur++;
				}
				if(cur<=t.second || cur>=N) return _P("NO\n");
				t.second=cur;
			}
		}
	}
	cout<<"YES"<<endl;
	
	
}

まとめ

2つめの条件を思いつくのにちょっと手間取った。