結果
問題 | No.2958 Placing Many L-s |
ユーザー |
![]() |
提出日時 | 2025-01-11 20:14:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 4,663 bytes |
コンパイル時間 | 530 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 80,384 KB |
最終ジャッジ日時 | 2025-01-11 20:14:21 |
合計ジャッジ時間 | 9,413 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
#yukicoder2958 Placing Many L-s#実験コードを書くdef brute(H, W):def make_valid():block = []for G in ([[1, 1, 1], [x, 0, x ^ 1], [0, 0, 0]] for x in range(2)):for _ in range(4):G = [[G[h][~ w] for h in range(3)] for w in range(3)]for i, (h, w) in enumerate([(h, w) for h in range(3) for w in range(3)]):if G[h][w] == 1:breakH = []for x in range(3):for y in range(3):if G[x][y] == 1:H.append((x - h, y - w))block.append(H)return blockblock = make_valid()#非再帰DFSで全列挙 左上詰で置いたときに最初の空きマスが(h, w)で、block[t]を置く予定G = [[0] * W for _ in range(H)]stack = [(0, 0, t) for t in range(8)]d = 0 #再帰の深さwhile stack:h, w, t = stack.pop()if h >= 0: #行きがけの処理#1. 実際に置けるか判定。置けないならcontinue 置けるなら実際に配置if not all( (x := h + p) in range(H) and (y := w + q) in range(W) andG[x][y] == 0 for p, q in block[t] ):continued += 1stack.append((~ h, w, t))for p, q in block[t]:assert G[ x := h + p ][ y := w + q ] == 0G[x][y] = d#2. 次の探索へa = h * W + wfor a in range(a + 1, H * W + 1):if a == H * W:breakx, y = a // W, a % Wif G[x][y] == 0:breakif a == H * W: #完全に置き切れた場合assert all( G[h][w] > 0 for h in range(H) for w in range(W) ), str(G)return Gx, y = a // W, a % Wfor u in range(8):stack.append((x, y, u))else: #帰りがけの処理h = ~ h#1. 既に置いた石を除去for p, q in block[t]:assert G[ x := h + p ][ y := w + q ] == dG[x][y] = 0d -= 1else: #だめでしたreturn G#H, Wのうち、Hが偶数になるように適宜変更する。#H ≡ 0 mod 8: W >= 2で常に可能。(8, 2), (8, 3)の構築を並べる#H ≡ 4 mod 8: Wが偶数なら可能。(4, 2)を並べる#H ≡ 2, 6 mod 8: Wが4の倍数なら可能。(W, H)を90度回転させる#結局 (4, 2), (8, 2), (8, 3)を使って構築すればよいと分かるtiles = [[None] * 9 for _ in range(9)]for h, w in [(4, 2), (8, 2), (8, 3)]:tiles[h][w] = brute(h, w)def rotate(G):if len(G) == 0:return []else:return [[G[h][~ w] for h in range( len(G) )] for w in range( len(G[0]) )]def solve(H, W):if H & 1 == W & 1 == 1:return []if H & 1:return rotate( solve(W, H) )#1. H ≡ 0 mod 8 を構築するif H % 8 == 0:if W == 1:return []G = [[0] * W for _ in range(H)]offset = 0 #既に置いた値for h in range(0, H, 8):if W & 1: #(8, 3)構築を置くbase = tiles[8][3]for x in range(8):for y in range(3):G[h + x][0 + y] = base[x][y] + offsetoffset += 6for w in range( (3 if W & 1 else 0), W - 1, 2 ):base = tiles[8][2]for x in range(8):for y in range(2):G[h + x][w + y] = base[x][y] + offsetoffset += 4return G#2. H ≡ 4 mod 8 を構築するif H % 8 == 4:if W & 1 == 1:return []G = [[0] * W for _ in range(H)]offset = 0base = tiles[4][2]for h in range(0, H, 4):for w in range(0, W, 2):for x in range(4):for y in range(2):G[h + x][w + y] = base[x][y] + offsetoffset += 2return G#3. H ≡ 2, 6 mod 8 を構築するif H % 8 in [2, 6]:return rotate( solve(W, H) ) if W % 4 == 0 else []return []#実行 エスパーしたけどおもしろかったfor _ in range( T := int(input()) ):H, W = map(int, input().split())G = solve(H, W)if G == []:print(-1)else:print(H * W // 4)for h in range(H):print(*G[h])