CS Academy #40 - Direct the Graph

問題

CS Academy

問題概要

頂点数の完全グラフの各辺に対して向きを付ける(トーナメント)。この時、経路長が3である閉路の個数が最大になるように向きを付け、その向きの付け方と、その結果経路長が3である閉路はいくつになるか答えよ。

• 

アイデア

まず、問題に答える前に、あるトーナメントに対して、経路長3の閉路の個数を数え上げるにはどうすればいいだろうか(コンテスト時間中は、ある辺に対して、他のある頂点と閉路をなすかチェックするしか思いつかなかった)。

逆に満たしていないものの個数を数えて、全体から引くことを考えてみる。全体で通りの3点を選ぶ方法があり、その3点の間にある有向辺が閉路をなしていないもののの個数を数える。すると、閉路をなさない形は下の図のようなパターンのみに帰着する。

それぞれの頂点の(入次数,出次数)に注目すると、それぞれ(0,2)、(1,1)、(2,0)となっている。

数え上げのためには、このどちらも出ている頂点とどちらも入ってくる部分に注目して、頂点の入次数を、出次数をと表すと、数え上げの重複を考慮して、経路長が3である閉路の個数は

となる。

本題に戻ると、この閉路の個数を最大化したい。各頂点に対する辺の個数の制約によって、であるから、これを最大化するにはとはできるだけ等しい値にすると良い。そのようなグラフは、各に対してちょうど半分(またはと)になるように辺の向きを割り当てるのが良い。(実は01を交互に出力をすると今回の出力形式だとそれが実現できる(隣接行列の上三角部分を出すので))。

inとoutが各頂点に均等に分かれるようにすれば良さそうってのは何となくあったけど数え上げができなかった…

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))

int a[2020][2020];

int main()
{
    ll n;
    cin >>n;

    ll U = n*(n-1)*(n-2)/6;
    ll sub = 0;

    int b = 0;
    rep(i,n)for(int j=i+1; j<n; ++j)
    {
        a[i][j] = b;
        a[j][i] = !b;
        b = !b;
    }

    rep(i,n)
    {
        ll in = 0, out = 0;
        rep(j,n)if(i!=j)
        {
            if(a[i][j]==1) ++in;
            else ++out;
        }

        sub += in*(in-1)/2;
        sub += out*(out-1)/2;
    }
    sub/=2;

    printf("%lld\n", U-sub);
    rep(i,n)for(int j=i+1; j<n; ++j) printf("%d", a[i][j]);
    printf("\n");
    return 0;
}