ICPC 2020-B 接触追跡 解説

ICPC

問題: https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1641?year=2020

問題の概要

人がm人います．最初，そのうちの一人がウイルスに感染しています．その後，nペアの人が順番に接触します．このとき，感染者と接触した人は感染疑いになります．また，感染疑いの人と接触した場合も感染疑いになります．

最終的に，感染/感染疑いの人は何人いますか？

解法（一般論）

（感染/感染疑いというのがめんどくさいので，以降は単に感染と書くことにします．）

接触者のペアを見たとき，少なくとも片方が感染しているなら両者とも感染します．よって，処理を効率よく行うには，利用者IDから，その人が感染しているかを高速に判定できれば良いです．これは，[利用者ID] = 1(感染) or 0(感染してない)となるような，0と1で構成される配列を使うことで、O(1)でできます．

はじめに，利用者IDがpの人だけ1を代入しておいて，接触者のペアのうち，どちらかの利用者IDの値に1が代入されていれば，両者ともに1を代入することを繰り返します．

最後に，配列の1の数が，そのまま答えになります．配列の要素が0か1であることを考慮すると，これは単に配列の要素の合計値として構いません．

実装（C/C++）

#include <stdio.h>

int main(){
    int m,n,p;
    while(scanf("%d %d %d", &m, &n, &p)){
        if(n+m+p == 0)break;
        // 利用者分の配列を確保して，0で初期化
        int v[100]={0};
        p--; // 0始まりに
        v[p] = 1; // IDがpの人は感染
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d %d", &a, &b);
            a--; b--; // 0始まりに
            // どっちか感染してたら
            if(v[a] == 1 || v[b] == 1){
                // 両方感染する
                v[a] = 1;
                v[b] = 1;
            }
        }
        int ans = 0;
        // 合計を求める
        for(int i=0;i<m;i++){
            ans += v[i];
        }
        printf("%d\n", ans);
    }
}

実装（python）

while True:
    m,n,p = map(int, input().split())
    if n+m+p == 0:
        break
    # 利用者分のリストを確保して，0で初期化
    v = [0 for i in range(m)]
    p -= 1 # 0始まりに
    v[p] = 1 # IDがpの人は感染
    for i in range(n):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        # どっちか感染してたら
        if v[a] == 1 or v[b] == 1:
            # 両方感染
            v[a] = 1
            v[b] = 1
    # 合計を求める
    print(sum(v))

別解: boolのOR演算

これはちょっとトリッキーですが，「どちらか一方でも感染してたら両者とも感染」というのは，OR演算そのものです．いま，感染していることをTrue，感染してないことをFalseとすると，

  • 両方感染してるとき，True | True = True
  • aだけ感染してるとき，True | False = True
  • bだけ感染してるとき，False | True = True
  • 両者感染してないとき，False | False = False

となって，感染ルールはOR演算そのものだということが分かります．これを利用すると，各ペアについて，「どちらか一方でも感染している？」ことを気にせずに実装できます．

#include <stdio.h>

int main(){
    int m,n,p;
    while(scanf("%d %d %d", &m, &n, &p)){
        if(n+m+p == 0)break;
        // 利用者分を確保して，falseで初期化
        bool v[100];
        for(int i=0;i<m;i++)v[i] = false;
        p--;
        v[p] = true;
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d %d", &a, &b);
            a--; b--; 
            // お互いに，単に相手とOR演算
            v[a] |= v[b];
            v[b] |= v[a];
            
        }
        int ans = 0;
        // 合計が答え
        for(int i=0;i<m;i++){
            ans += v[i];
        }
        printf("%d\n", ans);
    }
}