2630.色紙を作る

8046 ワード
Problem Solving テキストリンク

質問する


白準2630号カラーペーパーを作る

に答える


分割征服アルゴリズムは久しぶりで、解法をすっかり忘れてしまいました...
統合ソートアルゴリズムを見て概念を再認識し、
ステータスツリーを描き終わってから、コードの編成方法を考えます.
再帰的検索により,白と青の合計紙数を算出した.
同じ色でなければ4つの色紙に分かれているので、ステータスツリーも4本の枝を伸ばしています.
f(size, x, y)〜sizeは領域のサイズであり、x, yは領域の開始インデックスである.sizeが1になると、その領域の色が返される.
4つの領域の戻り値は、リストareaに保存される.
値が同じ場合は->領域の色を返します
同じ値でなければ->白と青の個数を足す
すべての検索が完了すると、メイン関数で呼び出されたf(n, 0, 0)が終了すると、最後の値last_valの結果に従って、1はblue、0はwhiteに1が加算されます.
import sys

def f(size, x, y):
    global white, blue
    if size == 1: return board[x][y]
    else:
        nxt_n = size // 2
        area = [0, 0, 0, 0]
        area[0] = f(nxt_n, x, y)
        area[1] = f(nxt_n, x, y + nxt_n)
        area[2] = f(nxt_n, x + nxt_n, y)
        area[3] = f(nxt_n, x + nxt_n, y + nxt_n)
        if all(x == 1 for x in area) or all(x == 0 for x in area): return area[0]
        else:
            white += area.count(0)
            blue += area.count(1)
            return -1

n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
white, blue = 0, 0
last_val = f(n, 0, 0)
if last_val == 1: blue += 1
elif last_val == 0: white += 1
print(f'{white}\n{blue}')
7月6日(レイアウト)
codevs 1080セグメントツリー練習(基本テンプレート単点修正区間加算)