GCJ 2016 Round 1A C - BFFs

問題

Dashboard - Round 1A 2016 - Google Code Jam

問題概要

人の子どもがいる．それぞれの子どもにはIDがまでそれぞれ与えられている．そして，どの子どもも1人ずつbest friend forever(BFF)を持っていて，それが誰なのかわかっている．

何人かの子どもの円を作りたい．円に加わっている全ての子どもに対して，BFFが左隣りか右隣りに来るようにしたいとき，最大で作ることの出来る円の大きさは何人から出来る円になるだろうか？

アイデア

まず，smallに関してはであるから，どの子どもを円に加えるかというのをすべて試すことができる(通り)．どの子どもで円を組むかを決め終わったら，その組に対して全ての順列を試し，ちゃんと全てに対してBFFの条件を満たしていればその人数の最大値を更新していくという方法を取ることが出来る．(実はこのように2段階に分けなくても，このような部分集合の順列は全体の順列のprefixとして現れてくれるのでの順列に対して随時更新をかけていくという方法で調べきれるよということがEditorialに書いてあった)．

しかしながらlargeではである．さすがに全通り試しているのは間に合わない．BFFはある種の写像であると考えて，からへ値が変化するようなイメージで考えると，それはまさに有向グラフとして考えることと一致する．そして，この有向森のそれぞれの連結部分に注目すると，「ループ部分とそのループ部分に向かっていく枝」で構成されていることがわかる．つまり，どの頂点からBFFをたどり始めても，必ずループに入るということになる．そして，その連結成分内にループ部分は1つしか存在しない，つまり，そのループ部分を大きな1つのノードとみなすと，ループ部分を根として根に向かって有向辺がのびている有向木の形をとっているわけである．

いま，ある頂点から始めるとそのBFFであるへ移動する．そのまたBFFであるへ移動する．これを繰り返していくと，のBFFのBFFのBFFの...のBFFにたどり着く．そして，上述のグラフの性質上，いずれループに突入し，再びすでに訪れたノードへ到達することになる．つまりあらゆる連結成分に対して，少なくとも「そこから辿れるBFFが全てループの中であるようなノード」が少なくとも1つは存在するということが言える．

このような3人以上で構成されているループを円の中に組み込んだ時を想定してみると，ループが存在するという時点で各子どもに対して隣にいなければならない子どもが2人発生してしまうので，そのループがある時点でそれ以外の人が入る余地が無い．なので，円を構成した時に，最大となる候補にこのようなループを挙げることができる．

ただそれだけではないことに気をつけたい．今回の条件では自己ループは発生しないので1人のループは存在しない．しかし，2人で構成されるループを考えてみよう．構成する子どものIDをととする．まず，この2人を円に組み込んでみる．すると，この2人はもうこの段階で満足していて，の左との右は空いている事になる．つまり他の人を連れてくることが出来る．ここには，この2人と連結していない子どもですら入りうる．しかし，できるだけ和を大きくしたいので，この形を壊さない形で拡張していこう．の隣には，をBFFに持つを選べば，またの左が空いていることに出来る．それをできるだけ繰り返す．についても同じことをしておく．これをしていっても，既に全ての人が満足している列が得られることになる．そして，このような列をそのまま円にしても良いし，このような列を複数組み合わせた円を作っても全ての人が満足している状態が保たれる．

つまり上述のことをまとめると，まず2人だけで構成されるループが作られうる場合が存在して，それを考えてみるとそのループの左と右にそれぞれBFFをできるだけ長い形で繋いだものを作っていき，それらを複数組み合わせることが最大の円を構成する候補であるということになる．

今までのことを簡潔にあらわしているのがまさにEditorialの図で，3人以上のループ，または2人のループの左右に枝を足したものを複数組み合わせたものが候補になる(図のように枝の部分としては長い方を選ぶのが当然最適である)ということを表している．

サイクルを見つけて，そのサイクルの大きさを調べて，3以上か2かでその後の挙動を決めようということになり，3以上ならそれを最大値の候補として更新，2ならそのを根として逆辺を辿ったときの木の深さと，で同様のことをして木の深さと，2を足してそれを数え上げていき，全ての連結成分を見終わった時に最大値として更新してあげるのが自分の実装方針になる．BFSなどを使っているが，問題のグラフは木なので時間計算量は．

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        int n;
        cin >>n;

        //BFF
        vector<int> g[1000];
        //逆辺
        vector<int> inv[1000];

        //辺作成
        rep(i,n)
        {
            int f;
            scanf(" %d", &f);
            --f;
            g[i].pb(f);
            inv[f].pb(i);
        }

        int ans=0;
        //ループサイズ2のものを組み合わせた時に出来る円の大きさ
        int twos=0;

        vector<bool> vis(n,false);

        //iから探索を始める
        rep(i,n)
        {
            //既に訪れている場所なので探索は不要
            if(vis[i]) continue;

            //はじめに連結成分を見つけてvisを更新しておく
            vis[i]=true;
            queue<int> que;
            que.push(i);
            while(!que.empty())
            {
                int v=que.front();
                que.pop();
                rep(j,g[v].size())
                {
                    if(!vis[g[v][j]])
                    {
                        vis[g[v][j]]=true;
                        que.push(g[v][j]);
                    }
                }
                rep(j,inv[v].size())
                {
                    if(!vis[inv[v][j]])
                    {
                        vis[inv[v][j]]=true;
                        que.push(inv[v][j]);
                    }
                }
            }

            //iからの連結成分を探すための訪問記録
            vector<bool> tvis(n,false);
            //現在位置
            int now=i;
            while(!tvis[now])
            {
                tvis[now]=true;
                now=g[now][0];
            }

            //この時点でnowには2回目の訪問になった
            //つまりループ内に存在する頂点である
            //このループの大きさを調べる
            set<int> s;
            while(1)
            {
                //既に訪れている
                if(s.find(now) != s.end()) break;
                s.insert(now);
                now=g[now][0];
            }

            //ループの大きさ
            int cycle=s.size();
            if(cycle==2)
            {
                //ループを構成する2頂点
                int l=now;
                int r=g[now][0];

                const int INF=123456;
                vector<int> dl(n,INF);
                vector<int> dr(n,INF);

                //lから出る逆辺をたどる
                dl[l]=0;
                que.push(l);
                while(!que.empty())
                {
                    int v=que.front();
                    que.pop();
                    rep(j,inv[v].size())
                    {
                        int nx=inv[v][j];
                        if(nx==r) continue;

                        if(dl[nx]>dl[v]+1)
                        {
                            dl[nx]=dl[v]+1;
                            que.push(nx);
                        }
                    }
                }

                //rから出る逆辺をたどる
                dr[r]=0;
                que.push(r);
                while(!que.empty())
                {
                    int v=que.front();
                    que.pop();
                    rep(j,inv[v].size())
                    {
                        int nx=inv[v][j];
                        if(nx==l) continue;

                        if(dr[nx]>dr[v]+1)
                        {
                            dr[nx]=dr[v]+1;
                            que.push(nx);
                        }
                    }
                }

                //最も遠い点を選ぶ
                int ml=0,mr=0;
                rep(j,n)
                {
                    if(dl[j]<INF) ml=max(ml,dl[j]);
                    if(dr[j]<INF) mr=max(mr,dr[j]);
                }
                
                twos+=2+ml+mr;
            }
            else ans=max(ans,cycle);

        }

        ans=max(ans,twos);

        printf("Case #%d: %d\n", t+1, ans);
    }
    return 0;
}