kmjp's blog

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

TopCoder SRM 575 Div2 Easy TheSwapsDivTwo

Div2も復習。
http://community.topcoder.com/stat?c=problem_statement&pm=12499

問題

数値配列が与えられる。
このうち2個の数値の位置を入れ替える場合、得られるユニークな数列が何通りあるか答える。

解法

数列の長さLは高々47なので、O(L^2)かかっても問題ないので全通りswapしてみればよい。
swapした結果をstringにしてsetに入れ、ユニークな数をカウントしてみた。

class TheSwapsDivTwo {
	public:
	int find(vector <int> sequence) {
		string s;
		int i,x,y;
		FOR(i,sequence.size()) s+='@'+sequence[i];
		
		set<string> m;
		FOR(x,s.size()) for(y=x+1;y<s.size();y++) {
			swap(s[x],s[y]);
			m.insert(s);
			swap(s[x],s[y]);
		}
		
		return m.size();
	}
}

まとめ

数値が小さいときはstringにした方が扱いがラクだな。
あまり配列を触っている意識がなくデータを扱える。

広告を非表示にする