✨
ABC109 D - Make Them Even解説[python]
URL
問題概要
- H*Wのgridがある。(i,j)のマスにはa[i][j]の値を初期値としてもつ
- 以下の操作を回数に上限なく行い偶数の値を持つマスの数を最大化したい
- 操作：まだ選んだことのないマスのうち1以上の値を持つマスを選びそのマスの値を１減らし、上下左右のいずれかのマスの値を1増やす
- 偶数の値を持つマスの数を最大化するような操作の仕方を出力せよ
提出コード
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
out = []
cnt = 0
for i in range(h):
for j in range(w - 1):
if a[i][j] % 2:
out.append([i + 1, j + 1, i + 1, j + 2])
a[i][j + 1] += 1
cnt += 1
for i in range(h - 1):
if a[i][w - 1] % 2:
out.append([i + 1, w, i + 2, w])
a[i + 1][w - 1] += 1
cnt += 1
print(cnt)
for i in range(cnt):
print(*out[i])
考察
- 直感的にほとんど全てのマスを偶数にできそうだと思ったので操作の性質を考える
- 性質を考えるとまず全体のマスの値の合計値は変わらない
- 行、列の中で全体のマスの偶奇が保存されるわけではない（自由に変更できる）
- 操作の自由度の高さから偶数の数は全体のsumが偶数なら全てのマス、奇数なら1つを除いた全てのマスできそうだと考えた
- 構築系の問題なので、それを満たしそうな操作をシンプルなものから考えてみる
- 端から（左上から）奇数のマスがあれば右のマスに値を1移す
- 行ごとに見て奇数の数が偶数個なら右端a[i][w-1]が奇数になる
- 行ごとの操作が全て終わった後に右端の列だけ見て同様に奇数のますを下に移す
- 操作の制限としては、1以上の値のマスを選ぶこと（奇数しか選ばないので条件を満たす）、同じマスは一回以下しか選ばないこと（右端は最後の操作以外では一回も選ばないのでOK）
実装方針
- 操作を素直に実装すれば良い
- gridの値を順次更新する
メモ
- 構築系は苦手だけど、これはすぐに解放が思いついた
- できるだけ端から見るなどシンプルな手法をまず考える
- 全体の操作回数を出力することを忘れていてWAをだしまくったので注意
Discussion