torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Google Code Jam 2014, Round 1B, A : The Repeater

問題概要

 N 個の文字列が与えられる。この文字列集合に対し、次の操作ができる。

  • 一つの文字列 s を選んで、s 中のある文字 c を、連続する二つの c に置き換える
  • 一つの文字列 s を選んで、s 中である文字 c が連続する部分を、一文字の c に置き換える

 文字列を全て等しくするために必要な操作回数の最小値を求めよ。不可能な場合はその旨を示せ。

解法

 まず、問題設定上の制約から、重複を除いて文字が出現する順序は変更できません。従って、全ての文字列について文字の重複を排除したもの同士が一致しなければ目標を達成できません。全ての文字列の文字の並びが等しいなら、何回かの操作により目標を達成できます。
 目標を達成できる場合の最適解について考えます。先程の考察より、重複を除いて出現する文字の順番は全ての文字列について一致しています。従って問題は、「各 i について、i 番目に出現する文字の個数を何個にするのが最適か」と言い換えられます。これは各 i について独立なので、更に部分問題 「i 番目の文字をいくつにするのが最適か」を解ければ全体を解けます。
 各文字列について i 番目の文字が連続している個数を並べた列を a とすると、i 番目の文字に関して最適な個数は [ min( a ), max( a ) ] 内の整数になります。この区間内にある整数 x について、\sum | x - a_i| が最小となるものが、i 番目の文字の個数として最適な値です。
 あとは各 i について最適な個数を求めて総和を取れば全体の最適解が求まります。

コード ( C++ )

using VI = vector<int>;
using VVI = vector<VI>;
using VS = vector<string>;
template < typename T = int > using LIM = numeric_limits<T>;
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

bool possible( VS ss )
{
	FOR( s, ss )
	{
		s.erase( unique( ALL( s ) ), s.end() );
	}

	return set<string>( ALL( ss ) ).size() == 1u;
}

VI convert( const string &s )
{
	const int L = s.size();

	VI res;
	REP( i, 0, L )
	{
		int j;
		for ( j = i; j < L && s[i] == s[j]; ++j );
		res.PB( j - i );
		i = j - 1;
	}

	return res;
}

int solve()
{
	int n;
	cin >> n;

	VS ss( n );
	FOR( s, ss )
	{
		cin >> s;
	}

	if ( !possible( ss ) )
	{
		return -1;
	}

	VVI nums( n );
	REP( i, 0, n )
	{
		nums[i] = convert( ss[i] );
	}

	int res = 0;
	REP( i, 0, nums[0].size() )
	{
		VI cnts( n );
		REP( j, 0, n )
		{
			cnts[j] = nums[j][i];
		}

		sort( ALL( cnts ) );

		int minimal = LIM<>::max();
		REP( t, cnts[0], cnts.back() + 1 )
		{
			int tmp = 0;
			FOR( c, cnts )
			{
				tmp += abs( c - t );
			}
			minimal = min( minimal, tmp );
		}

		res += minimal;
	}

	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int t;
	cin >> t;

	REP( i, 0, t )
	{
		const int res = solve();

		cout << "Case #" << i + 1 << ": " << ( res == -1 ? "Fegla Won" : toString( res ) ) << endl;
	}

	return 0;
}

コード ( Haskell )

readInt = ( readLn :: IO Int )

main = do
	t <- readInt
	results <- replicateM t solve

	mapM_ ( \( n, r ) -> printf "Case #%d: %s\n" n r ) $ zip ( [ 1 .. ] :: [Int] ) results

solve = do
	n <- readInt
	ss <- replicateM n getLine

	return $ if valid ss then solve' ss else "Fegla Won"

valid = ( == 1 ) . length . group . map convert
	where
		convert = map head . group

solve' = show . sum . map solve'' . transpose . map convert
	where
		convert = map length . group
		solve'' as = minimum $ [ sum $ map ( abs . ( x - ) ) as | x <- [ minimum as .. maximum as ] ]