cormoran's note


cormoran

競技プログラミング・電子工作・ロボットなどで遊びます



Recent Post




AOJ2022 Princess, a Cryptanalyst

AOJ2022 Princess, a Cryptanalyst - お姫様の暗号解読

再帰なしでbitDPするのは初めてだったみたい。

問題概要

N個の文字列が与えられる。

それら全てを部分文字列として含む文字列のうち、その長さが最小になるものを求めよ。長さが同じものが複数ある場合は辞書順最小のものを答えとする。

$1 <= N <= 10$

解法

bitDPする。

巡回セールスマン問題の始点に戻らないバージョンと同じだけど、昔書いたTPSのコードを探したら再帰で書いていたので今回はループで書いてみた。

今まで何も考えないままに for(i = 0; i < (1 << N); i++)ってなんなんだ…って思ってたけど、書き出してみたらいい感じにDPできることがわかった。(今更)

for(i = 0; i < (1 << N); i++) とすると下のようになる。

0 0 0 0 0 0 0 1 * 0 0 1 0 * 0 0 1 1 0 1 0 0 * 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 *

考えると当たり前だが、i番目までのビットで表せる全パターンが現れたあとで、i+1番目のビットが立つので、うまく部分問題を解いてから次の段に遷移できる。


#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

#define rep(i, j) for(int i=0; i < (int)(j); i++)
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) {
    for(T &a : v) is >> a; return is;
}

void set_min(string &s, const string &s1) {
    if(s == "") s = s1;
    if(s1.size() < s.size()) s = s1;
    else if(s1.size() == s.size()) s = min(s, s1);
}


string merge(const string &s1, const string &s2) {
    rep(i, s1.size()) {
        rep(j, s2.size()) {
            if(i + j < s1.size()) {
                if(s1[i + j] != s2[j]) goto FAIL;
            } else {
                return s1 + s2.substr(j);
            }
        }
        return s1;
  FAIL:;
    }
    return s1 + s2;
}

bool solve() {
    int N; cin >> N;
    if(N == 0) return false;
    vector<string> S(N); cin >> S;
    rep(i, S.size()) rep(j, i) {
        if(merge(S[j], S[i]) == S[j]) {
            S.erase(S.begin() + i);
            i--;
            break;
        }
    }
    N = S.size();
    vector<vector<string>> dp(1 << N, vector<string>(N)); // dp[使ったかどうかのbit列][最後に使った文字列の番号] = 最小文字列
    rep(i, N) dp[1 << i][i] = S[i];
    rep(stat, 1 << N) {
        rep(src, N) {
            if(not (stat & (1 << src))) continue;
            rep(dst, N) {
                if(stat & (1 << dst)) continue;
                set_min(dp[stat | (1 << dst)][dst], merge(dp[stat][src], S[dst]));                
            }
        }
    }
    string ans = "";
    rep(i, N) {
        set_min(ans, dp[(1 << N) - 1][i]);
    }
    cout << ans << endl;
    return true;
}

int main() {    
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(solve());
    return 0;
}


comments powered by Disqus