TopCoder SRM 602, Division 1, Level 1 : TypoCoderDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12924&rd=15820

概要

　あるコンテストでのレーティングシステムでは、2200 以上を brown coder 、2200 未満を ciel coder と呼ぶ。ねこの Lower は現状 ciel coder であり、今年の終わりでのレーティングは X である。
　来年にも何回かのコンテストがある。それぞれのコンテストに於いて、Lower は真面目にやってレートを上げるか、わざと負けてレートを下げるかを選ぶことができる。i 番目のコンテストを真面目にやるとレートが D[ i ] 上がり、負けると D[ i ] 下がる（ 0 未満にはならない）。
　Lower は ciel coder でいることが好きなので、二回以上続けて brown coder ではいたくない。すなわち、brown coder になった次の回では必ず ciel coder に戻る。
　このコンテストでは、一年間に最も多く色（ brown or ciel ) が変わった参加者に特別賞を出している。Lower が最高で何回色を変えることができるか求めよ。

解法

　それぞれのコンテストについて勝つか負けるかを順番に決めていくとします。このとき、考慮したコンテストの数とその時点でのレーティングが等しければ同じ状態と見做すことができ、最も解が良くなる状態だけ考慮すればよくなります。しかし、そのまま DP にしようとするとレーティングの変動幅がとても大きいので DP テーブルがメモリに収まりません。
　ところが、レーティングが 2200 以上のとき、Lower は必ず ciel に戻ってこなければなりません。ということは、brown になるような選択の次に続く選択は確定しています。つまり、次回コンテストで負けることで ciel に戻って来れるならば 勝つ→負ける という選択が可能で、そうでないときはそのコンテストで勝ってはいけません。ciel で居続ける分には制約が無いので、負けることはいつでも可能です。このことを踏まえると、レーティング 2200 以上では選択の余地が無いので、状態として保持する必要は無く、勝つ→負ける という一連の選択を一回の操作として考えることができます。そうすると保持する状態のレーティングは 2200 未満になるので、次のような DP を考えることができます。

• dp[ i 個考慮 ][ レーティングが j ] := 色が変わった回数

　dp[ 0 ][ X ] を 0 で初期化し、それ以外は -INF で初期化します。dp[ i ][ j ] からの状態遷移は次のようになります（ j の次元は 0 <= j < 2200 でクリッピングする）。

• dp[ i + 1 ][ j - D[ i ] ] を dp[ i ][ j ] で更新（負ける場合）
• dp[ i + 1 ][ j + D[ i ] ] を dp[ i ][ j ] で更新（勝つが ciel のままでいる場合）
• dp[ i + 2 ][ j + D[ i ] - D[ i + 1 ] を dp[ i ][ j ] + 2 で更新（今回勝って brow になり、次で負けて ciel に戻る場合）

さらに、一番最後のコンテストだけは brown に留まっても良いので、その遷移も加えます。このときに限り、レーティング 2200 として扱うと楽に書けます。

• dp[ i + 1 ][ 2200 ] を dp[ i ][ j ] + 1 で更新

　計算が終わったあと、dp[ N ] の最大値が答えです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

const int INF = INT_MAX / 2;

class TypoCoderDiv1
{
public:
	int getmax( vector <int> D, int X )
	{
		const int N = D.size();

		VVI dp( N + 1, VI( 2201, -INF ) );
		dp[0][X] = 0;

		REP( i, 0, N )
		{
			REP( j, 0, 2200 )
			{
				{ // lose
					const int r = max( 0, j - D[i] );
					dp[ i + 1 ][r] = max( dp[ i + 1 ][r], dp[i][j] );
				}
				if ( j + D[i] < 2200 )
				{ // win and stay ciel
					dp[ i + 1 ][ j + D[i] ] = max( dp[ i + 1 ][ j + D[i] ], dp[i][j] );
				}
				if ( i + 1 < N && 2200 <= j + D[i] && j + D[i] - D[ i + 1 ] < 2200 )
				{ // win at NOT last and back to ciel
					const int r = max( 0, j + D[i] - D[ i + 1 ] );
					dp[ i + 2 ][r] = max( dp[ i + 2 ][r], dp[i][j] + 2 );
				}
				if ( i + 1 == N && 2200 <= j+ D[i] )
				{ // win at last
					dp[ i + 1 ][ 2200 ] = max( dp[ i + 1 ][ 2200 ], dp[i][j] + 1 );
				}
			}
		}

		return *max_element( ALL( dp.back() ) );
	}
};