Make Them Even [AtCoder Beginner Contest 109 D]

https://beta.atcoder.jp/contests/abc109/tasks/abc109_d

考察過程

1. 400点問題にしては難しい気がする
2. 点数の低い構築は機械的にやれる最適戦略があるイメージ
3. 特に今回は操作回数の最小化は求められてないので、簡単な機械化を目指す
4. すると、奇数の物を右に詰めていって、最後に最右で奇数の物を下に詰めていくと、右下が1になるかならないかになる
5. これを実装する（4を思いつくのが一番むずい）

解法

https://beta.atcoder.jp/contests/abc109/submissions/3163646

二段階に分けて操作を行う。
　
1. 全ての行について奇数の数を右にずらしていく
左から順番に見ていって、奇数の個数であれば、1つ左に移す。
移せば、移した元は偶数になる。
もし、移した先が奇数になってしまった場合は、続けてそれも右にずらしていこう。
これを繰り返すと、各行について最右以外は偶数にできる
　
2. 最右の列について奇数の数を下にずらしていく
上から順番に見ていって、奇数の個数であれば、1つ下に移す
移せば、移した元は偶数になる。
もし、移した先が奇数になってしまった場合は、続けてそれも下にずらしていこう。
これを繰り返すと、全体では右下以外は偶数にできる
　
最終的にできあがる盤面を見てみると、最適解っぽい。
これを実装するとAC。
C++だと答えを保持するとにtupleを使うのが良い。

int H, W, A[505][505];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];
 
    vector<tuple<int, int, int, int>> ans;
    rep(y, 0, H) rep(x, 0, W - 1) {
        if (A[y][x] % 2 == 1) {
            A[y][x]--;
            A[y][x + 1]++;
            ans.push_back(make_tuple(y, x, y, x + 1));
        }
    }
    rep(y, 0, H - 1) {
        if (A[y][W-1] % 2 == 1) {
            A[y][W - 1]--;
            A[y + 1][W - 1]++;
            ans.push_back(make_tuple(y, W - 1, y + 1, W - 1));
        }
    }
 
    int n = ans.size();
    printf("%d\n", n);
    fore(t, ans) {
        int a, b, c, d;
        tie(a, b, c, d) = t;
        printf("%d %d %d %d\n", a + 1, b + 1, c + 1, d + 1);
    }
}