torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 575, Division 2, Level 1 : TheSwapsDivTwo

概要

整数列が与えられる。
ランダムに二つの異なるインデックスを選んで、その二つの数字を交換する操作を一回する。
作られる数列の総数を求めよ。

解法

実際に交換後の数列を生成して、その総数を数えます。
集合( C++ では set )を用いることで重複なく数えられます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class TheSwapsDivTwo
{
public:
	int find( vector <int> sequence )
	{
		const int N = sequence.size();
		set<VI> res;
		
		REP( i, 0, N )
		{
			REP( j, i + 1, N )
			{
				VI tmp( sequence );
				swap( tmp[i], tmp[j] );
				res.insert( tmp );
			}
		}
		return res.size();
	}
};