問題

Dashboard - Round 2 2016 - Google Code Jam

問題概要

工場には $n$ 個の機械がある．それぞれの機械にはオペレーターがひとりずつ必要になる．いま，オペレーターを $n$ 人雇おうとしている．そして， $n$ 次の正方行列が与えられ， $(i,j)$ の位置には従業者 $i$ が $j$ 番目の機械を扱うことが出来るか否かが記されている．

$n$ 人の従業者の出勤順序はその日によってランダムである．従業者が向上に到着した時，まだ空いている機械の中でその従業者が扱うことのできる機械の中からランダムに１つを選んでその日の仕事を行う．ここで選べる機械が無い時，その従業者はその日何もすることが出来ない．このような状況を望ましくないと思い，どのような状況でも，つまり出勤の順番やその時に各従業者が選ぶ機械に依存せずに毎日機械が稼働されるようにしたい．

いま， $n$ 個の機械を稼働させるために従業者1人に対してある機械の使い方を1ドルで教えることが出来る．毎日機械が稼働されるようにするための教育のために必要なお金の最小値を求めよ．

$1 \le n \le 25$

アイデア

問題文の中にも例示されているが，出勤順序によって上手く行かなくなってしまう場合があることを確認しておきたい．例えば $n=2$ の時，従業者がAとBとして，機械は1と2とする．そしてAは1と2を扱え，Bは2を扱える．出勤順序がBの方が先である場合，Bは必ず2を選び後からくるAは残っている1を選ぶが，先にAが来た場合，1と2のどちらかをランダムに選ぶことになり，もし2を選んでしまった場合には1を稼働できる人がもういなくなってしまうのでBに1の教育をする必要があるわけである．また，全員に対して全部の教育をしておけば必ずうまくいくので，答えが存在しないということがありえないことは意識しておきたい．

本番では自分はSmallだけ解いた，Smallの制約は $1 \le n \le 4$ であり，全ての教育方法を総当り( $2^{n*n}$ 通り)することで求められる．

ただ，Largeの制約ではそんなのは間に合わない．以下，Largeについて考えていく．

まず，この従業者と機械の関係は二部グラフとして考えられる．するとこの問題はこの二部グラフに対して，辺を追加してあらゆる「極大マッチング」が「完全マッチング」になるようにするために必要な辺の本数の最小値を求めたい，ということになる(極大マッチングという言葉は初めて聞いたが，マッチングの中で，それ以上他の辺を追加することができないようなものという定義らしい．これが最大マッチングになるとは限らないことはなんとなく想像がつく)．

この問題を解くために，まずはどのような二部グラフが「あらゆる極大マッチングが完全マッチングになる」のかを知る必要がある．そして，ちょっと実験してみるとグラフのつながっている頂点の要素集合の中で完全二部グラフである必要があるという仮説が見つかり，これは実際正しそうである．こうかもしれないというのは実際に手を動かしてみるとなんとかう想像できる．実際本番でも，自分が(やり方は思いつかなかったが)「1の正方形の塊が」作れればそれでうまくいくなあと思っていたけど，それはまさにこのことであるから，この仮説にたどり着くのはそんなに難しいことなのではないかと思う．そのグラフがどのような形であるかは解説を参考に．

ただ，逆も正しいかと言われるとそれは直感的にはどちらかわからない．これが証明できれば部分的に完全二部グラフを作るための最小コストを探す問題に変わるわけである．

証明

背理法による証明を考えてみる．今，「任意の極大マッチングが完全マッチングになるのは二部グラフの各連結成分が完全二部グラフになっている時に限られる」ということを示したいので，「任意の極大マッチングが完全マッチングになるが，二部グラフある連結成分が完全二部グラフではないような二部グラフが存在する」と仮定して話を進めていく．

この仮定されたグラフの中で，最も小さい頂点数のグラフを $G$ とする．まず始めに， $G$ は連結なものと考えて良い．なぜなら，もし連結になっていないところがあるならその部分を取り出せばより小さいものを考えることができるからである．また，二部グラフのそれぞれが同じ頂点数であるということも完全マッチングが存在するということから明らかだ．そして完全マッチングは無いのだから少なくとも1つは辺が抜けていて，その辺は $a$ と $b$ の間の辺が無いということにする．

