kojingharangの日記

SRM 630 Div1 250 Egalitarianism3

13:50 |

• 木と各辺の距離が与えられる。集合に属するノード間の距離がすべて同じになるような最大集合のサイズを計算せよ。
• 1≦|ノード数|≦50, 1≦距離≦1000

• 1-2-3 として, 1と3は集合になりうるけど距離≧1なので 2 がある限り 1,2,3 はだめだな
• 2を中心とする感じか
• 必ず中心がありそうだ
• 中心からの距離 r なものを集めるか→無向グラフのdfsを書き始める →r なもの同士が2rじゃないとだめだった
• ていうかn≦50だからWFでいいじゃん (久しぶりに出たらやぼったいことをしてしまった)
• submit
• 中心があるのは答えが 3 以上になるときで、n≧2なら常に最低 2 になるんだった→再提出（やぼったい）

• Failed system test

• (あとで)
• 2r のチェックが甘かった。各頂点について自分 + 距離が2rになる頂点数の最大値を k としてたが、うまくずれてて実際のサイズはもっと小さいという場合があり得る。
• 追加しようとするたびに集合に加えていいか全部とチェックするようにした
• 中心ノードから距離 r なクリークは複数通りあるんじゃないか？と思ったが結局1通りに定まるので条件を満たすものは貪欲に追加して良い。

• 今回 "Egalitarianism3" だったけど、"Egalitarianism" はSRM584 で出題されていたようだ。(懐かしい)
• https://topcoder-g-hatena-ne-jp.jag-icpc.org/kojingharang/20130710

• ↓passed in practice room

class Egalitarianism3 {
	public:
	int maxCities(int n, vector <int> a, vector <int> b, vector <int> len) {
		if(n<=2) return n;
		VVI g = VVI(n, VI(n, 1<<30));
		REP(i, n-1) {
			g[a[i]-1][b[i]-1] = len[i];
			g[b[i]-1][a[i]-1] = len[i];
		}
		REP(i, n) g[i][i]=0;
		REP(k, n) REP(i, n) REP(j, n) g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
		ll ans = 2;
		REP(i, n) {
			map<int, VI> hi; // hi[r] ... i を中心とした距離 r かつ全点間について距離が 2r のノード集合
			REP(j, n) {
				auto& vs = hi[g[i][j]];
				ll r = g[i][j];
				// check if we can add j to hi[r]
				bool ok = true;
				for(auto v : vs) if(g[v][j] != 2*r) ok=false;
				if(ok) {
					hi[r].PB(j);
					ans = max(ans, (ll)hi[r].size());
				}
			}
		}
		return ans;
	}
};

ツイートする