Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

 | 

2017-05-07

AtCoder Grand Contest 014 D - Black and White Tree

09:56 | AtCoder Grand Contest 014 D - Black and White Tree - kojingharangの日記 を含むブックマーク はてなブックマーク - AtCoder Grand Contest 014 D - Black and White Tree - kojingharangの日記 AtCoder Grand Contest 014 D - Black and White Tree - kojingharangの日記 のブックマークコメント

  • 木が与えられる。先手は白、後手は黒で塗られてない頂点を順番に塗っていく。塗れなくなったら黒頂点に隣接する頂点を全部黒にする。
  • 白が残ってたら先手の勝ち。最適にプレイしたらどっちが勝つか求めよ。
  • 2≦頂点数≦10^5
  • 葉とその親がどちらも白になったら白が勝つ。
  • という状態を作り出すには、葉である子が 2 個以上ある頂点を最初に白に塗ればいい。
  • 最初にそういうのがなかったら? う〜む
  • 葉である子が 1 個だけの頂点を白に塗ったら、次はその葉を黒にするしかない。
  • ? - 親 - 葉 の親と葉を消していくといい?
  • それ以外のとこに白を塗ることで勝てることはあるんじゃないかとかいろいろもやっとして終わり
  • 帰納法で完全マッチングあり←→後手勝ちが証明できるようだ。
  • ? - 親 - 葉 の親と葉を消せるだけ消して、1頂点になった or 葉である子が 2 個以上ある頂点があったら First, なければまた繰り返し、消えなくなったら Second でよかった
  • solve1 で remove_if は計算量的にやばいかなと思ったが時間は solve2 と同じくらいだった。
  • solve1 は実装だけならできていたかもしれないので、証明がいまいちできない時はそれっぽい実装を進めてしまうというのもありだなぁ特に何回でも試せるコンテストでは。
  • solve2 は実際にはノードを消さないちょい賢い方法。あまり思いつく気はしない。
  • Accepted in practice
ll N;

// ノードを実際に消していく版
// ? - A - B があったとき A, B を消しまくる。葉である子が 2 個以上ある頂点がでてきたら First
// 頂点が 1 個になっても First
// なければまた繰り返し
// 消えなくなったら Second 
string solve1(VVI& g) {
	while(1) {
		ll edges = 0;
		REP(i, N) {
			int cnt=0;
			edges += g[i].size();
			for(int j : g[i]) {
				if(g[j].size()==1) cnt++;
			}
			if(cnt>=2) {
				return "First";
			}
		}
		edges/=2;
		if(edges==0) return "First";

		// i - adj - X =... -> X =...
		bool ch=false;
		REP(i, N) {
			if(g[i].size()==1) {
				int adj = g[i][0];
				if(g[adj].size()==2) {
					int X = g[adj][0]==i ? g[adj][1] : g[adj][0];
					{
						auto en = remove_if(ALL(g[X]), [=](int a) { return adj==a; });
						g[X].erase(en, g[X].end());
					}
					g[adj].clear();
					g[i].clear();
					ch=true;
				}
			}
		}
		if(!ch) break;
	}
	return "Second";
}

// return: このノード以下で完全マッチの相手を探しているノードの個数
ll dfs(int u, int p, VVI& g) {
	ll x = 0;
	for(int v: g[u]) if(v!=p) x += dfs(v, u, g);
	if(x==0) return 1; // need to match ... 子が全部マッチしてるので
	if(x==1) return 0; // matched
	return INF; // 余りが確定したので無理
}

// ノードを消さないスマート版
string solve2(VVI& g) {
	// rest==0 ←→ 完全マッチしている
	ll rest = dfs(0, -1, g);
	string ans = rest ? "First" : "Second";
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	string s;
	while(cin>>N) {
		VVI g(N);
		REP(i, N-1) {
			ll A, B;
			cin>>A>>B;
			A--;B--;
			g[A].PB(B);
			g[B].PB(A);
		}

//		string ans = solve1(g);
		string ans = solve2(g);

		cout<<ans<<endl;
	}
	
	return 0;
}
コメント
 |