WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};