Algoogle

Algorithm for Programming Contest

AOJ 2555 Everlasting Zero

Category: AOJ Tag: implementation

Everlasting Zero

問題概要


プレイヤーはN個のスキルがあって, それらにポイントを割り振る.
ポイントは一度割り振ったら減らせない.
各コマンドを覚えるのに必要なスキルのポイントの条件が与えられる.
各コマンドはその条件を全て満たしている時に取得可能.
このとき, 全てのコマンドを取得するような方法は存在するか.

解法


1つのコマンド内の条件で矛盾する場合はNo

まだ取得していないコマンドaを取得した時に, 他のまだ取得できていないコマンドのうち, aを取ったあとでは取得できないコマンドがあるか確認する.
あるならまだaは取得しない. ないなら取得する.
1周回して取得できるコマンドがなければNo
それをM回繰り返す.

コード


(2555.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
60
61
62
63
64
#include <iostream>
#include <vector>
#include <map>

using namespace std;

typedef pair<int, int> pii;
const int inf = 100;
vector<vector<pii> > skills;
int M, N;
bool can[128][128];
bool used[128];

bool ok(int a, int b){
    for(int i = 0; i < N; i++)
        if(skills[a][i].first > skills[b][i].second)
            return 0;
    return 1;
}

bool ok2(int cur){

    for(int i = 0; i < M; i++)
        if(!used[i] and !can[cur][i]) return 0;
    return 1;
}

bool solve(){
    cin >> M >> N;
    for(int i = 0; i < M; i++){
        vector<pii> res = vector<pii>(N, pii(0, inf));
        int K; cin >> K;
        for(int j = 0; j < K; j++){
            int s, t; string c;
            cin >> s >> c >> t;
            s--;
            if(c[0] == '>') res[s].first = max(res[s].first, t);
            else res[s].second = min(res[s].second, t);
            if(res[s].first > res[s].second) return 0;
        }
        skills.push_back(res);
    }
    for(int i = 0; i < M; i++)
        for(int j = 0; j < M; j++)
            if(ok(i, j)) can[i][j] = 1;
    int cnt = 0;
    for(int i = 0; i < M; i++){
        int f = -1;
        for(int j = 0; j < M; j++)
            if(!used[j] and ok2(j)){
                used[j] = 1;
                f = j;
                break;
            }
        if(f < 0) return 0;
        if(++cnt == M) return 1;
    }
    return 0;
}

int main(){
    cout << (solve()? "Yes": "No") << endl;
    return 0;
}

Comments