結果
| 問題 |
No.283 スライドパズルと魔方陣
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:22:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,491 bytes |
| コンパイル時間 | 210 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 77,184 KB |
| 最終ジャッジ日時 | 2025-05-14 13:24:55 |
| 合計ジャッジ時間 | 7,041 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 WA * 17 |
ソースコード
import sys
def solve():
N = int(sys.stdin.readline())
grid_input = []
for _ in range(N):
grid_input.append(list(map(int, sys.stdin.readline().split())))
if N == 2:
print("impossible")
return
# Memoization for inversion counting can speed it up if called with same tile list
memo_inversions = {}
def count_inversions(arr_tuple):
if arr_tuple in memo_inversions:
return memo_inversions[arr_tuple]
arr = list(arr_tuple)
n_len = len(arr)
inv_count = 0
for i in range(n_len):
for j in range(i + 1, n_len):
if arr[i] > arr[j]:
inv_count += 1
memo_inversions[arr_tuple] = inv_count
return inv_count
def get_solvability_invariant(current_grid, n_val, is_initial_puzzle_state):
tiles = []
entity_r, entity_c = -1, -1
n_sq_val = n_val * n_val
for r_idx in range(n_val):
for c_idx in range(n_val):
val = current_grid[r_idx][c_idx]
if is_initial_puzzle_state: # 0 is the blank
if val == 0:
entity_r, entity_c = r_idx, c_idx
else:
tiles.append(val)
else: # Target magic square, N^2 is the "blank"
if val == n_sq_val:
entity_r, entity_c = r_idx, c_idx
else:
tiles.append(val)
inversions = count_inversions(tuple(tiles))
entity_row_from_bottom = n_val - 1 - entity_r # 0-indexed from top, convert to 0-indexed from bottom
if n_val % 2 == 1: # N is odd
return inversions % 2
else: # N is even
return (inversions + entity_row_from_bottom) % 2
invariant_initial = get_solvability_invariant(grid_input, N, True)
def generate_magic_square(n_gen):
if n_gen == 0: return []
if n_gen == 1: return [[1]]
mg_square = [[0 for _ in range(n_gen)] for _ in range(n_gen)]
if n_gen % 2 == 1: # Odd N
r, c = 0, n_gen // 2
num = 1
while num <= n_gen * n_gen:
mg_square[r][c] = num
num += 1
r_prev, c_prev = r, c
r = (r - 1 + n_gen) % n_gen
c = (c + 1 + n_gen) % n_gen
if mg_square[r][c] != 0:
r = (r_prev + 1) % n_gen
c = c_prev
elif n_gen % 4 == 0: # Doubly Even N
for r_idx in range(n_gen):
for c_idx in range(n_gen):
mg_square[r_idx][c_idx] = (r_idx * n_gen) + c_idx + 1
for r_idx in range(n_gen):
for c_idx in range(n_gen):
if (r_idx % 4 == c_idx % 4) or ((r_idx % 4) + (c_idx % 4) == 3):
mg_square[r_idx][c_idx] = (n_gen * n_gen + 1) - mg_square[r_idx][c_idx]
else: # Singly Even N (N % 4 == 2) - Strachey's method
m = n_gen // 2
def make_odd_sub_square(size, start_val_offset):
sub_sq = [[0 for _ in range(size)] for _ in range(size)]
r_s, c_s = 0, size // 2
curr_num_in_sub = 1
while curr_num_in_sub <= size * size:
sub_sq[r_s][c_s] = curr_num_in_sub + start_val_offset
curr_num_in_sub += 1
r_s_prev, c_s_prev = r_s, c_s
r_s = (r_s - 1 + size) % size
c_s = (c_s + 1 + size) % size
if sub_sq[r_s][c_s] != 0:
r_s = (r_s_prev + 1) % size
c_s = c_s_prev
return sub_sq
s1_vals = make_odd_sub_square(m, 0)
s2_vals = make_odd_sub_square(m, m*m)
s3_vals = make_odd_sub_square(m, 2*m*m)
s4_vals = make_odd_sub_square(m, 3*m*m)
for r_idx in range(m):
for c_idx in range(m):
mg_square[r_idx][c_idx] = s1_vals[r_idx][c_idx]
mg_square[r_idx][c_idx+m] = s3_vals[r_idx][c_idx]
mg_square[r_idx+m][c_idx] = s4_vals[r_idx][c_idx]
mg_square[r_idx+m][c_idx+m] = s2_vals[r_idx][c_idx]
k_strachey = (m - 1) // 2
for r_s_idx in range(m):
for c_s_idx in range(k_strachey):
mg_square[r_s_idx][c_s_idx], mg_square[r_s_idx+m][c_s_idx] = \
mg_square[r_s_idx+m][c_s_idx], mg_square[r_s_idx][c_s_idx]
middle_col_sub_idx = m // 2
for r_s_idx in range(m):
if r_s_idx != (m // 2):
mg_square[r_s_idx][middle_col_sub_idx], mg_square[r_s_idx+m][middle_col_sub_idx] = \
mg_square[r_s_idx+m][middle_col_sub_idx], mg_square[r_s_idx][middle_col_sub_idx]
for r_s_idx in range(m):
for c_offset in range(k_strachey):
c_s_idx_in_subgrid = (m - 1) - c_offset
global_c_idx_for_s3s2_part = c_s_idx_in_subgrid + m
mg_square[r_s_idx][global_c_idx_for_s3s2_part], mg_square[r_s_idx+m][global_c_idx_for_s3s2_part] = \
mg_square[r_s_idx+m][global_c_idx_for_s3s2_part], mg_square[r_s_idx][global_c_idx_for_s3s2_part]
return mg_square
candidate_magic_squares = []
m_canonical = generate_magic_square(N)
candidate_magic_squares.append(m_canonical)
if N > 0: # Check N>0 to avoid issues with N=0 if it were possible
m_reflected = [[0 for _ in range(N)] for _ in range(N)]
is_different = False
for r_idx in range(N):
for c_idx in range(N):
m_reflected[r_idx][c_idx] = m_canonical[r_idx][N - 1 - c_idx]
if m_reflected[r_idx][c_idx] != m_canonical[r_idx][c_idx]:
is_different = True
if is_different:
candidate_magic_squares.append(m_reflected)
for ms_candidate in candidate_magic_squares:
invariant_magic_square = get_solvability_invariant(ms_candidate, N, False)
if invariant_initial == invariant_magic_square:
print("possible")
for r_idx in range(N):
print(*(ms_candidate[r_idx]))
return
print("impossible")
solve()