AtCoder ABC 109 D - Make Them Even (緑色, 400 点)

最初は「一度選んだマスを使えない」を完全に呼び飛ばしてしまった上に、それに気づいた後も「奇数マス同士をマッチングして、うまく経路を設定する」という方向の考察をしまくって、上手くいかずに迷走した...

問題へのリンク

問題概要

縦 行、横 列に区切られたマス目があってマス には 枚のコインが置かれている。以下の操作を何度でも行うことができて、偶数枚のコインが置かれたマスの数を最大化せよ:

• まだ選んだことのないマスのうち 1 枚以上のコインが置かれているマスを 1 つ選び、そのマスに置かれているコインのうち 1 枚を上下左右に隣接するいずれかのマスに移動する

またその操作を復元せよ。

解法

• 
• 

考えたこと

偶数奇数だけが重要なので、コインの枚数は「0 (偶数は全部 0)」か「1 (奇数は全部 1)」という風に考えても同じ。

そして操作は

• 奇数マスを上下左右に移動させて、他の奇数マスに接触すると相殺できる

という風に考えることができる。

• 奇数が偶数個のとき、奇数同士をペアにして、奇数を消滅させられる
• 奇数が奇数個のとき、1 個を除いて奇数を消滅させられる

という風にできそうである。実際にできる方法として、

ABC 109 お疲れ様でしたー！！！

A：A × B の偶奇を判定
B：慎重に頑張る
C：GCD(x1-X, x2-X, ..., xN-X)
D：ジグザグに道を予め設定しておいて、その道順に「奇数」を回収したら次の「奇数」まで運ぶ、を繰り返した

(が、D は「一度選んだマスはダメ」という条件に気づかずにひたすら迷走した)

— けんちょん (@drken1215) 2018年9月8日

のようにすればいい。

#include <iostream>
#include <vector>
using namespace std;

typedef pair<int,int> pint;
typedef pair<pint,pint> ppint;

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int> > a(H, vector<int>(W, 0));
    int odd = 0;
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) {
        cin >> a[i][j];
        if (a[i][j] & 1) ++odd;
    }
    
    vector<ppint> res;
    int num = 0;
    int x = 0, y = 0;
    for (int iter = 0; iter < W*H; ++iter) {
        if (a[x][y] & 1) ++num;
            
        int nx = x, ny = y;
        if (x % 2 == 0) {
            if (ny == W-1) ++nx;
            else ++ny;
        }
        else {
            if (ny == 0) ++nx;
            else --ny;
        }
        if (num & 1) if (num < odd) res.push_back(ppint(pint(x, y), pint(nx, ny)));
        x = nx, y = ny;
    }
        
    cout << res.size() << endl;
    for (auto p : res) {
        cout << p.first.first+1 << " " << p.first.second+1 << " " << p.second.first+1 << " " << p.second.second+1 << endl;
    }
}