AGC010-F Tree Game 解説 - 橙になりたいaquarium

こんにちは、
競プロのしすぎで編入試験の勉強とレポートが手についてない愚かな少女は誰でしょう。
そう、しんちゃんです。

AGC-Fを解いてみたかったので、difficultyが一番低いものを選んで解いてみました。
1600点ってなんだかやばそうですね(笑)。現在AtCoderのレートが1784(青)である私だと3時間かかりました。
atcoder.jp

以前解いていた別の赤diffもオススメです(知識が必要なく、あきらめなければ解けるはずです)。
こちらも2時間かかりました。
atcoder.jp

$2 \leqq N \leqq 3000$ ということで $O(N^2)$ とかで解きたくなります。

気にしておく性質として、木は二部グラフであり、高橋君のターンの初めに駒が置いてある頂点は限られています。このとき、青木君のターンの初めに駒が置いてある頂点は、高橋君と被ることがありません。
つまり、頂点ごとに誰のターンかがわかります。

まぁまずは、ある頂点からスタートしたとして、勝敗と計算量を考慮せず考えてみましょう。
その頂点( $from$ としましょう)と、その頂点と隣接してる頂点( $to$ としましょう)において…、

すべての $to$ において、 $A[from] <= A[to]$ とき、高橋君が負けることがわかります。

なぜなら、 $from$ からどこへ進もうとも、青木君が $from$ へ戻すことができるからです。
このとき、配列 $lose$ を用意して、 $lose[from] = true$ とします。

次に、ある $to$ が存在して、 $lose[to] = true$ かつ $A[from] > A[to]$ を満たすならば、高橋君は勝ちます。

ここで、 $lose[to] = true$ の条件だけでいいと勘違いしてしまう人は多いと思います。
こう考えるといいです。高橋君スタートで $from$ にいたとすると、 $A[from]$ は 1 減り、 $to$ へ移動します。 $to$ が新たな $from$ としてスタートです。
このとき、青木君の負けが確定するためには、元の $from, to$ において、 $A[from] \geqq A[to]$ が必要です。
ここで注意するのは、 $A[from]$ は 1 減ったものであるということです。なので、 $A[from] - 1 \geqq A[to]$ 、つまり $A[from] > A[to]$ という条件が必要になります。
このとき、配列 $win$ を用意して、 $win[from] = true$ とします。

3つ目。すべての $to$ において、 $win[to] = true$ ならば $lose[from] = true$ です。

こちらはわかりやすいと思われます。
さらに、すべての $to$ において、 $win[to] = true$ または $A[from] <= A[to]$ ならば $lose[from] = true$ です。

さて、次の段階に移りましょう。
$win[to] = true$ ならば $from$ と $to$ の間の辺を消せます。
なぜなら $from$ から $to$ へ移っても意味がない(どうせ負ける)からです。
そして辺を消したとき、頂点が 1 つの連結成分が生まれてしまうときがあります。
この場合は、その頂点 $from$ から $win[to] = true$ となる $to$ へ辺を追加しても結果が変わらないことから、負けになるとわかります。

同様に、 $lose[to] = true$ かつ $A[from] \leqq A[to]$ となる $from$ と $to$ の間の辺も消してあげましょう。

最後の段階です。
辺を消すのと上記の操作を繰り返せば、いつかは全ての頂点 $v$ において、 $lose[v] = true$ もしくは $win[v] = true$ がなりたち、 $win[v] = true$ となる $v$ を昇順に出力すればいいです。
辺を消せば(もしくは未操作の段階で)、連結成分内で $A[v]$ が最小となる頂点 $v$ が少なくとも 1 つ存在し、 $lose[v] = true$ となります。
そのような頂点が現れたとき、その頂点に隣接する頂点 $to$ を考えると、明らかに $A[v] \leqq A[to]$ です。 $A[v] < A[to]$ であれば、 $win[to] = true$ とできるので、 $A[v] = A[to]$ の場合を考えましょう。このとき、 $A[v]$ は連結成分内で最小ですから、 $A[to]$ も連結成分内で最小となります。したがって、 $lose[to] = true$ となります。よって、 $A[to]$ の勝敗は確実に決定できるのです。

以上より、上記の操作 1 回につき、 $win[v] = true$ となる $v$ が少なくとも 1 つできます。そして $v$ と接続している辺を消せます。辺が消えればもちろん頂点の勝ち負けも決まっていきます。

辺の個数は $N - 1$ ですから、繰り返しは $N$ 回を超えることはないとわかります。
各繰り返しで、各頂点と隣接する頂点の探索、そして辺の削除で $O(N$ log $N)$ ですから、この問題の時間計算量は、 $O(N^2$ log $N)$ となり、間に合います。(logが影響しやすいグラフほどループの回数が減るので←ほんとか？)

2023/12/04追記
辺の削除回数は合計で $O(N$ log $N)$ であり、削除を試みる回数は $O(N^2)$ であり、辺を根こそぎとられた頂点から辺を探索するのは $O(1)$ なので、解法全体の時間計算量は $O(N^2)$ となります。

ソースコードはこちら。
atcoder.jp

#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define rep(i, n) for(int i=0;i<n;i++)
#define all(i, v) for(auto& i : v)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int n, a, b;
    cin >> n;
    vector<set<int> > v(n); // グラフ

    vector<int> c(n);
    rep(i, n) cin >> c[i];

    rep(i, n - 1){ //辺の追加
        cin >> a >> b;
        a--; b--;
        v[a].insert(b); 
        v[b].insert(a);
    }

    bool lose[n], win[n]; // 負け、勝ち
    memset(lose, 0, sizeof(lose));
    memset(win, 0, sizeof(win));

    bool con = false; // ループ継続判定

    do{
        con = false;

        // 負ける頂点を増やす。
        rep(i, n){
            if(lose[i] || win[i]) continue;
            bool ok = true;
            all(to, v[i]) if(c[to] < c[i]) ok = false;
            if(ok) lose[i] = true;
        }

        // 勝てる頂点を増やす。
        rep(i, n){
            if(lose[i] || win[i]) continue;
            bool ok = false;
            all(to, v[i]) if(lose[to] && c[to] < c[i]) ok = true;
            if(ok) win[i] = true;
        }

        // 勝つ頂点の周りの辺を消す。
        rep(i, n){
            set<int> pos;
            all(to, v[i]) if(win[i] || win[to]) pos.insert(to);
            all(to, pos){
                v[i].erase(to);
                v[to].erase(i);
            }
        }

        // lose[i] == true かつ c[i] >= c[to] となる辺を消す。
        rep(i, n){
            if(!lose[i]) continue;
            set<int> pos;
            all(to, v[i]) if(c[i] >= c[to]) pos.insert(to);
            all(to, pos){
                v[i].erase(to);
                v[to].erase(i);
            }
        }

        // まだ決まってないのがあるなら続ける。
        rep(i, n) if(!lose[i] && !win[i]) con = true; 
    }while(con);

    rep(i, n) if(win[i]) cout << i + 1 << " ";
    cout << endl;

    return 0;
}

みなさまよいお年を～～!!!!
冬休みクラスメートと会えなくて暇なので(←暇ではない。寂しいので)通話などのお誘い待ってます。