SRM631 Div1 Medium "CatsOnTheLineDiv1"

問題

TopCoder Statistics - Problem Statement

考えたこと

ぬこグループが取るべき行動は２通りある。

１つは一匹ずつ散らばること。(パターン１)

複数ポイントが0になるため理想的な動き方。ネックはこの動き方をするための条件が厳しいこと。ぬこの数だけ空きポイントが必要だし、時間が十分にないといけない。

もう１つは他グループと併合すること。(パターン２)

１つめの動きを諦めざるを得ないときは、下手に散らばないでグループ全体で行動した方がよい。そして複数ポイントを最小化するために、別のグループを探して併合できれば併合したい。元々2匹いたところが100匹になったとしても、全く問題ない。

左のグループから順に考察していくことにすると・・・

パターン１の動きができるならば、その時はなるべく左に寄りたい。こうすることで、次(１つ右)のグループのパターン１の動きをなるべくやり易くさせてあげられる。また、次のグループがパターン２の動きをするとしても、ぬこの数が単数になるため右に寄ることのメリットは全くない。

パターン２の動きをするときは、なるべく右に寄りたい。こうすることで、次のグループがパターン２で動く時に併合させやすくなる。次のグループがパターン１の動きをするときに邪魔になるかと思いきや、邪魔になるくらい近い(時間内にぶつかる事ができる)なら併合すりゃいいじゃんということで、右によることによるデメリットが全くない。

DPで、単数複数それぞれで最も右のぬこの位置を状態として持っておき、単数の時はなるべく左、複数の時はなるべく右になるようにして、更新していけばよい。

ソースコード

// dp[i][j][0] := 右端が単数で最も左
// dp[i][j][1] := 右端が複数で最も右
// i...グループのインデックス
// j...今までに複数ポイントが何個できてしまったか
int dp[1050][1050][2];

class CatsOnTheLineDiv1 {
public:

    int getNumber(vector <int> pos, vector <int> count, int time) {
        int n = pos.size();

        // x昇順
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (pos[j - 1] > pos[j]) {
                    int t = pos[j - 1];
                    pos[j - 1] = pos[j];
                    pos[j] = t;
                    t = count[j - 1];
                    count[j - 1] = count[j];
                    count[j] = t;
                }
            }
        }

        // dp初期化
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j][0] = INF_R;
                dp[i][j][1] = INF_L;
            }
        }
        dp[0][0][0] = INF_L;
        
        // dp更新
        for (int id = 0; id < n; id++) {
            for (int cnt = 0; cnt < n; cnt++) {
                // 単数
                if (dp[id][cnt][0] != INF_R) {
                    int r = dp[id][cnt][0];
                    // パターン１の動きをする
                    //- 左に伸ばせる数
                    int canLeft = min(time, pos[id] - r - 1);
                    //- 右に伸びるべき数
                    int needRight = count[id] - canLeft - 1;
                    if (needRight <= time) {
                        // 時間内にいけるなら動く
                        dp[id + 1][cnt][0] = min(dp[id + 1][cnt][0], pos[id] + needRight);
                    }
                    // パターン２の動きをする
                    //- なるべく右へ
                    dp[id + 1][cnt + 1][1] = max(dp[id + 1][cnt + 1][1], pos[id] + time);
                }

                // 複数
                if (dp[id][cnt][1] != INF_L) {
                    int r = dp[id][cnt][1];
                    // パターン１の動きをする
                    //- 左に伸ばせる数
                    int canLeft = min(time, pos[id] - r - 1);
                    //- 右に伸びるべき数
                    int needRight = count[id] - canLeft - 1;
                    if (needRight <= time) {
                        // 時間内にいけるなら動く
                        dp[id + 1][cnt][0] = min(dp[id + 1][cnt][0], pos[id] + needRight);
                    }
                    // パターン２の動きをする
                    //- 併合できるなら併合
                    if (pos[id] - time <= r) {
                        dp[id + 1][cnt][1] = max(dp[id + 1][cnt][1], r);
                    }
                    // なるべく右へ
                    dp[id + 1][cnt + 1][1] = max(dp[id + 1][cnt + 1][1], pos[id] + time);
                }

                
            }
        }

        // dp結果
        for (int i = 0; i <= n; i++) {
            if (dp[n][i][0] != INF_R) {
                return i;
            }
            if (dp[n][i][1] != INF_L) {
                return i;
            }
        }
        return n;
    }
};