Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC002-B 「Box and Ball」 (400)

editorialの換言が天才的すぎる。

問題リンク

概要

 N個の箱があり、最初の時点で各箱にはボールが1個ずつ入っている。箱1のボールは赤色、他の箱のボールは全て白色である。

これから箱に対して M回の操作を行う。 i回目の操作では箱 x_iからボールを1個取り出して箱 y_iに入れる。

 M回の操作が終わった時点で、赤いボールが入っている可能性のある箱の数を求めよ。

制約

  •  2 \leq N \leq 10^5
  •  1 \leq M \leq 10^5
  •  x_i \neq y_i
  • 空の箱からボールを取り出すような操作は行われない。

解説

具体的に「操作 iで赤ボールと白ボールが選ばれた場合で分岐して...」なんてやっていたら指数的にパターンが分岐してしまい、とてもじゃないが手に追えない。

そこで、知りたいのは「赤ボールが入っている可能性があるか」だけなので、その情報を保持することにする。

  •  x_iに赤ボールが入っている可能性がない場合

    このとき移動するボールは絶対に白ボールなので、情報に変化はない。

  •  x_iに赤ボールが入っている可能性がある場合

    このとき移動するボールは赤か白かは分からないが1、どちらにせよ y_iに赤ボールが入る可能性が出てくる。

さらにこれだけでは不十分で、もう1つ考慮すべきことがある。それは「空箱に赤ボールは絶対入っていない」ということ。つまりボールを移動したあと x_iが空になった場合、 x_iに赤ボールが入っている可能性はなくなる。このためにも、「各箱に入っているボールの数」も保持する必要がある。

問題の換言

解法としては上で十分なのだが、いかんせん抽象的で分かりにくいだろう。 そういう方も、editorialの以下の言い換えならすぐに理解できるかもしれない。

 N個のコップがあり、最初の時点で各コップには水が1Lずつ入っている。コップ1の水は赤色、他のコップの水は全て無色透明である。

これからコップに対して M回の操作を行う。 i回目の操作ではコップ x_iから水を1L取り出してコップ y_iに入れる。

 M回の操作が終わった時点で、赤色のついた水が入っているコップの数を求めよ。

箱をコップ、ボールを水に変えただけでとてもイメージが掴みやすくなる。

実装例

#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    int num[N + 1];
    fill(num, num + N + 1, 1);
    // 箱iにはボールがnum[i]個入っている

    bool red[N + 1];
    fill(red, red + N + 1, false);
    red[1] = true;
    // red[i] = 赤いボールが入っている「可能性がある」か

    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        if (red[x]) red[y] = true;
        // 赤ボールが移動するかもしれない

        --num[x];
        ++num[y];
        if (num[x] == 0) red[x] = false;
        // 空箱に赤ボールが入っている可能性は0
    }

    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        if (red[i]) ++ans;
    }
    cout << ans << endl;
    return 0;
}

感想

  • 可能性の捉え方は個人差が大きそう。
  • 可能性の拡散を水に喩えるのは見事の一言。

  1. 場合によっては x_iには白ボールしか入っていないこともある。それでも x_iに赤ボールが入っているような操作は必ず存在するので、その操作の場合だけを考えればいい。