WARush

SRMの結果とか、解けた問題のコードを書いていきます

AtCoder Regular Contest #013 D "切り分けできるかな?"

ACしてるソースコードをカンニング

Komakiさんのソースコードを参考にさせて頂きましたm(_ _)m

  • 基本的な考察

例えば 3*4*5の塊があったとする。

3*4の部分を断面として切っていくと
12 24 36 48の重さのものが作れる

3*5の部分を断面として切っていくと
15 30 45の重さのものが作れる

4*5の部分を断面として切っていくと
20 40の重さのものが作れる

まとめると、12 15 20 24 30 36 40 45 48の9種類の重さが作れる。

高橋君、又は青木君にとって足りない重さのものを作るように切っていけば、
何も考えなくても9 * 2で18回切れば重りが揃うことになる。
つまり、塊を切ると左右に分かれる。その左側の塊を、
必要とされている重さになるように切ればオーケーだ。
しかし、これだと材料を最小にできない。

そこで切って2つになった塊を、左側だけでなく、右側も利用する事を考える。
左側を高橋君。右側を青木君に使ってもらうことにする。
3*4*5で考えると

断面 左(高橋君) 右(青木君)
3*4 12 48
24 36
36 24
48 12
3*5 15 45
30 30
45 15
4*5 20 40
40 20

この例だと左と右の塊が常に利用できたので、
材料は9個あれば済むことになる。
つまり、左右ペアで使えれば材料を1つ節約できるのだ。
今回は9個ペアを作れたので、18 - 9 で材料は9個になる。


3*4*5と2*3*4の塊で考えてみる。
簡単のために1つ目の3*4の断面と2つ目の2*3の断面だけに焦点をあてる。
1つ目で3*4を断面にすると
12 24 36 48が作れる。
2つ目で2*3を断面にすると
6 12 18が作れる
よって、作る重さは6 12 18 24 36 48になる。

ここで、1つ目から切っていくと

断面 左(高橋君) 右(青木君)
3*4 12 48
24 36
36 24
48 12
2*3 6 18
18 6

となり、6個ペアを作れ、材料が6個で済むのだが、
2つ目から切っていくと

断面 左(高橋君) 右(青木君)
2*3 6 18
12 12
18 6
3*4 12(無駄) 48
24 36
36 24
48 12(無駄)

5個しかペアが作れず、材料が7個必要になってしまう。
ペアを最大限作るにはどうしたらよいか、という問題となる。

  • グラフにして考える

これをグラフで表すと、まずこんな感じで求めている重さがある。
f:id:Ekaing:20130318235913j:plain


そして、ペアで作る事ができる重さを線で結ぶ
f:id:Ekaing:20130319000025j:plain


例えば、24 36をペアで作るとこんな感じになる
f:id:Ekaing:20130319000140j:plain


そして、さっきの材料が無駄になってしまったのはこんな感じになったから
f:id:Ekaing:20130319000222j:plain


1つ目から切ると、ペアを最大限作れるようになる。
f:id:Ekaing:20130319000354j:plain

  • 2部グラフの最大マッチング問題

これは、高橋君、または青木君で重さを共有しないように、
ペアを最大いくつ作れるか?ということなので、
2部グラフの最大マッチング問題に帰着できる。(蟻本P.195)

この例だと下図のように始点(S)と終点(T)を置いて、
全ての辺の容量を1にしてから最大流を求めれば、最大のペア数が求まる。
f:id:Ekaing:20130319140035j:plain


作らなければいけない数からペア数を引けば問題の答えとなる。

事後

最大流の実装って難しいなぁ・・・
あと、重さの種類が最大10000種類超えるから、
2次元配列でグラフもつとダメだったよ・・・

ソースコード
class E{
public:
    E( int _to, bool _can, int _rev ):to(_to),can(_can),rev(_rev){}
    int to, rev;
    bool can;
};

vector<E> G[13000];
bool used[13000];

// vからtまで流せたか?
bool max_flow_dfs(int v, int t){
    if( v == t ) return true;
    
    used[v] = true;
    // どこに流そうかな~
    for( int i = 0; i < G[v].size(); i++ ){
        E& e = G[v][i];
        if( !e.can || used[e.to] ) continue;
        // ここや!
        bool res = max_flow_dfs( e.to, t );
        if( res ){
            // 流せたら辺を閉じ、逆辺を開く
            e.can = false;
            G[e.to][e.rev].can = true;
            return true;
        }
    }
    return false;
}

// SからTへの最大流を求める
int max_flow(int s, int t){
    int flow = 0;
    while( true ){
        memset( used, false, sizeof(used) );
        bool res = max_flow_dfs(s, t);
        if( !res ) return flow;
        flow++;
    }
}

int main() {

    int N;
    cin >> N;

    // 塊の情報を入力
    vector<vector<int> > L(N, vector<int>(3, 0));
    for( int i = 0; i < N; i++ ){
        for( int j = 0; j < 3; j++ ){
            cin >> L[i][j];
        }
    }

    // 作らなくちゃいけない重さを初期化
    vector<int> g;
    for( int i = 0; i < N; i++ ){
        for( int j = 0; j < 3; j++ ){
            int b = 1;
            for( int k = 0; k < 3; k++ ){
                if( j != k ) b *= L[i][k];
            }
            for( int k = 1; k < L[i][j]; k++ ){
                g.push_back( b * k );
            }
        }
    }
    sort( g.begin(), g.end() );
    g.erase( unique(g.begin(), g.end()), g.end() );
    int gSize = g.size();

    // 重さにインデックスをつける
    map<int, int> ids;
    for( int i = 0; i < gSize; i++ ){
        ids[g[i]] = i;
    }

    // 辺を初期化
    for( int i = 0; i < N; i++ ){
        for( int j = 0; j < 3; j++ ){
            int b = 1;
            for( int k = 0; k < 3; k++ ){
                if( j != k ) b *= L[i][k];
            }
            for( int k = 1; k < L[i][j]; k++ ){
                int g1 = b * k;
                int g2 = b * (L[i][j] - k);
                int id1 = ids[g1];
                int id2 = ids[g2] + gSize;
                G[id1].push_back(E(id2, true, G[id2].size()));
                G[id2].push_back(E(id1, false, G[id1].size()-1));
            }
        }
    }

    // 2部マッチングの始点と終点の辺を追加
    int S = gSize * 2;
    int T = gSize * 2 + 1;
    for( int i = 0; i < gSize; i++ ){
        G[S].push_back(E(i, true, G[i].size()));
        G[i].push_back(E(S, false, G[S].size()-1));
    }
    for( int i = gSize; i < gSize * 2; i++ ){
        G[i].push_back(E(T, true, G[T].size()));
        G[T].push_back(E(i, false, G[i].size()-1));
    }

    // 最大流で最大ペアを求めてそれを引く
    int res = gSize * 2 - max_flow(S, T);
    
    cout << res << endl;
}