Codeforces #831 : D. Knowledge Cards

なんか異様に苦戦して以上にダメだった回。
https://codeforces.com/contest/1740/problem/D

問題

H*Wのグリッドがあり、初期状態で左上マスに1～Kの番号を持つカードが積まれている。
また、初期状態でカードの積まれた順が与えられる。

カードの山があるマスを1つ選び、一番上のカードを右または下のマスのカードの山の一番上に移すことを考える。
最終的に右下マスに、上から1,2,3...,Kとカードが並ぶようにできるか。

解法

カードの番号の大きい順に右下に積んでいくことを考える。
途中、左上と右下を除く(H*W-2)マス分だけ、まだ右下に持っていけないカードを保留させておくことができると考え、保留中のカード一覧を更新していけばよい。

int T;
int H,W,K;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>K;
		FOR(i,K) {
			cin>>A[i];
			A[i]--;
		}
		
		set<int> S;
		int ma=K-1;
		FOR(i,K) {
			S.insert(A[i]);
			if(S.size()==H*W-2) break;
			while(S.size()&&*S.rbegin()==ma) {
				S.erase(ma);
				ma--;
			}
		}
		if(i<K) {
			cout<<"TIDAK"<<endl;
		}
		else {
			cout<<"YA"<<endl;
		}
		
		
	}
}

まとめ

なんで本番こんなに手間取ったんだろ。