読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ABC027 D - ロボット

競プロ 考察 DP

想定解賢いなあ…という感じ。

問題

D: ロボット - AtCoder Beginner Contest 027 | AtCoder

数直線の原点にロボットが置かれている。 はじめ、ロボットの幸福度は 0 である。

このロボットに命令列が与えられる。 命令列は次の 3 文字のみからなり、先頭から末尾まで順に実行される。

M : 正または負の好きな向きに、距離 1 だけ移動する。 + : 今の座標を x とすると、幸福度が +x だけ変化する。 - : 今の座標を x とすると、幸福度が −x だけ変化する。 命令列を実行し終えた後、 ロボットは原点に戻っていなければならない 。 命令列を実行している間、ロボットの座標および幸福度は負になり得る。

最終的な幸福度を最大化するようにロボットが移動したとき、最終的な幸福度を求めよ。

制約

命令列の長さ:  1 \leq S \leq 10^5

(部分点:  1 \leq S \leq 1000)

解法

部分点解法

制約が小さいのでDPで通る。「int dp[i番目までの命令を実行し][位置jにいるときの] = 最大の幸福度」とすればよい。 O(N^2)

static const int OFFSET = 1005;
static const int WIDTH = 2 * OFFSET + 1;
static const int MAX_N = 1000;
static const ll INF = 1e18;

string S;
ll dp[MAX_N + 1][WIDTH];
int N;

signed main() {
    cin >> S;
    N = S.size();

    rep(i, N) rep(j, WIDTH) dp[i][j] = -INF;
    dp[0][OFFSET] = 0;
    rep(i, N) {
        rep2(j, 1, WIDTH - 1) {
            if (S[i] == 'M') {
                dp[i+1][j] = max(dp[i][j-1], dp[i][j+1]);
            } else if (S[i] == '+' && S[i] != -INF) {
                dp[i+1][j] = dp[i][j] + (j - OFFSET);
            } else if (S[i] == '-' && S[i] != -INF) {
                dp[i+1][j] = dp[i][j] - (j - OFFSET);
            }
        }
    }

    cout << dp[N][OFFSET] << endl;
}

満点解法

各Mに>, <のどちらを割り当てればよいか考える。>, <の割り当て方が決まっていれば、+, -の左側にある<, >の個数を見れば+, -のときにいくつ幸福度が変化するかはわかる。これは見方を変えると、各>, <について、幸福度の変化量はその右側にある+, -の個数で決まるということである。そこでまず、各Mを>に割り当てたときの幸福度の変化量d(右にある+の個数と-の個数との差)を求める。幸福度を最大にしたいので、Mのうち、変化量が大きい方の半分、小さい方の半分を<にすればよい。よって求める答えは、dをソートし、後ろ半分の和と前半分の和の差を取ることで得られる。ソートの計算量が一番大きく O(|S| \log |S|)

signed main() {
    string S;
    cin >> S;
    int N;
    N = S.size();

    vi vec;
    int x = 0;
    rrep(i, N) {
        if (S[i] == 'M') {
            vec.emplace_back(x);
        } else {
            x += (S[i] == '+') ? 1 : -1;
        }
    }

    if (vec.empty()) {
        cout << 0 << endl;
        return 0;
    }

    sort(all(vec));
    int sm1 = 0;
    rep(i, vec.size() / 2) {
        sm1 += vec[i];
    }

    int sm2 = 0;
    rep2(i, vec.size() / 2, vec.size()) {
        sm2 += vec[i];
    }

    cout << sm2 - sm1 << endl;

}

とりあえずDPで解けたのは成長っぽい。