けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 303 D - Shift vs. CapsLock (茶色, 400 点)

AtCoder AtCoder400点 ABC-D 茶色diff DP テーマにストーリー性のある面白い問題 文字列 最小コスト ナップサックDP 現実世界の題材を扱った問題 DP状態:on/off 最適化問題

ランレングス圧縮をする問題に一瞬見えるかもしれない。でもそんなことしないで、最初から最後まで綺麗に DP で殴れる！

問題概要

文字 'a' と 'A' のみからなる長さ N の文字列 S が与えられる。

以下のキーボード操作を繰り返すことで、この文字列 S を画面に打ち込みたい。そのための最小コストを求めよ。

なお、CapsLock が ON の状態と OFF の状態とがあって、初期状態では OFF であるとする。

  • 操作 1 (a キーを押す)：コスト X
    • OFF のときは、文字 'a' が入力される
    • ON のときは、文字 'A' が入力される
  • 操作 2 (Shift + a キーを押す)：コスト Y
    • OFF のときは、文字 'A' が入力される
    • ON のときは、文字 'a' が入力される
  • 操作 3 (CapsLock キーを押す)：コスト Z
    • OFF のときは、ON になる
    • ON のときは、OFF になる

制約

  • 1 \le X, Y, Z \le 10^{9}
  • 1 \le N \le 3 \times 10^{5}

考えたこと

慣れてくると、この手の問題は条件反射で DP だと思えるようになる！！

しかし、慣れる前は色々考察してしまうと思う。たとえば、 X が Y よりも極端に小さいときは、'a' と 'A' の変わり目で CapsLock キーを押すといいんだろうなとか。

この考察に走ると、ランレングス圧縮したくなったりする。しかし、この考察の道は、無限の場合分けに苦しむことになる。頑張っても、頑張っても、恐ろしいコーナーケースがたくさん作れてしまう。

DP へ！

こういう時は DP だ。DP は元々は「全探索解法をメモ化して効率化したもの」とみなせるので、本質的には探索解法だ。恐ろしい場合分けも、探索し尽くしてしまう解法の前では驚異ではない。

次の配列 dp を用意しよう。ナップサック問題を解く DP などに慣れていれば、十分理解できると思う。

  • dp[i][0] ← 文字 S_{0}, S_{1}, \dots, S_{i-1} を打ち終えて、CapsLock が OFF であるような状態にするまでの最小コスト
  • dp[i][1] ← 文字 S_{0}, S_{1}, \dots, S_{i-1} を打ち終えて、CapsLock が ON であるような状態にするまでの最小コスト

DP の遷移を詰める部分も、ナップサック問題を解く DP がちゃんと理解できていれば難しくないと思う。計算量は O(N) となる。

なお、これ以降、DP 遷移を実現するのに関数 chmin() をたくさん用いる。 a と b とを比較して、 b の方が小さい場合は a を b に更新するものだ。更新が発生するときには true を返し、発生しないときは false を返す。

bool chmin(long long& a, long long b) { 
    if (a > b) { 
        a = b; 
        return true;
    } 
    return 0; 
}

初期条件

初期状態では OFF の状態なので、dp[0][0] = 0 と表せる

遷移

まず、CapsLock キーを押して ON / OFF を入れ替える部分は次のように記述できる。

chmin(dp[i][0], dp[i][1] + Z);
chmin(dp[i][1], dp[i][0] + Z);

その後、文字 S_{i} を打ちます。文字が 'a' であるか 'A' であるかに応じて次のように記述できます。

  • 文字 'a' を打つとき
chmin(dp[i+1][0], dp[i][0] + X);  // OFF 時
chmin(dp[i+1][1], dp[i][1] + Y);  // ON 時
  • 文字 'A' を打つとき
chmin(dp[i+1][0], dp[i][0] + Y);  // OFF 時
chmin(dp[i+1][1], dp[i][1] + X);  // ON 時

あとは、この遷移を素直に実装すれば OK！

コード

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    long long X, Y, Z;
    string S;
    cin >> X >> Y >> Z >> S;
    
    // 初期条件
    vector<vector<long long>> dp(S.size()+1, vector<long long>(2, INF));
    dp[0][0] = 0;
    
    // DP を回す
    for (int i = 0; i < S.size(); ++i) {
        // CapsLock を押す場合を試す
        chmin(dp[i][0], dp[i][1] + Z);
        chmin(dp[i][1], dp[i][0] + Z);
        
        // 'a' を押す
        if (S[i] == 'a') {
            chmin(dp[i+1][0], dp[i][0] + X);  // OFF 時
            chmin(dp[i+1][1], dp[i][1] + Y);  // ON 時
        } else {
            chmin(dp[i+1][0], dp[i][0] + Y);  // OFF 時
            chmin(dp[i+1][1], dp[i][1] + X);  // ON 時
        }
    }
    cout << min(dp[S.size()][0], dp[S.size()][1]) << endl;
}