WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM602 Div1 Easy "TypoCoderDiv1"

問題

TopCoder Statistics - Problem Statement

TypeCoderはTopCoderに似たプログラミングコンテストである。TypeCoderもまたレーティングシステムを採用している。TypoCoderにはbrown coderとciel coderの2つの種類がある。brown coderはレーティングが2200以上のコーダーをいう。ciel coderはレーティングが2200に満たないコーダーをいう。

猫のロワーはTypoCoderのコーダーである。彼は現在ciel coderである。彼のレーティングは今年はXで終えた。

来年、いくつかのコンテストが開催される。各コンテストでロワーはベストを尽くすか、わざと負けるか選択することができる。i回目のコンテスト(0-base)の重要さはD[i]である。もしロワーがi回目のコンテストでベストを尽くせば、彼のレーティングはD[i]上がる。もしわざと負ければ、彼のレーティングはD[i]下がる。ただし、0を下回ることはない。正確には、彼のレーティングはmin(D[i],コンテストを受けたときのレーティング)だけ下がる。

ロワーはciel coderであることに誇りを持っている。よって、彼は2回続けてbrown coderになることは我慢ならなかった。つまり、彼がbrown coderになる度に次のコンテストの後で再びciel coderになる必要がある(次回コンテストがあれば)。

TypoCoderは1年間で最も色が変わったコーダーに対し、"カメレオンコーダー・オブ・ザ・イヤー"として表彰する。

あなたはint[] Dとint Xが与えられる。ロワーが来年、最大で何回色を変えられるかを返せ。

制約

1 <= コンテストの回数 <= 50
0 <= D[i] <= 10^9
0 <= X <= 2199



考えたこと

うーむ・・D[i]が最大10^9とな・・・

DPっぽいが、レーティングを状態として持つわけにいかんか←思考の罠
ここは何回目のコンテストで、何回色が変わったときの、レーティングの最大最小を持つ・・・とか?

・・・

だめだ、できね・・

・・・

あ、これ連続でbrown coderになれないから、色が2回一気に変わると考えれば、レーティングは0~2199まで持てばよさそうだ!

dp[i][j] := i回目のコンテスト開始時で、レーティングがjだったときの、最大の色変化数。

初期化はdp[0][X] = 0 (他は-1)
更新は
☆わざと負ける
⇒レーティングダウン

☆最後のコンテストの場合
⇒ベストを尽くして2200超えるようなら+1

☆ベストを尽くしても2200を超えない場合
⇒レーティングアップ

☆ベストを尽くしたら2200を超えて、かつ次のコンテストで2200を下回る場合
⇒2回分一気に計算して、+2

結果はdp[コンテストの回数][j]の最大値


int dp[55][2250];

class TypoCoderDiv1 {

    public:

    int getmax(vector <int> D, int X) {
        int N = D.size();
        
        memset(dp, -1, sizeof(dp));

        // dp初期化
        dp[0][X] = 0;

        // dp更新
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 2200; j++) {
                if (dp[i][j] == -1) continue;
                // lose
                int nj = max(0, j - D[i]);
                dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j]);

                // best
                if (i == N - 1) {
                    // last
                    if (j + D[i] >= 2200) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);
                }
                else if (j + D[i] < 2200){
                    // rate up
                    nj = j + D[i];
                    dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j]);
                }
                else {
                    nj = max(0, j + D[i] - D[i + 1]);
                    // +2
                    if (nj < 2200) dp[i + 2][nj] = max(dp[i + 2][nj], dp[i][j] + 2);
                }
            }
        }

        // 結果集計
        int res = 0;
        for (int i = 0; i < 2200; i++) {
            res = max(res, dp[N][i]);
        }
        return res;
    }
};