グラフ $G$ は連結なので， $a$ に対して少なくとも1つは辺が繋がっている．その頂点を $c$ とする．さてここで，新たにグラフ $G'$ というものを考える．これは， $a$ と $c$ とそれに関連する辺を取り除いたものである．このグラフは完全二部グラフになっているので， $G$ に関しての極大マッチングとしてこれに辺 $(a,c)$ を加えたものは考えられる．ここで， $G'$ は $G$ よりも頂点数が少ないので仮定に矛盾するわけではない．

さて，この $G'$ 内において， $b$ を含む連結成分を $H$ としよう．以下の3通りの場合が考えられる：

$G$ において， $H$ 内から $c$ への辺 $(d,c)$ のような形のものが少なくとも1つは存在することは仮定から言える． $G'$ 内の連結成分は全て完全であるから， $G'$ において $d$ と $b$ を除いたマッチング $M'$ は容易に構成できて，それに辺 $(d,c)$ を加えて $G$ のマッチング $M$ とする．確かにこのマッチング $M$ は極大マッチングであるが，この時 $a$ と $b$ はカバーできていないので完全マッチングではない．よって矛盾．
$H$ から $c$ への辺は無いが， $(a,e)$ のように $a$ から $H$ 内の頂点 $e$ への辺が存在する場合も考えられる． $e$ とは違う側の頂点を $f$ とする． $H$ などの $G'$ 内の連結成分は全て完全であるから $G'$ 内で $e$ と $f$ を除いたマッチング $M'$ を構成できる．それに辺 $(a,e)$ を加えて $G$ のマッチング $M$ とすると，これは極大マッチングであるが，完全マッチングではないので，矛盾．
$H$ が $a$ とも $c$ とも繋がっていない時， $G$ は連結とは言えず，仮定に反するので矛盾．

問題の考察

問題に戻ると，まずはじめにグラフの各連結成分に対してそれぞれ各側のつながっている頂点数を調べる必要がありそうだ．それをpairとして $(p_1 , q_1 ), (p_2 , q_2 ), ...$ のように表すことにしよう．問題の制約上， $n \le 25$ であるから，最大でもこのpairの個数は50個になる(どの頂点同士も繋がっていない時に， $(1,0)$ というペアが25個と $(0,1)$ というペアが25個が現れることになる)．そして上で考えた仮説に基づくと，このpairをいくつかのグループに分けて，それぞれのグループ内でP側の個数の和=Q側の個数の和というのが成り立つ(balanced group)ようにグループ分けされていれば，そのグループ内で辺を足すことで条件を達成することが出来るようになるわけである．

グループの大きさが片側 $r$ 個の大きさである時，そのグループ内には $r^2$ 本の辺が必要になる．つまり，グループの個数を $R$ とすれば，最終的なグラフには辺が $\displaystyle \sum_{i=1}^{R} r_i$ 本あるということになる．そして，元からあった本数 $C$ は答えに含める必要がないので，答えとしては $\displaystyle \sum_{i=1}^{R} r_i - C$ を最小化したいということになってくる． $C$ は定数であるから，実際は無視してしまって構わない．つまり，この和の最小化という問題になる．

このような問題をみると，bitDPとかを考えたくなる．dp[mask][size] = maskに含まれるpairの部分集合だけを見た時 "balanced group" を構成でき，そしてその合計のグループのサイズがsizeであるときにかかるコストの最小値というものを考えれば答えはdp[(1<<R)-1][n]を見ればわかるということになる．ただ，このままだとメモリ制約が厳しい．

状態数を減らせないかと考えてみる．ここで，pairとして変換されたときに全く同じ状態のものを区別する必要がないのではないか，ということになる．例えば，25個の頂点同士があって全く辺がないときはさっきのでいくと50個のpairができることになるが，例えばどの $(1,0)$ と $(0,1)$ を繋ぐのかによってその後には影響しない．むしろその個数が分かればそれでいいのである．つまり，この場合に考慮すべき部分集合としての数は個数のみを考慮して26*26だけになる．さてここは解説に頼るが，解説によるとこのように個数を考慮した時に生まれる最大の部分集合の数は43008らしい．これでさっきのDPができれば十分に間に合いそうだ．

