第3回 ドワンゴからの挑戦状 本選 A - 計算ドリル

http://dwacon2017-honsen.contest.atcoder.jp/tasks/dwango2017final_a

問題概要

0~9の数字と+, -の演算子のみからなる文字列Sが与えられる。この文字列を逆ポーランド記法とみなして計算を行ったときの最終的な計算結果をこの文字列の値とする。ただしこのとき文字列中に最初に含まれている0~9の文字は必ず一桁の数字とみなす。文字列SをK文字まで書き換えたとき、正しい逆ポーランド記法の式にすることができるかを判定せよ。またできるならば書き換えによって得られる最大の値を求めよ。

1 <= |S| <= 52, 0 <= K <= |S|

解法

この問題の制限の中での逆ポーランド記法は、以下のような文脈自由文法として表すことができる。

  • <数> ::= ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’
  • <演算子> ::= ‘+’ | ‘-’
  • <数> ::= <数><数><演算子>

この定義に従えば、この問題はある区間を<数><数><演算子>の3つの区間に区切って再帰的に最大値を求めていく問題と考えることができる。つまり以下のようなDPで解くことができる。

dp(i, j, k) = i文字目からj文字目までの区間をひとつの<数>とみなしたとき、k文字まで書き換えて得られる最大の値(と最小の値)

DPの遷移を考えると、区間i~jの区切りを全部試すのにO(|S|), 区間にkをいくつ割り振るかでもO(|S|)かかるので、状態数のO(|S|^3)と合わせて結局O(|S|^5)となる。525≒4*108で結構不安になるが、実際には区間がどんどん短くなっていくため定数倍はだいぶ軽い。

細かい話として、演算子にはマイナスもあるのでDPでは最小の値も保持しておく必要がある(演算子がマイナスの場合、例えば最大値-最小値が最大になりうる)。また「正しいポーランド記法にできない」を表すのにも特別な値を割り当てるなどの処理が必要。

感想

DPを思いつくのが大変だったし、実装はもっと大変だった。こういう細かい部分の実装がめんどくさい問題ってAtcoderだと珍しい印象。

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
int INF = 1 << 29;
 
bool isDigit(char c) {
    return c - '0' >= 0 && c - '9' <= 9;
}
 
void main() {
    auto K = readln.chomp.to!int;
    auto S = readln.chomp;
    auto N = S.length.to!int;
 
    auto mem = new Tuple!(int, int)[][][](N, N, K + 1); // (min, max)
    foreach (i; 0..N) foreach (j; 0..N) fill(mem[i][j], tuple(INF, INF));
    
    Tuple!(int, int) dfs(int l, int r, int k) {
        if (mem[l][r][k][0] != INF) return mem[l][r][k];
 
        int L = r - l + 1;
        
        if (L % 2 == 0) {
            return tuple(-INF, -INF);
        } else if (L == 1) {
            if (k > 0) return tuple(0, 9);
            else if (S[l].isDigit) return tuple(S[l] - '0', S[l] - '0');
            else return tuple(-INF, -INF);
        } else {
            if (k == 0 && S[r].isDigit) return tuple(-INF, -INF);
            int mn = INF;
            int mx = -INF;
            foreach (kk; max(0, k-1)..k+1) {
                char[] op;
                if (kk == k) {
                    if (S[r] == '+') op = ['+'];
                    else if (S[r] == '-') op = ['-'];
                    else continue;
                } else {
                    op = ['+', '-'];
                }
 
                for (int i = l; i < r; i += 2) {
                    foreach (j; 0..kk+1) {
                        auto t1 = dfs(l, i, j);
                        auto t2 = dfs(i + 1, r - 1, kk - j);
                        if (t1[0] == -INF || t2[0] == -INF) continue;
                        foreach (opp; op) {
                            if (opp == '+') {
                                mn = min(mn, t1[0] + t2[0]);
                                mx = max(mx, t1[1] + t2[1]);
                            } else {
                                mn = min(mn, t1[0] - t2[1]);
                                mx = max(mx, t1[1] - t2[0]);
                            }
                        }
                    }
                }
            }
 
            mem[l][r][k] = mn == INF ? tuple(-INF, -INF) : tuple(mn, mx);
            return mem[l][r][k];
        }
    }
 
    auto ans = dfs(0, N - 1, K);
    if (ans[0] == -INF) writeln("NG");
    else {
        writeln("OK");
        writeln(ans[1]);
    }
}