Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-02-02SRM496 Div1

SRM496 Div1 950 YetAnotherHamiltonianPath

| 23:53 | SRM496 Div1 950 YetAnotherHamiltonianPath - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM496 Div1 950 YetAnotherHamiltonianPath - SRM diary(Sigmar) SRM496 Div1 950 YetAnotherHamiltonianPath - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

950だしちょっと読んでみた

意外とHardにしてはストレートフォワードな感じ

まず、コストはX^2+Y^2-LCP(X,Y)^2だが、どんな順番で訪問しても、ノードの入力時及び出力時にX^2のコストがかかるため、

LCP(X,Y)^2を最大化することだけを考えれば良い

少し制約を緩くして、始点と終点を自由に選べるとすると、再帰的にプレフィクスが一致するところをまとめればいい

例えば最初の文字がaのものをまとめ、更にその中で2文字目がbのものをまとめ・・といった感じ

これを実現するには実は単にソートして辞書順に訪れればOK

さて始点と終点が定められると、どうすれば良いのかというのが問題

色々試してみると比較的すぐに規則性が分かるが、始点と終点の共通プレフィクスをpref、全ノードの共通プレフィクスをprefallとすると、pref^2-prefall^2だけ全体のLCPが小さくなることが分かる

ということで後は計算するだけ

なんですが、プラクティスではpref^2-prefall^2の部分を勘違いして計算ミスで1WAしてしまった・・・


ソースコード

以下はプラクティスで通したコードです

class YetAnotherHamiltonianPath {
public:
	int leastCost(vector <string> label) {
		ll res=0;

		int n=label.size();

		res+=label[0].size()*label[0].size()+label[1].size()*label[1].size();
		for(int i=2; i<n; i++) {
			res+=label[i].size()*label[i].size()*2;
		}

		string pref01;
		for(int k=0; k<(int)min(label[0].size(), label[1].size()); k++) {
			if(label[0][k]==label[1][k]) pref01.push_back(label[0][k]);
			else break;
		}
		int prefall=pref01.size();
		for(int i=2; i<n; i++) {
			int tprefall=0;
			for(int k=0; k<(int)min(pref01.size(), label[i].size()); k++) {
				if(pref01[k]==label[i][k]) tprefall++;
				else break;
			}
			prefall=min(prefall, tprefall);
		}
		res+=pref01.size()*pref01.size()-prefall*prefall;

		sort(label.begin(), label.end());
		for(int i=1; i<n; i++) {
			int pref=0;
			for(int k=0; k<(int)min(label[i-1].size(), label[i].size()); k++) {
				if(label[i-1][k]==label[i][k]) pref++;
				else break;
			}
			res-=pref*pref;
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110202