ここで，どのような実装にすれば良いのかわからなくなって，他の人の提出を見たところ，実装が比較的簡単そうなDPの構成方法があったのでそれで解答を作っていく．dp[mask][lc][rc] = 連結成分の使用状態がmask，従業者側・機械側の独立成分をそれぞれlc,rc個使用した時にいくつかのbalanced groupを形成するために必要なコストの最小値として，連結成分と独立成分を別にして考えるとメモリ的に抑えられる．まず，連結成分になるものの最小のものを考えてみると，それは(1,2)のような3個からなるものである．なぜなら，(2,0)のようにどちらか片方が0になるような連結成分はグラフの性質上存在し得ないし．(1,1)は連結成分に入れる必要が無いからである．それは，もうすでにbalancedなのでこれ以上要素をふやす必要がないので考慮する対象から外してしまっていいのである．すると，この連結成分に入りうるのは最低でも3個からなるものなので，問題制約的に50個以下の頂点数のときは状態数は $2^{17}$ だけ用意しておけばいいということになる．

DPの更新の際には部分集合の列挙が必要になるが，そこは蟻本を参考にした．

実装(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 pb push_back
#define fi first
#define se second

const int INF=12345678;
int dp[1<<17][26][26];

int main()
{
    int CASE;
    cin >>CASE;
    rep(T,CASE)
    {
        int ans=0, edge=0;

        //input
        int n;
        cin >>n;
        vector<string> s(n);
        rep(i,n) cin >>s[i];

        //グラフ構成
        vector<int> G[50];
        rep(i,n)rep(j,n)
        {
            if(s[i][j]=='1')
            {
                G[i].pb(n+j);
                G[n+j].pb(i);
                ++edge;
            }
        }

        //independent
        int lc=0, rc=0;
        //connected component
        int cc=0;
        int l[17], r[17];

        //連結成分をBFSで探索
        vector<bool> vis(2*n, false);
        rep(i,2*n)
        {
            if(vis[i]) continue;
            int L=0, R=0;

            queue<int> que;
            que.push(i);
            vis[i]=true;
            if(i<n) ++L;
            else ++R;
            while(!que.empty())
            {
                int v=que.front();
                que.pop();
                rep(j,G[v].size())
                {
                    int nx=G[v][j];
                    if(!vis[nx])
                    {
                        vis[nx]=true;
                        que.push(nx);
                        if(nx<n) ++L;
                        else ++R;
                    }
                }
            }

            if(L==1 && R==0) ++lc;
            else if(L==0 && R==1) ++rc;
            else if(L==R) ans+=L*R;
            else
            {
                l[cc]=L;
                r[cc]=R;
                ++cc;
            }
        }

        //DP
        rep(mask,1<<cc)rep(i,lc+1)rep(j,rc+1) dp[mask][i][j]=INF;
        dp[0][0][0]=0;
        //もらう感じで
        rep(mask,1<<cc)rep(i,lc+1)rep(j,rc+1)
        {
            //独立成分同士を繋ぐ
            if(i>0 && j>0) dp[mask][i][j] = min(dp[mask][i][j], dp[mask][i-1][j-1]+1);

            //部分集合を列挙
            int sub=mask;
            while(sub>0)
            {
                int Lnum=0,Rnum=0;
                rep(k,cc)
                {
                    if(sub&(1<<k))
                    {
                        Lnum += l[k];
                        Rnum += r[k];
                    }
                }

                //両者の個数を揃える
                int ti=i, tj=j;
                if(Lnum < Rnum) ti -= Rnum-Lnum;
                if(Lnum > Rnum) tj -= Lnum-Rnum;

                int cost=max(Lnum, Rnum);
                //更新
                if(ti>=0 && tj>=0) dp[mask][i][j]=min(dp[mask][i][j], dp[sub^mask][ti][tj]+cost*cost);

                sub = (sub-1)&mask;
            }
        }

        //output
        printf("Case #%d: %d\n", T+1, ans+dp[(1<<cc)-1][lc][rc]-edge);
    }
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Round2 D - Freeform Factory

問題

問題概要

アイデア

証明

問題の考察

実装(C++)