torus711 のアレ

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

TopCoder SRM 538, Division 2, Level 1 : SwappingDigits

概要

数字を表す文字列が与えられる。
異なる二つのインデックスを選び、その二桁を入れ替える操作を高々一回できる。
作ることのできる最小の数を求めよ。
ただし、Leading Zero をもつものは認められない。

解法

可能なスワップを全て試し、最も小さくなるものを求めます。
Leading Zero を除外するのを忘れないようにしましょう。

コード

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

class SwappingDigits
{
public:
	string minNumber( string num )
	{
		const int N = num.size();
		string res = num;

		REP( i, 0, N )
		{
			REP( j, i + 1, N )
			{
				string tmp( num );
				swap( tmp[i], tmp[j] );
				if ( tmp[0] == '0' )
				{
					continue;
				}
				res = min( res, tmp );
			}
		}

		return res;
	}
};