AtCoder Beginner Contest 109: D - Make Them Even

競技プログラミング AtCoder 二次元グリッド

問題

問題文

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

問題概要

縦 H, 横 W のマス目がある. マス (i, j) には a_{ij} 枚のコインがある.

コイン 1 枚を上下左右のいずれかに移動するという操作を各マスについて 1 回以下行って偶数枚のコインが置かれているマスを最大化せよ.

解答例

指針

  • 一筆書きとなるような経路をなぞりながらコインを移動する

解説

以下のように一筆書きとなるような経路をなぞり奇数枚であれば次のマスに移動するというようなことを繰り返すと偶数枚のマスを最大化できる.

f:id:kira000:20190101123911p:plain

  • C++ による実装例
// submission: https://atcoder.jp/contests/abc109/submissions/3908903
// Language: C++14 (GCC 5.4.1)
// Time: 340 ms
// Memoly: 11892 KB

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int a[505][505];
    int H, W;

    vector<string> ans;

    cin >> H >> W;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> a[i][j];
        }
    }
    int x = 0, y = 0;
    int dx = 1;

    while (true) {
        int nx, ny;
        if (x+dx < 0 || W <= x+dx) {
            nx = x;
            ny = y + 1;
            dx *= -1;
        } else {
            nx = x+dx;
            ny = y;
        }

        if ( H <= ny ) {
            break;
        }
        if ( a[y][x] % 2 == 1 ) {
            a[y][x]--;
            a[ny][nx]++;
            ans.push_back( to_string(y+1) + " " + to_string(x+1) + " "
                    + to_string(ny+1) + " " + to_string(nx+1) );
        }
        x = nx; y = ny;
    }

    cout << ans.size() << endl;

    for (auto i: ans) {
        cout << i << endl;
    }

    return 0;
}
  • Python3 による実装例
# submission: https://atcoder.jp/contests/abc109/submissions/3909266
# Language: Python3 (3.4.3)
# Time: 375 ms
# Memoly: 16344 KB

def main():
    ans, a = [], []
    H, W = map(int, input().split())
 
    for i in range(H):
        a += [list(map(int, input().split()))]
 
    x, y, dx = 0, 0, 1
 
    while True:
        nx, ny = x, y
        if x+dx < 0 or W <= x+dx:
            nx = x
            ny = y+1 
            dx *= -1
        else:
            nx = x+dx
            ny = y
 
        if H <= ny:
            break
 
        if a[y][x] % 2 == 1:
            a[y][x] -= 1
            a[ny][nx] += 1
            ans += [str(y+1) + " " + str(x+1) + " " + str(ny+1) + " " + str(nx+1)]
        x, y = nx, ny
 
    print (len(ans))
 
    for i in ans:
        print (i)
 
main()

別に一筆書きじゃなくても以下のような経路を通っても偶数枚のマスを最大化できる. こちらのほうが若干実装が楽かもしれない.

f:id:kira000:20190101124105p:plain

  • C++ による実装例
// submission: https://atcoder.jp/contests/abc109/submissions/3909409
// Language: C++14 (GCC 5.4.1)
// Time: 338 ms
// Memoly: 11892 KB

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int a[505][505];
    int H, W;
    vector<string> ans;

    cin >> H >> W;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H-1; j++) {
            if (a[j][i] % 2 == 1) {
                a[j][i]--;
                a[j+1][i]++;
                ans.push_back( to_string(j+1) + " " + to_string(i+1) + " "
                        + to_string(j+2) + " " + to_string(i+1) );
            }
        }
    }

    for (int i = 0; i < W-1; i++) {
        if (a[H-1][i] % 2 == 1) {
            a[H-1][i]--;
            a[H-1][i+1]++;
            ans.push_back( to_string(H) + " " + to_string(i+1) + " "
                        + to_string(H) + " " + to_string(i+2) );
        }
    }

    cout << ans.size() << endl;

    for (auto& e: ans) {
        cout << e << endl;
    }

    return 0;
}
  • Python3 による実装例
# submission: https://atcoder.jp/contests/abc109/submissions/3909431
# Language: Python3 (3.4.3)
# Time: 342 ms
# Memoly: 16348 KB

def main():
    ans, a = [], []
    H, W = map(int, input().split())
 
    for i in range(H):
        a += [list(map(int, input().split()))]

    for i in range(W):
        for j in range(H-1):
            if a[j][i] % 2 == 1:
                a[j][i] -= 1
                a[j+1][i] += 1
                ans += [ str(j+1) + " " + str(i+1) + " " + str(j+2) + " " + str(i+1) ]

    for i in range(W-1):
        if a[H-1][i] % 2 == 1:
            a[H-1][i] -= 1
            a[H-1][i+1] += 1
            ans += [ " ".join([str(H), str(i+1), str(H), str(i+2)]) ]
    print (len(ans))
 
    for i in ans:
        print (i)
 
main()

参考文献