TopCoder SRM 823 : Div1 Medium TigerMaster

エイヤで解いてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17397

問題

N点M辺の無向グラフが与えられる。ここでMは10N以上である。
各辺には重みが設定されている。

長さ20のパスで、重みが昇順となるものを1つ構築せよ。

解法

まず辺を重み順にソートする。
f(n,v) := n番目までの辺を見たとき、vを末尾とするパスのうち最長のもの
これをどん欲に管理しよう。
もしn番目の辺が点u,vをつなぐ場合、

• f(n,u) = longer(f(n-1,u), f(n-1,v) + [u])
• f(n,v) = longer(f(n-1,v), f(n-1,u) + [v])

となる。

全部で20N回パス長が長くなるタイミングがあるので、鳩ノ巣原理より、f(M,v)のうちいずれかのvでは長さが20以上のものがある。

pair<int,int> from[100][22];

class TigerMaster {
	public:
	vector <int> train(int N, int M, vector <int> X, vector <int> Y, vector <int> D) {
		vector<pair<int,int>> E;
		int i;
		FOR(i,M) {
			E.push_back({D[i],i});
		}
		MINUS(from);
		FOR(i,N) from[i][0]={0,0};
		
		int j;
		sort(ALL(E));
		FORR(e,E) {
			int i=e.second;
			int x=X[i],y=Y[i];
			for(j=19;j>=0;j--) {
				if(from[x][j].first>=0&&from[y][j+1].first==-1) {
					from[y][j+1]={i,x};
				}
				if(from[y][j].first>=0&&from[x][j+1].first==-1) {
					from[x][j+1]={i,y};
				}
			}
		}
		FOR(i,N) if(from[i][20].first>=0) {
			int cur=i,step=20;
			vector<int> R;
			while(step) {
				int a=from[cur][step].first;
				int b=from[cur][step].second;
				R.push_back(a);
				cur=b;
				step--;
			}
			R.push_back(cur);
			reverse(ALL(R));
			return R;
		}
		return {};
		
	}
}

まとめ

気づくまでだいぶ手間取った。