torus711 のアレ

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

TopCoder SRM 596, Division 2, Level 2 : ColorfulRoad

概要

一直線上の道があり、道は N 個の部分に分かれている。
各部分は左端から 0, 1, 2, ... と番号付けられる。
各部分には色がついていて、色は 'R', 'G', 'B' の三種類である。
位置 0 の色は 'R' である。

きつねは最初位置 0 にいて、位置 N - 1 まで移動したい。
移動はいくつかの step の連続となる。
距離 d の step では、コスト d * d をかけて、d 個右の部分に移動する。
また、'R' -> 'G' -> 'B' -> 'R' -> ... という順序で色を踏みたい。
位置 N - 1 に移動するために必要なコストの最小値を求めよ。
移動が不可能な場合は -1 で示せ。

解法

深く考えずに DP しました。
 dp[ 位置 ] := 到達するための最小コスト
です。
各位置からは可能な step を全て試します。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define MP( a, b ) make_pair( ( a ), ( b ) )

const int INF = INT_MAX / 2;
map<char,char> nexts = { MP( 'R', 'G' ), MP( 'G', 'B' ), MP( 'B', 'R' ) };

class ColorfulRoad
{
public:
	int getMin( string road )
	{
		const int N = road.size();

		VI dp( N, INF );
		dp[0] = 0;

		REP( i, 0, N - 1 )
		{
			REP( j, i + 1, N )
			{
				if ( road[j] == nexts[ road[i] ] )
				{
					const int d = j - i;
					dp[j] = min( dp[j], dp[i] + d * d );
				}
			}
		}

		return dp.back() == INF ? -1 : dp.back();
	}
};