AGC002B Box and Ball

AGC002B Box and Ball

提出AC

int main()
{
    cout <<setprecision(10);
    ll n , m;
    cin >> n >> m;
    vector<ll> x(m),y(m);
    rep(i,m){
        cin >> x[i] >> y[i];
    }
    vector<pair<ll,bool>> boal(n); //個数 赤がありうるかそうかどうか
    rep(i,n){
        boal[i].first = 1;
        boal[i].second = false;
    }
    boal[0].second = true;
 
    ll ans = 0;
    rep(i,m){
        ll from = x[i]-1;
        ll to = y[i]-1;
 
        boal[from].first -- ;
        boal[to].first ++;
        if(boal[from].second){
            if(boal[from].first == 0){
                boal[from].second = false;
            }
            boal[to].second = true ;
        }
    }
    rep(i,n){
        if(boal[i].second){
            ans ++ ;
        }
    }
    cout << ans << endl;
}

解法

赤がある場所をどうにかして保持する

例えば、移動前が2個で赤があるかもしれないなら、移動後は、

移動した先と移動した元に赤が入っている可能性がある。

しかし前回赤があった場所も、そこからどこかにボールを移動させた後、そこにボールがないなら

赤は存在しているはずがない。

コードの説明

x[i],y[i]には、i回目の操作、xからyにボールを一個投げることを示している。

boal[i]には、箱に入ってるボールの数と、赤が存在しうるかどうかがbool型で入っている

最初箱1に赤が入っているので、boal[i].secondをtrueにしておいてあるの。

rep(i,m)が操作をするところで、from が移動元 to が移動先

移動元fromのボールの数が1個から0個になったらボールが存在していないのでその箱に赤がある可能性は0

よって、boal[from].second = false にする

みたいなノリ

悪くないコードだと思うよ