ACM-ICPC 2010国内予選 E. 最強の呪文

ACM-ICPC

id:kusano_progさんに先に書かれてしまいましたが…。

E. 最強の呪文

解法

  • [現在の呪文の長さ][現在地] を使った拡張ダイクストラ
    • 文字列A, B, Cに対して、一般にmin(A+C, B+C) = min(A, B) + Cは成り立たない
    • が，AとBの長さが同じなら成り立つので文字列長ごとに管理する
  • エッジの文字列長が高々6なので，ループが無ければ文字列長は(6*ノード)数以下
  • 今回は最強の呪文が定まらない場合もあるので(12*ノード数)まで調べた
    • ループなしで作れる辞書順最小の文字列をsとする
    • ループありでsより辞書順が小さい文字列が作れると最強の呪文は定まらない
      • ループ部分の文字列をwとすると，uv > uwv > uwwv > … となるから
    • なので、ループありでsより辞書順で小さい文字列を作れるかを調べる必要がある
    • ループありでsより辞書順で小さい文字列があれば、倍くらい調べれば1つは見つかる
      • 辞書順を小さくするループのうち長さ(6*ノード数)以下のものがある…ハズ
      • いろいろ考えましたが、この辺の正当性は自信がないです
      • ジャッジデータには反例がありませんでしたが…
  • 以下のコードで行っている処理は以下の通り
    • 長さ(12*ノード数以下)ごとに拡張ダイクストラで辞書順最小の呪文を調べる
    • 作った呪文のうち辞書順最小のものを取りだす
    • 呪文を作った経路を調べてループの有無を判定し、答えを出力

7/6 8:24追記 (正当性の証明)

  • どうやら(6*ノード数)の倍の長さを調べておけば大丈夫そうです
    • 以下では次の証明を試みています。間違いがあったら教えていただけると嬉しいです
      • ループなしで作れる辞書順最小の文字列をsとする
      • ループありで作れるsより辞書順で小さい文字列が存在するとき、
      • そのような文字列のうち長さ(12*ノード数)以下のものが存在する
  • ループありでsより辞書順で小さく、かつsより長い文字列の集合をTとする
    • ループなしで辞書順最小の文字列sの長さは(6*ノード数)以下
    • 条件からTに属する文字列の先頭|s|文字の辞書順はsより小さい
  • Tに属する文字列のうち長さ(12*ノード数)以下のものが存在する
    • Tに属する文字列どれかを生成する過程を考える
    • 先頭|s|文字を生成したらループを経由せずにゴールに向かうとする
      • 実際には|s|〜|s|+5文字を生成したら
    • その結果できる文字列をtとすると、tはTに属する
      • tの条件からt < s
      • tがループを含まないとすると、sの条件に反する
  • tの長さを考えると、高々(|s|+5+ゴールまでにできる文字列長)
    • ループなしなら生成される文字列の長さは6*(ノード数-1)以下
    • 同じノードは2度通らないので通る枝の数は高々(ノード数-1)
  • よって、tの長さ ≦ (|s|+5+6*(ノード数-1)) ≦ 12*ノード数
  • 上で書いてる「ループの長さが(6*ノード数)以下」は、まだ自信ありません
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef vector< vector< pair<int, string> > > Graph;

class Node{
public:
    int pos; string str; int prev;
    Node(int pos, string str, int prev) : pos(pos), str(str), prev(prev) {}
    bool operator < (const Node &nd) const { return str > nd.str; }
};

int main(){
    int n, a, s, g;
	int prev[480][40];
	string str[480][40];
	while(cin >> n >> a >> s >> g, n){
		Graph graph(n);
		for(int i=0;i<a;i++){
			int x, y; string lab; cin >> x >> y >> lab;
			graph[x].push_back(make_pair(y,lab));
		}
		memset(prev, -1, sizeof(prev));
		for(int i=0;i<12*n;i++)
			for(int j=0;j<n;j++) str[i][j] = "";
		priority_queue<Node> qu; qu.push(Node(s, "", -2));
		while(!qu.empty()){
			Node nd = qu.top(); qu.pop();
			int pos = nd.pos, size = nd.str.size();
			if(prev[size][pos]!=-1) continue;
			prev[size][pos] = nd.prev;
			str[size][pos] = nd.str;
			for(int i=0;i<graph[pos].size();i++){
				int npos = graph[pos][i].first;
				if(size + graph[pos][i].second.size() >= 12*n) continue;
				string nstr = nd.str + graph[pos][i].second;
				if(str[nstr.size()][npos]==""||nstr<str[nstr.size()][npos]){
					str[nstr.size()][npos] = nstr;
					qu.push(Node(npos, nstr, size*n+pos));
				}
			}
		}
		int minpos = -1;
		string ans = "";
		for(int i=0;i<12*n;i++){
			if(str[i][g]=="") continue;
			if(ans == ""||ans > str[i][g]){
				ans = str[i][g];
				minpos = i;
			}
		}
		bool flag = (minpos != -1);
		bool visit[40];
		memset(visit, false, sizeof(visit));
		int cur = minpos*n+g;
		while(flag&&cur!=-2){
			if(visit[cur%n]) flag = false;
			visit[cur%n] = true;
			cur = prev[cur/n][cur%n];
		}
		cout << (flag ? ans : "NO") << endl;
	}
}