Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 SALT TREE XV

Category: JOI Tag: tree

SALT TREE XV

問題概要


木が与えられる. 2人のプレイヤーは交互に以下のいずれかの操作をし, 最初に操作ができなくなった方が負ける. 先手は必ず勝てるので, AIに必ず勝つプログラムを書け.

  • まだ取られていない頂点を1つ取る. この際その頂点に張られている辺も取られる.
  • まだ取られていない辺を1つ取る.

解法


相手の番に辺の数も頂点の数も偶数になるように頂点か辺を取れば良い.

コード


(Salt.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "grader.h"
#include "salt.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

void remove(int u, int v, vector<pii> &E, vector<int> &V)
{
        vector<pii> F;
        if(u == v) {
                for (__typeof(V.begin()) it = V.begin(); it != V.end(); it++) {
                        if(*it == u) {
                                V.erase(it,it+1);
                                break;
                        }
                }
                for(__typeof(E.begin()) it = E.begin(); it != E.end(); it++)
                        if(it->first != u and it->second != v) F.push_back(*it);
        }
        else {
                for(__typeof(E.begin()) it = E.begin(); it != E.end(); it++)
                        if(it->first != u or it->second != v) F.push_back(*it);
        }
        swap(E, F);
}

pii solve(vector<pii> &E, vector<int> &V)
{
        int es = E.size(), vs = V.size();
        if(es%2 and vs%2==0) return E[0];
        else {
                int cnt[1024] = {};
                for(__typeof(E.begin()) it = E.begin(); it != E.end(); it++){
                        cnt[it->first]++;
                        cnt[it->second]++;
                }
                for (__typeof(V.begin()) it = V.begin(); it != V.end(); it++)
                                if(cnt[*it]%2==es%2) return pii(*it,*it);
        }
        return pii(0,0);
}

void play(int N, int F[][2]) {
        vector<int> V;
        vector<pii> E;
        for (int i = 0; i < N; i++){
                if(i < N-1) E.push_back(pii(F[i][0]-1, F[i][1]-1));
                V.push_back(i);
        }
        while(true) {
                int ru, rv;
                pii rm = solve(E, V);
                remove(rm.first, rm.second, E, V);
                turn(rm.first+1, rm.second+1, &ru, &rv);
                if(!ru and !rv) return;
                ru--; rv--;
                remove(ru, rv, E, V);
        }
}

Comments