JOI春合宿 2007-day2 SALT TREE XV

問題文 : SALT TREE XV

解法 :
(qnighy さんのものをチラッと見てしまったので, 考えながら書いた所をまとめる.)

まず, ある状態から, 辺の数が0 で頂点の数が0 に出来れば自分の勝利であることを確認する.
また, 辺の数が0 の状態への遷移は, 頂点が1 個の時に限る. このように遷移をたどると, 後手の辺数と頂点数を常に偶数個にしてしまえば勝てることが分かる. 頂点数か辺数が奇数であれば, 適切に辺/頂点を取り除くことで必ず頂点数 / 辺数のどちらも偶数にできる.

次に, 入力されるグラフは木であるから, 頂点数がN であれば, 辺数はN - 1 である. いずれかは奇数であるはずなので, かならず先手が勝利することが出来る.

コード (AtCoder用) :

#include "grader.h"
#include "salt.h"
#include <vector>
#include <cstdio>

#define MAX_N (1000)

using namespace std;

vector<int> G[MAX_N];
bool used[MAX_N];

void vanish(int N, int u, int v)
{
	vector<int>::iterator it;
	
	if (u < v){
		for (it = G[u].begin(); it != G[u].end(); it++){
			if (*it == v) *it = -1;
		}
		for (it = G[v].begin(); it != G[v].end(); it++){
			if (*it == u) *it = -1;
		}
	}
	else {
		used[u] = true;
		for (int i = 0; i < N; i++){
			for (it = G[i].begin(); it != G[i].end(); it++){
				if (i == u || *it == u) *it = -1;
			}
		}
	}
}

void play(int N, int E[][2])
{
	int ru, rv;
	
	for (int i = 0; i < N - 1; i++){
		G[E[i][0] - 1].push_back(E[i][1] - 1);
		G[E[i][1] - 1].push_back(E[i][0] - 1);
	}
	
	int Vnum, Enum;
	int mu, mv;
	
	while (1){
		
		int Vnum = N, Enum = 0;
		for (int i = 0; i < N; i++){
			if (used[i]) Vnum--;
			for (int j = 0; j < G[i].size(); j++){
				if (~G[i][j]) Enum++;
			}
		}
		
		Enum /= 2;
		
		if (Vnum % 2 == 0 && Enum & 1){
			for (int i = 0; i < N; i++){
				for (int j = 0; j < G[i].size(); j++){
					if (~G[i][j]){
						mu = i;
						mv = G[i][j];
					}
				}
			}
		}
		else if (Vnum & 1 && Enum % 2 == 0){
			for (int i = 0; i < N; i++){
				int cnt = 0;
				for (int j = 0; j < G[i].size(); j++) if (~G[i][j]) cnt++;
				if (!used[i] && cnt % 2 == 0) mu = mv = i;
			}
		}
		else {
			for (int i = 0; i < N; i++){
				int cnt = 0;
				for (int j = 0; j < G[i].size(); j++) if (~G[i][j]) cnt++;
				if (!used[i] && cnt == 1) mu = mv = i;
			}
		}
		
		if (mu > mv) swap(mu, mv);
		vanish(N, mu, mv);
		
		turn(mu + 1, mv + 1, &ru, &rv);
		
		--ru, --rv;
		if (ru + rv < 0) break;
		else vanish(N, ru, rv);
	}
	
  return;
}