思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder Beginner Contest 109 D - Make Them Even

目次

結論

  • 奇数枚のマスのコインを,別の奇数の枚数のコインがあるマスに移動させる.

  • 一筆書きの要領で,すべてのマスをチェックする.

はじめに

  • AtCoderで出題された問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います.

想定読者

  • 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.

筆者の実力

記事の特徴

  • なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.

  • 試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

D - Make Them Even (400点)

発想・解法とそれらを引きだすための方法・解釈

  • 最初の一歩は?

    • 出力すべきなのは,条件に該当するマスが最大となるときの,操作回数とその手順である.
  • 奇数枚のコインがあるマスから1枚を,別の奇数枚のコインあるマスに移動させることで,両方とも偶数枚にできる.このため,奇数枚のコインがあるマスが偶数なら,すべて偶数にできる.一方で,奇数枚のコインがあるマスが奇数なら,1か所だけ奇数枚のままになる.

  • 考察のキモ(Key Insight)は?

    • 操作の手順としては,奇数枚のあるマスから,まだチェックしていないマスかつ奇数枚の部分があれば,1枚移動させる.これを一筆書きの要領で繰り返す.
  • どうしたら思いつけそうか?

    • 端から条件を満たすように操作を行う.これを「条件を満たさない部分を別の部分に移動させる」と言い換える.
  • 実装のポイントは?

    • 各行で,奇数枚のマスがあれば,現在のマスからすぐ右のマスへコインを1枚移動させる.左端から右端まで繰り返す.

    • 右端に奇数枚のマスが固まっているため,上から下へ見ることを繰り返す.

Python3による回答例

# -*- coding: utf-8 -*-


def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    operations = list()

    # See:
    # https://atcoder.jp/contests/abc109/submissions/3154532
    for row in range(h):
        for col in range(w - 1):
            if a[row][col] % 2 == 1:
                operations.append((row + 1, col + 1, row + 1, col + 2))
                a[row][col] -= 1
                a[row][col + 1] += 1

    for row in range(h - 1):
        if a[row][w - 1] % 2 == 1:
            operations.append((row + 1, w, row + 2, w))
            a[row][w - 1] -= 1
            a[row + 1][w - 1] += 1

    n = len(operations)
    print(n)

    for i in range(n):
        y, x, y_dash, x_dash = operations[i]
        print(y, x, y_dash, x_dash)


if __name__ == '__main__':
    main()

得られた知識・知見

  • 端から条件を満たすように,条件に合わない部分をほかの場所へ移せばよい,という考え方.

感想

  • 手順を出力せよという形式について,より精進が必要だと思いました.

  • 解説されればできそうな気がしますが,自力で思いつくところに特にハードルが高いように感じました.

  • 実装においても,解説ACした解法はかなり冗長になってしまいました.コンテスト本番で上位に入られていた方の実装を写経したところ,かなりシンプルな実装で感動しました.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/06/20 作成
  • 2019/0x/xx 更新