結果

問題 No.2797 Square Tile
コンテスト
ユーザー navel_tos
提出日時 2024-06-29 15:21:20
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,767 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 849,352 KB
最終ジャッジ日時 2024-06-29 15:21:24
合計ジャッジ時間 2,334 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 MLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 2797 Square Tile

import random, math

#愚直判定
def check(A, B, A_list, B_list):
    L = A ** 2 + B ** 2
    if not len(A_list) == len(B_list) == L:
        return False
    if not all(i in range(L) and j in range(L) for i, j in A_list + B_list):
        return False
    D = [[0] * L for _ in range(L)]
    for i, j in A_list:
        for x in range(i, i + A):
            x %= L
            for y in range(j, j + A):
                y %= L
                if D[x][y] == 1: return False
                D[x][y] = 1
    for i, j in B_list:
        for x in range(i, i + B):
            x %= L
            for y in range(j, j + B):
                y %= L
                if D[x][y] == 1: return False
                D[x][y] = 1
    return True

#タイルA_listが定められていると仮定する。B_listを愚直に作成せよ。
def fill(A, B, A_list):
    L = A ** 2 + B ** 2
    if not len(A_list) == L:
        return []
    if not all(i in range(L) and j in range(L) for i, j in A_list):
        return []
    D = [[0] * L for _ in range(L)]
    for i, j in A_list:
        for x in range(i, i + A):
            x %= L
            for y in range(j, j + A):
                y %= L
                if D[x][y] == 1: return []
                D[x][y] = 1
    B_list = []
    while len(B_list) < L:
        for i in range(L):
            for j in range(L):
                if D[i][j] == 0 and D[(i - 1) % L][j] == D[i][(j - 1) % L] == 1:
                    B_list.append((i, j))
                    for x in range(i, i + B):
                        x %= L
                        for y in range(j, j + B):
                            y %= L
                            if D[x][y] == 1: return []
                            D[x][y] = 1
    return B_list


#乱択解法
def solve_random(A, B):
    L = A ** 2 + B ** 2
    while True:
        A_list = [(random.randint(0, L - 1), random.randint(0, L - 1))
                  for _ in range(L - 1)] + [(0, 0)]
        B_list = fill(A, B, A_list)
        if len(B_list) == L:
            assert check(A, B, A_list, B_list)
            visualize(A, B, A_list, B_list)
            return A_list, B_list

def visualize(A, B, A_list, B_list):
    L = A ** 2 + B ** 2
    D = [[None] * L for _ in range(L)]
    for i, j in A_list:
        for x in range(i, i + A):
            x %= L
            for y in range(j, j + A):
                y %= L
                D[x][y] = 'a'
        D[i][j] = 'A'
    for i, j in B_list:
        for x in range(i, i + B):
            x %= L
            for y in range(j, j + B):
                y %= L
                D[x][y] = 'b'
        D[i][j] = 'B'
    for d in D:
        print(''.join(d))


#実験結果を採用
#答えとなる盤面を出力せよ。
def solve(A, B):
    L = A ** 2 + B ** 2
    if math.gcd(A, B) == 1:
        A_list = []
        B_list = []
        for i in range(L):
            A_list.append((A * i % L, B * i % L))
            B_list.append((A * (i + 1) % L, B * i % L))
        return A_list, B_list
    else:
        G = math.gcd(A, B)
        H = L // G
        a_list, b_list = solve(A // G, B // G)
        A_list = [(H * i + G * x, H * j + G * y)
                  for x, y in a_list for i in range(G) for j in range(G)]
        B_list = [(H * i + G * x, H * j + G * y)
                  for x, y in b_list for i in range(G) for j in range(G)]
        return A_list, B_list
    

def test(A, B):
    A_list, B_list = solve(A, B)
    visualize(A, B, A_list, B_list)
    

#答えを実行
A, B = map(int, input().split())
A_list, B_list = solve(A, B)

#愚直で片方のリストを再生成してみる
if A < B: A_list = fill(B, A, B_list)
else:     B_list = fill(A, B, A_list)

#出力
for i, j in A_list + B_list: print(i, j)
0