mayoko’s diary

プロコンとかいろいろ。

天下一プログラマーコンテスト2015予選A C - 天下一美術館

天下一プログラマーコンテスト2015予選Aに参加しました。天下一完でした。別に予選通過できるとは思ってないけどもうちょっと解けないかなぁ…

解法

基本的に,AとBで一致している部分は交換する必要も色を入れ替える必要もありません(そうしないほうが得)。
また,色を2回以上移動させることは損なのでやる必要がありません(2回以上色を交換するなら,それぞれの色を変更すれば良い)。

そこで,色が一致していない部分について,隣あったセルと入れ替える,もしくは色を変更する,という操作をすることになります。

また考察ですが,隣り合ったセルを入れ替える場合,どちらか一方だけBと一致しもう一方はBと一致しないというような入れ替え方はやはり2つのセルの両方で色を変更をすれば良いだけなので考えなくて良いです。
つまり,セルを交換する場合は両方のセルが完成図(B)と一致する場合のみです。

こう考えると,なるべくセルを交換してBを作るのが有利であると気づきます(色を変更するのは1回の操作で1つのセルしか合わせられないが,交換するのは1回の操作で2つのセルを合わせられるので)。

この交換の回数をなるべく大きくしたときの交換回数をfとし,AとBで不一致だったセルの数をcntとすると,答えは
f + (cnt - 2*f) = cnt-f
と求められます。

後はこのfを求めれば勝ちですが,これは色を白と黒に分けた時の最大マッチングとして求めることが出来ます。

const int MAXN = 77;
int A[MAXN][MAXN], B[MAXN][MAXN];

// Dinic法:最小カット,最大フローで使う
// 使い方: Dinic* dinic = new Dinic(V)で初期化(Vは頂点数)
// dinic->add_edgeまたはdinic->add_edge_bothで点をつなげてdinic->max_flowで最大フローを求める
#define NG -1
#define SZ(a) ((int)((a).size()))
class Dinic
{
public:
    Dinic(int input_maxv) : maxv(input_maxv)
    {
        G.resize(input_maxv);
        level.resize(input_maxv);
        iter.resize(input_maxv);
    }

    void add_edge_both(int from, int to, int cap)
    {
        const int rev_from  = SZ(G[from]);
        const int rev_to    = SZ(G[to]);
        G[from].push_back(edge(to,cap,rev_to));
        G[to].push_back(edge(from,cap,rev_from));
    }

    void add_edge(int from, int to, int cap)
    {
        const int rev_from  = SZ(G[from]);
        const int rev_to    = SZ(G[to]);
        G[from].push_back(edge(to,cap,rev_to));
        G[to].push_back(edge(from,0,rev_from));
    }

    int max_flow(int s, int t)
    {
        int flow = 0;
        for(;;)
        {
            bfs(s);
            if(level[t]<0) break;
            fill(iter.begin(),iter.end(),0);
            int f;
            while( (f=dfs(s,t,DINIC_INF))>0)
            {
                flow += f;
            }
        }

        return flow;
    }

    vector <bool> get_nodes_in_group(int s)
    {
        vector <bool> ret(maxv);

        queue<int> que;
        que.push(s);
        while(!que.empty())
        {
            int v = que.front();
            que.pop();
            ret[v]=true;

            for(int i=0;i<SZ(G[v]);i++)
            {
                edge &e = G[v][i];
                if(e.cap>0 && !ret[e.to])
                {
                    que.push(e.to);
                }
            }
        }
        return ret;
    }

    void disp()
    {
        for (int v = 0; v < maxv; v++)
        {
            printf("%d:",v);
            for(int i=0;i<SZ(G[v]);i++)
            {
                if(G[v][i].init_cap>0)
                {
                    printf("->%d(%d),",G[v][i].to,G[v][i].init_cap);
                }
            }
            printf("\n");
        }
    }

private:
    void bfs(int s)
    {
        fill(level.begin(),level.end(),NG);
        queue<int> que;
        level[s]=0;
        que.push(s);
        while(!que.empty())
        {
            int v = que.front();
            que.pop();
            for(int i=0;i<SZ(G[v]);i++)
            {
                edge &e = G[v][i];
                if(e.cap>0 && level[e.to]<0)
                {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f)
    {
        if(v==t) return f;
        for (int &i=iter[v];i<SZ(G[v]);i++)
        {
            edge& e = G[v][i];
            if(e.cap>0 && level[v]<level[e.to])
            {
                int d = dfs(e.to, t, min(f, e.cap));
                if(d>0)
                {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    static const int DINIC_INF = INT_MAX;

    struct edge
    {
        edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
        int to;
        int cap;
        int rev;
        int init_cap;
    };

    int maxv;
    vector < vector <edge> > G;
    vector < int > level;
    vector < int > iter;

};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int M, N;
    cin >> M >> N;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> B[i][j];
        }
    }
    int cnt[2] = {0, 0};
    vector<pii> diff[2];
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i][j] != B[i][j]) {
                if (A[i][j] == 0) {
                    cnt[0]++;
                    diff[0].emplace_back(i, j);
                } else {
                    cnt[1]++;
                    diff[1].emplace_back(i, j);
                }
            }
        }
    }
    int s = cnt[0]+cnt[1], t = s+1, V = t+1;
    Dinic dinic(V);
    for (int i = 0; i < cnt[0]; i++) dinic.add_edge(s, i, 1);
    for (int i = 0; i < cnt[1]; i++) dinic.add_edge(cnt[0]+i, t, 1);
    for (int i = 0; i < cnt[0]; i++) for (int j = 0; j < cnt[1]; j++) {
        int y = diff[0][i].first, x = diff[0][i].second;
        int ny = diff[1][j].first, nx = diff[1][j].second;
        if (abs(ny-y)+abs(nx-x) == 1) {
            dinic.add_edge(i, j+cnt[0], 1);
        }
    }
    int f = dinic.max_flow(s, t);
    cout << cnt[0] + cnt[1] - f << endl;
    return 0;
}