AOJ 1362 Do Geese See God?

AOJ 競プロ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362

問題概要

文字列 S を部分列（部分文字列ではない）に持つような最小の長さの回文の集合の中で，辞書順 k 番目のものを求めよ．
・制約
1 <= |S| <= 2000
1 <= k <= 10^18

解法

区間DPをやります．作れる文字列の数 + 辞書順最小構築が必要なので，DPかなあという推測は立つと思います．

まず，問題を2つの部分に分けます．

  1. 最小の文字列の長さを求める
  2. 作ることのできる回文のパターン数

最小の文字列の長さは，以下の dp で求められます．
len[i][j] := S[i, j] を部分列にもつような回文の最小長さ
右端と左端が一致していない場合，最小の回文を構成するのであれば，そのどちらかを挿入することになります．一致していれば，明らかに挿入する必要はありません．これを元に漸化式を立てます．

作ることのできる回文のパターン数も，以下の dp で求められます．
dp[i][j] := S[i, j] を部分列にもつような最小長さの回文の種類数
この計算には len[i][j] を用います．S[i] と S[j] が等しい場合，最小長さにするので dp[i + 1][j - 1] が答えです．S[i] と S[j] が異なる場合，S[i] と S[j] のどちらかを挿入することになりますが，len[i + 1][j] と len[i][j - 1] の値の大小によって，どちらを挿入するべきか判定できます．（もちろん小さくなる方を挿入する．）
挿入するほうが決まれば，そのときの dp[i + 1][j] または dp[i][j - 1] の値を加算します．

dp[0][n - 1] < K なら答えはありません．

最後に構築パートですが，これはいつものやつなので雑に書きます．
S[l] == S[r] ならその文字を使うことが確定します．
S[l] != S[r] なら，短くなるほうを選びます．どちらをえらんでも同じ長さを達成できるなら小さい方を使いたいですが，K を超えないギリギリに向かうように選ぶ必要もあります．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;
 
ll add(ll& a, ll b) {
    return a = min(a + b, INFLL * 2);
}
 
int main() {
    string S;
    ll K;
    cin >> S >> K;
    int const n = S.size();
    vector<vector<int>> len(n, vector<int>(n, INF));
    for(int i = n - 1; i >= 0; --i) {
        len[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                len[i][j] = (i + 1 == j ? 2 : len[i + 1][j - 1] + 2);
            }
            len[i][j] = min(len[i][j], min(len[i + 1][j], len[i][j - 1]) + 2);
        }
    }
    vector<vector<ll>> dp(n, vector<ll>(n));
    for(int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                add(dp[i][j], (i + 1 == j ? 1 : dp[i + 1][j - 1]));
            } else {
                int min_len = min(len[i + 1][j], len[i][j - 1]);
                if(len[i + 1][j] == min_len) {
                    add(dp[i][j], dp[i + 1][j]);
                }
                if(len[i][j - 1] == min_len) {
                    add(dp[i][j], dp[i][j - 1]);
                }
            }
        }
    }
 
    if(dp[0][n - 1] < K) {
        cout << "NONE" << endl;
        return 0;
    }
 
    ll t = 1;
    string l_ans;
    int l = 0, r = n - 1;
    while(l < r) {
        if(S[l] == S[r]) {
            l_ans += S[l++];
            r--;
        } else {
            if(len[l + 1][r] < len[l][r - 1]) {
                l_ans += S[l++];
            } else if(len[l + 1][r] > len[l][r - 1]) {
                l_ans += S[r--];
            } else {
                ll t2 = t + (S[l] < S[r] ? dp[l + 1][r] : dp[l][r - 1]);
                if(t2 > K && S[l] < S[r] || t2 <= K && S[l] > S[r]) {
                    l_ans += S[l++];
                } else {
                    l_ans += S[r--];
                }
                if(t2 <= K) {
                    t = t2;
                }
            }
        }
    }
    auto r_ans = l_ans;
    reverse(begin(r_ans), end(r_ans));
    if(l == r) {
        l_ans += S[l];
    }
    cout << l_ans + r_ans << endl;
}

感想

こういう問題は苦手．