問題

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

解法

偶数枚のコインが置かれたマスの数の最大値について、偶奇の性質から、以下の雑な見積もりができます。

全コインの枚数が偶数ならば高々HW
全コインの枚数が奇数ならば高々HW-1

そして実はこの雑な見積もりはタイトです。すなわち、全コインの枚数が偶数ならば各マスに置かれたコインの枚数を偶数枚にでき、そうでなくとも、1マスを除いて、各マスに置かれたコインの枚数を偶数枚にできます。

最初に、そのようなコインの配置を実現する手順を述べます。

マス(1, 1)に置かれたコインの枚数が奇数ならば、マス(1, 2)にコインを1枚移す
マス(1, 2)に置かれたコインの枚数（マス(1, 1)から移されたコインも含めてカウント）が奇数ならば、マス(1, 3)にコインを1枚移す
...
マス(1, W-1)に置かれたコインの枚数が奇数ならば、マス(1, W)にコインを1枚移す
マス(1, W)に置かれたコインの枚数が奇数ならば、マス(2, W)にコインを1枚移す
マス(2, 1)に置かれたコインの枚数が奇数ならば、マス(2, 2)にコインを1枚移す
マス(2, 2)に置かれたコインの枚数が奇数ならば、マス(2, 3)にコインを1枚移す
...
マス(2, W-1)に置かれたコインの枚数が奇数ならば、マス(2, W)にコインを1枚移す
マス(2, W)に置かれたコインの枚数が奇数ならば、マス(3, W)にコインを1枚移す
...
マス(H, 1)に置かれたコインの枚数が奇数ならば、マス(H, 2)にコインを1枚移す
マス(H, 2)に置かれたコインの枚数が奇数ならば、マス(H, 3)にコインを1枚移す
マス(H, W-1)に置かれたコインの枚数が奇数ならば、マス(H, W)にコインを1枚移す

AAで表すと以下のイメージです。

→→→...→→↓
→→→...→→↓
...
→→→...→→↓
→→→...→→終

上記手順により、マス(H, W)以外のマスに置かれたコインの枚数は偶数になることは明らかです。それでは、マス(H, W)に置かれたコインの枚数の偶奇はどうなるでしょうか。

全コインの枚数が偶数ならば、他のマスのコインはすべて偶数なので、マス(H, W)に置かれたコインの枚数も偶数です。
全コインの枚数が奇数ならば、他のマスのコインはすべて偶数なので、マス(H, W)に置かれたコインの枚数は奇数です。

したがって、最初の雑な見積もりはタイトであることが分かりました。

ACしたコード

この問題も、計算量の都合を考えると、宣言的にプログラミングするのは難しいですね。

H, W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]
ans = []
for i in range(H):
    for j in range(W):
        if a[i][j] % 2 == 1:
            a[i][j] -= 1
            if j < W - 1:
                ans.append((i + 1, j + 1, i + 1, j + 2))
                a[i][j + 1] += 1
            elif i < H - 1:
                ans.append((i + 1, j + 1, i + 2, j + 1))
                a[i + 1][j] += 1
print(len(ans))
for y, x, y_, x_ in ans:
    print(y, x, y_, x_)

024号文書

主にプログラミング

ABC109 D - Make Them Even

問題

解法

ACしたコード