AOJ 1169. 最強の呪文

問題文

問題文

考えたこと(箇条書き)

start --(S1, S2) --> v --T--> goalと行く場合を考える（vは注目した1頂点. S1,S2,Tは文字列）。
まず、S1 < S2 ⇒ S1 + T < S2 + Tは偽なので、各頂点で辞書順最小を作る方法では「最強の呪文」を作ることができない。（反例：S1 = "a", S2 = "ab", T = "c")
しかし|S1| = |S2|なら上の命題が真になるので、dp[文字数][頂点] = 辞書順最小とすることができる。（今いる頂点と文字数が同じなら, 辞書順最小が良い。）
よって、このDPをする。

最強の呪文が定まる場合、最強の呪文がなす経路はパス（同じ頂点を2度通らない）になることが示せる。(1つのサイクルを含む場合について証明すればよい）
よって, 最強の呪文（dp[--][goal]）がサイクルを1つ以上含んでしまった時点で"NO"が確定する。
サイクルを1つ以上含むことで, パスの場合よりも強い呪文を作れるとすると、同じサイクルをn個含む「パスの場合よりも強い呪文」が任意の正整数nについて存在する。すなわち、
パスの場合よりも強い呪文が存在する ⇔ 経路長n未満の場合よりも強い, 経路長n以上2n以下の呪文が存在する
が成り立つ。よって、経路長2n以下まで, すなわち文字数12n以下まで調べれば十分である。
(もう少し考えると、パスの場合よりも強い呪文が存在する ⇔ 文字数6n未満の場合よりも強い, 文字数6n以上12n以下の呪文が存在する. も成り立つことが分かる)

はまった点

・dp[頂点] = 辞書順最小, を立てようとして嵌った。
・dp[枝を通った回数][頂点][長さ] = 辞書順最小, としてMLEした。
・dp[今までの文字数][今いる頂点] = 辞書順最小, としたが, 長さ昇順にループを回さないせいでTLEした。
・文字数 ≦ 6 * nまでしか考えていなくて、WAした。

…考察を詰める集中力がほしい。

ソースコード

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

int n, m, s, g;
vector<int> et[40];
vector<string> ec[40];
string dp[481][40];

int main() {
    int i, j, k;
    
    while (cin >> n >> m >> s >> g) {
        if (!n) break;
        for (i = 0; i < n; i++) { et[i].clear(); ec[i].clear(); }
        for (i = 0; i <= 12 * n; i++) { for (j = 0; j < n; j++) { dp[i][j] = "{"; } }
        for (i = 0; i < m; i++) {
            int a, b; string spell;
            cin >> a >> b >> spell;
            et[a].push_back(b);
            ec[a].push_back(spell);
        }
        
        dp[0][s] = "";
        for (i = 0; i < 12 * n; i++) {
            for (j = 0; j < n; j++) {
                for (k = 0; k < et[j].size(); k++) {
                    int v = et[j][k];
                    int len = ec[j][k].length();
                    if (i + len > 12 * n) continue;
                    dp[i + len][v] = min(dp[i + len][v], dp[i][j] + ec[j][k]);
                }
            }
        }
        
        int id = 0;
        for (i = 1; i <= 12 * n; i++) {
            if (dp[id][g] > dp[i][g]) id = i;
        }
        if (id >= 6 * n || dp[id][g] == "{") { cout << "NO" << endl; }
        else { cout << dp[id][g] << endl; }
    }
    return 0;
}

感想

複雑な問題設定だと思っていたが、いざ実装してみるととても簡潔に書けたので、良問だなあと思った。
発想というよりは、典型テク（知識, 発想・証明法）を上手く使いこなす系の問題な印象。