AtCoder Regular Contest 080 D – Grid Coloring をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Regular Contest 080 D – Grid Coloring

入出力例に惑わされず、可能な限り簡単な構造を考察する問題。……いや、別に凝ったのを出力したければ、頑張ってもいいけど……うずまき型とか……。

# AtCoder Regular Contest 080 D - Grid Coloring
# https://atcoder.jp/contests/arc080/tasks/arc080_b
# tag: グリッド 特殊構造

# 同じ色なら全て繋がっている必要がある ＝ 繋がってさえいれば形は問わない
# グリッド全体をひと筆書きできるような経路があれば、
# 一筆書きの各分割区間は連結しているとみなせるので、
# そこに各色を求められる数だけ順番に置いていけばいい。

# たぶん一番簡単で例外がないのが、
# 123
# 654
# 789
# みたいな経路。

# ↑を簡単に作るにはどうしよう……
# 123
# 456
# 789
# みたいに普通に並べてから、一行おきにひっくり返せばいいのでは？

def main():
    H, W = map(int, input().split())
    N = int(input())
    n_by_color = list(map(int, input().split()))

    # とりあえずひとつなぎの配列を作成し、後から整形する
    seq = []
    for c, n in enumerate(n_by_color, start=1):
        for i in range(n):
            seq.append(c)

    # 先程作ったものを、W ごとに H 個に分割しつつ……
    for h in range(H):
        row = seq[h*W:h*W+W]

        # 一行おきにひっくり返しながら出力する
        if h % 2 == 0:
            print(*row)
        else:
            print(*row[::-1])

main()

arc080_d.py view raw

関連

コメントを残すコメントをキャンセル