TopCoder SRM 602 Div1 Easy TypoCoderDiv1 [1人競技プログラミング Advent Calendar 2016 3日目]

この記事は1人競技プログラミング Advent Calendar 2016 3日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

TypoCoderというコンテストがあり、レーティング2200以上がbrown coder、2200未満がciel coderである。
Cat Lowerの現在のレーティングXとコンテスト毎のレーティング変動配列Dが与えられる。

i番目のコンテストでベストを尽くした場合はD[i]分レーティングが上がる。
i番目のコンテストで何もしなかった場合はD[i]分レーティングが下がる。0以下にはならない。

Cat Lowerはciel coderが好きなので、i番目のコンテストでbrown coderになった際にi+1番目のコンテストではciel coderに戻らなければならない。
最大でbrown coderとciel coderの入れ替わる事が出来る回数は何回かを答えよ。

解いた方法：
DP。dp[ 終了したコンテスト ][ 現在のレート ] = 変動回数 でやりました。
遷移する際に、必ずi+1番目では元のciel coderに戻らなければならないという条件があるので、2つ先のコンテストではレートがciel coderの取り得る値になっている。
その為、オーダーがO(len(D)*2200)回程度にまで落ちて間に合う。

vectorのsizeと負の数の比較でfalseを返しハマっていた…。泣きたい。 とりあえず遅すぎたけどWAは出さずに一発ACは達成。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int dp[51][2201];

class TypoCoderDiv1 {
    public:
    vector<int> D;
    int X;
    int getmax(vector<int> _D, int _XX) {
        D = _D, X = _XX;

        REP(i, 51) REP(j, 2201) dp[i][j] = -1;
        dp[0][X] = 0;

        REP(i, D.size()){
            REP(j, 2200){
                if(dp[i][j] == -1) continue;

                if(j + D[i] >= 2200){
                    if( i-2 < (int)D.size() && ((j + D[i] - D[i+1]) < 2200)){
                        dp[i+2][max(0, j + D[i] - D[i+1])] = max(dp[i][j] + 2, dp[i+2][max(0, j + D[i] - D[i+1])]);
                    }

                    if( i+1 == D.size() ){
                        dp[i+1][2200] = max(dp[i][j] + 1, dp[i+1][2200]);
                    }
                }else{
                    dp[i+1][j + D[i]] = max(dp[i][j], dp[i+1][j+D[i]]);
                }

                if(j - D[i] > 0){
                    dp[i+1][ j - D[i] ] = max(dp[i][j], dp[i+1][j-D[i]]);
                }else{
                    dp[i+1][0] = max(dp[i][j], dp[i+1][0]);
                }
            }
        }


        int ans = 0;
        REP(i, 2201){
            ans = max(ans, dp[D.size()][i]);
        }

        return ans;
    }
};