SRM 299 DIV2 1000 StrangeParticles

問題概要

　空間を飛び回る粒子があります。２つの粒子がぶつかると、以下の３つのうちどれかが起きます。

1. 最初の粒子が消滅する
2. ２つ目の粒子が消滅する
3. 何も起こらない

粒子の数は50個以下です。任意のペアの粒子が衝突した場合、上の1-3のうちどれが起こるかという情報が与えられます。その情報を元にランダムな回数・順番で粒子同士が衝突したとき、最終的に残る粒子の数の最小値を求めよ。

方針

　強連結成分（SCC）分解して、DAGにして、DAGの根の数が答え。強連結成分分解は、DFSを二回やる方法が有名ですが、この問題では節点数が小さいのでワーシャルフロイド法を利用したやり方でもできます。

1. 粒子Aが粒子Bを消すことができるとき、AからBへ有向枝をはる。
2. ワーシャルフロイドで、1.の推移閉包を求める。
3. i->jパス、j->iパスが同時に存在するとき、閉路と考える。これを利用して、SCCにグルーピングしていく。
4. SCCを1つの節点とみなして、枝をはり直してDAGにする。
5. 各接点の入次数を数える。

まあソース見た方が早いです。DFS2回バージョンは直感的に理解するのが難しいですが、こっちのワーシャルフロイドバージョンは直感的につかみやすいですねー。実装量も少ないので、計算量に余裕がある場合はこっちのほうがいいかもしれません。

ソースコード

view plainprint?

1. bool win[50][50];  
2. int id[50];  
3. int d[50];  
4.   
5. class StrangeParticles {  
6. public:  
7.     int remain(vector<string> interacts) {  
8.         int N = interacts.size();  
9.   
10.         memset(win, 0, sizeof(win));  
11.         REP(i, N) REP(j, N) if (i == j || interacts[i][j] == '-') win[i][j] = 1;  
12.         REP(k, N) REP(i, N) REP(j, N) win[i][j] |= win[i][k] & win[k][j];  
13.   
14.         memset(id, -1, sizeof(id));  
15.         int p = 0;  
16.         REP(i, N) {  
17.             if (id[i] == -1) {  
18.                 FOR (j, i, N) if (win[i][j] & win[j][i]) id[j] = p;  
19.                 ++p;  
20.             }  
21.         }  
22.   
23.         memset(d, 0, sizeof(d));  
24.         REP(i, N) REP(j, N) if (win[i][j]) {  
25.             if (id[i] != id[j])  
26.                 d[id[j]]++;  
27.         }  
28.   
29.         int ret = 0;  
30.         REP(i, p) if (d[i] == 0) ++ret;  
31.   
32.         return ret;  
33.     }  
34. };  

bool win[50][50];
int id[50];
int d[50];

class StrangeParticles {
public:
    int remain(vector<string> interacts) {
        int N = interacts.size();

        memset(win, 0, sizeof(win));
        REP(i, N) REP(j, N) if (i == j || interacts[i][j] == '-') win[i][j] = 1;
        REP(k, N) REP(i, N) REP(j, N) win[i][j] |= win[i][k] & win[k][j];

        memset(id, -1, sizeof(id));
        int p = 0;
        REP(i, N) {
            if (id[i] == -1) {
                FOR (j, i, N) if (win[i][j] & win[j][i]) id[j] = p;
                ++p;
            }
        }

        memset(d, 0, sizeof(d));
        REP(i, N) REP(j, N) if (win[i][j]) {
            if (id[i] != id[j])
                d[id[j]]++;
        }

        int ret = 0;
        REP(i, p) if (d[i] == 0) ++ret;

        return ret;
    }
};