SRM575 Div2 Easy "TheSwapsDivTwo"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12499
訳
整数の配列がある。ここから2つのインデックスを選び、その値を入れ替える。
(その交換された要素は同じ値かもしれない)
一回だけ交換した後、何種類の配列が出来るかを返せ。
制約
2 <= 配列の要素数 <= 47
1 <= 配列の値 <= 47
考えた事
紙に数列を書きまくって法則を探る。
基本的には全てのインデックスの組み合わせ
つまり要素数をnとすると、 n-1 + n-2 +...+ 2 + 1でよい。
ただし、2つのインデックスの値が同じ場合、
元と同じ配列になるので、その数え上げを一回までに制限すればよさそう。
要素数が最大50ぐらいだし、スワップをシミュレートしてもおk
ソースコード
class TheSwapsDivTwo { public: int find(vector <int> seq){ int n = seq.size(); bool eq = false; int res = 0; for( int i = 0; i < n; i++ ){ for( int j = i + 1; j < n; j++ ){ if( seq[i] == seq[j] ){ if( eq ) continue; eq = true; } res++; } } return res; } };