kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2022 Round3 : Easy TwoDimensionalSort

久々に負の点数を取ってしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17625&rd=19264

問題

26*26の盤面で、最大26個のルークが置いてある。
これらはアルファベットが振られている。
ルークを合計で最大60回まで移動し、各ルークの配置がrow-major-orderで昇順に並ぶようにせよ。

解法

まず各行で横移動を行い、全ルークが異なる列に来るようにする。
その後、縦移動してn番目のアルファベットはn行目に来るようにすればよい。

どちらかというと難しいのは前者で、他のルークに移動経路を邪魔されないものを優先的に移動する必要がある。

int Y[26],X[26];
vector<int> ret;
vector <string> S;
class TwoDimensionalSort {
	public:
	void move(int r1,int c1,int r2,int c2) {
		if(r1==r2&&c1==c2) return;
		int dy=0;
		
		ret.push_back(r1);
		ret.push_back(c1);
		ret.push_back(r2);
		ret.push_back(c2);
		swap(S[r1][c1],S[r2][c2]);
	}
	vector <int> sortLetters(vector <string> board) {
		S=board;
		int N=26;
		MINUS(X);
		MINUS(Y);
		int y,x,i;
		
		ret.clear();
		int TX[26]={};
		MINUS(TX);
		int nex=0;
		FOR(y,N) {
			int cnt=0;
			deque<pair<int,int>> V;
			FOR(x,N) if(S[y][x]!='.') V.push_back({x,nex++});
			while(V.size()) {
				FOR(i,V.size()) {
					if(V[i].first==V[i].second) {
						V.erase(V.begin()+i);
						break;
					}
					int L,R;
					if(V[i].first<V[i].second) {
						L=V[i].first+1;
						R=V[i].second;
					}
					else {
						L=V[i].second;
						R=V[i].first-1;
					}
					for(x=L;x<=R;x++) if(S[y][x]!='.') break;
					if(x==R+1) {
						move(y,V[i].first,y,V[i].second);
						V.erase(V.begin()+i);
						break;
					}
					
					
				}
			}
		}
		
		FOR(y,N) FOR(x,N) if(S[y][x]!='.') {
			move(y,x,S[y][x]-'A',x);
		}
		FOR(y,N) cout<<S[y]<<endl;
		return ret;
		
	}
}

まとめ

うーん。