けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題へのリンク

問題概要 (ABC 109 D)

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

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

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

解法

  •  1 \le H, W \le 500
  •  0 \le a_i \le 9

考えたこと

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

そして操作は

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

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

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

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

のようにすればいい。

#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;
    }
}