結果
| 問題 | No.2257 Swim and Sleep |
| ユーザー |
 shobonvip
|
| 提出日時 | 2023-03-24 06:32:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 436 ms / 2,000 ms |
| コード長 | 6,752 bytes |
| コンパイル時間 | 242 ms |
| コンパイル使用メモリ | 82,128 KB |
| 実行使用メモリ | 80,840 KB |
| 最終ジャッジ日時 | 2024-09-18 15:53:07 |
| 合計ジャッジ時間 | 6,320 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
# コードを綺麗にしたfrom math import gcdfrom collections import defaultdictmod = 998244353# m ... 決まっている鯨の数# rl ... 方向の個数 (長さ 4 の配列)# x ... 鯨の x 座標 (長さ m の配列)# y ... 鯨の y 座標 (長さ m の配列)# r ... 鯨の方向 (長さ m の配列)# w ... 盤面の x 軸の広さ# h ... 盤面の y 軸の広さ# g ... gcd(w, h)# TYPE 1 縦・横のみdef count_type1(m, rl, x, y, r, w, h, g):ret = 0# 横if rl[0] + rl[1] == 0:d = defaultdict(lambda: -1)mode = 1for i in range(m):if d[y[i]] == -1:d[y[i]] = r[i]elif d[y[i]] != r[i]:mode = 0breakif mode:f = len(d)ret += pow(2, h-f, mod)ret %= mod# 縦if rl[2] + rl[3] == 0:d = defaultdict(lambda: -1)mode = 1for i in range(m):if d[x[i]] == -1:d[x[i]] = r[i]elif d[x[i]] != r[i]:mode = 0breakif mode:f = len(d)ret += pow(2, w-f, mod)ret %= modreturn ret# TYPE 2 偶数自明 (g = 0 mod 2)def count_type2(m, rl, x, y, r, w, h, g):ret = 0if g % 2 == 0:# パリティで場合分けするfor parity in range(2):d1 = defaultdict(lambda: -1)d2 = defaultdict(lambda: -1)mode = 1for i in range(m):if r[i] == 0 or r[i] == 1:# 縦if (x[i] + y[i]) % 2 != parity:mode = 0breakif d1[x[i]] == -1:d1[x[i]] = r[i]elif d1[x[i]] != r[i]:mode = 0breakelse:# 横if (x[i] + y[i]) % 2 != 1 ^ parity:mode = 0breakif d2[y[i]] == -1:d2[y[i]] = r[i]elif d2[y[i]] != r[i]:mode = 0breakif mode:ret += pow(2, w-len(d1) + h-len(d2), mod)ret %= modreturn ret# TYPE 3 (x-y)%g で場合分けdef count_type3(m, rl, x, y, r, w, h, g):ret = 0for v in [(1, 3), (0, 2)]:if rl[v[0]] == rl[v[1]] == 0:mode = 1d = defaultdict(lambda:-1)for i in range(m):t = (x[i] - y[i]) % gif d[t] == -1:d[t] = r[i]elif d[t] != r[i]:mode = 0breakif mode:ret += pow(2, g-len(d), mod)ret %= modreturn ret# TYPE 4 (x+y)%g で場合分けdef count_type4(m, rl, x, y, r, w, h, g):ret = 0for v in [(1, 2), (0, 3)]:if rl[v[0]] == rl[v[1]] == 0:mode = 1d = defaultdict(lambda:-1)for i in range(m):t = (x[i] + y[i]) % gif d[t] == -1:d[t] = r[i]elif d[t] != r[i]:mode = 0breakif mode:ret += pow(2, g-len(d), mod)ret %= modreturn ret# TYPE 4.5.1# TYPE 3, 4 のうち, TYPE 1 にあてはまるものを除くdef count_type451(m, rl, x, y, r, w, h, g):ret = 0for v in range(4):if rl[0] + rl[1] + rl[2] + rl[3] - rl[v] == 0:ret -= 2ret %= modreturn ret# TYPE 4.5.2# TYPE 3, 4 のうち, TYPE 2 にあてはまるものを除くdef count_type452(m, rl, x, y, r, w, h, g):ret = 0if g % 2 == 0:for p in range(4):for q in range(4):if p//2 == q//2: continuemode = 1for i in range(m):t = (x[i] + y[i]) % 2if t == 0 and r[i] != p:mode = 0breakif t == 1 and r[i] != q:mode = 0breakif mode:ret -= 1ret %= modreturn ret# 非自明の 48 通りを作るdef make_hijimei():ret = []for num in range(4 ** 8):v = numa = [[0] * 4 for i in range(4)]rl = [0] * 4for i in range(8):t = v % 4v //= 4a[i//4][i%4] = ta[i//4 + 2][(i+2)%4] = trl[t] += 2# 衝突するか否かmode = 1for i in range(4):md = -1for j in range(4):if a[i][j] == 0 or a[i][j] == 1:if md == -1:md = a[i][j]elif md != a[i][j]:mode = 0breakfor j in range(4):md = -1for i in range(4):if a[i][j] == 2 or a[i][j] == 3:if md == -1:md = a[i][j]elif md != a[i][j]:mode = 0breakif mode == 0:continueb = [[0] * 4 for i in range(4)]for i in range(4):for j in range(4):b[i][j] = a[i][j]# 愚直にシミュレーションするfor tyr in range(20):c = [[-1] * 4 for i in range(4)]for i in range(4):for j in range(4):if b[i][j] == 0:if c[i][(j+1)%4] != -1:mode = 0breakc[i][(j+1)%4] = b[i][j]if b[i][j] == 1:if c[i][(j-1)%4] != -1:mode = 0breakc[i][(j-1)%4] = b[i][j]if b[i][j] == 2:if c[(i-1)%4][j] != -1:mode = 0breakc[(i-1)%4][j] = b[i][j]if b[i][j] == 3:if c[(i+1)%4][j] != -1:mode = 0breakc[(i+1)%4][j] = b[i][j]if mode == 0:breakb = c# 衝突しなかった場合, TYPE 1, 2, 3, 4 に当てはまるかを確認if mode:ans = 0m = 16x = [0] * my = [0] * mr = [0] * mrl = [0] * 4for i in range(4):for j in range(4):x[i*4 + j] = iy[i*4 + j] = jr[i*4 + j] = a[i][j]rl[a[i][j]] += 1w = 4h = 4g = 4ans += count_type1(m, rl, x, y, r, w, h, g)ans += count_type2(m, rl, x, y, r, w, h, g)ans += count_type3(m, rl, x, y, r, w, h, g)ans += count_type4(m, rl, x, y, r, w, h, g)ans += count_type451(m, rl, x, y, r, w, h, g)ans += count_type452(m, rl, x, y, r, w, h, g)# TYPE 1, 2, 3, 4 に当てはまらない場合, 非自明if ans == 0:ret.append(a)return ret# 実行！ar = make_hijimei()# TYPE 5# 非自明 48通りを全探索するdef count_type5(m, rl, x, y, r, w, h, g):ret = 0if g % 4 == 0:a = [[-1] * 4 for i in range(4)]mode = 1for i in range(m):if a[x[i]%4][y[i]%4] == -1:a[x[i]%4][y[i]%4] = r[i]elif a[x[i]%4][y[i]%4] != r[i]:mode = 0breakif mode == 0:return 0for b in ar:mode = 1for i in range(4):for j in range(4):if a[i][j] != -1 and a[i][j] != b[i][j]:mode = 0breakif mode:ret += 1return ret# 解くdef solve():# 順番逆のほうが直感的なので逆にしてます（ごめんね）w, h, m = map(int,input().split())v = {"U":0, "D":1, "L":2, "R":3}g = gcd(w, h)rl = [0] * 4 # 方向のカウントx = [0] * m # Xy = [0] * m # Yr = [0] * m # 方向# 入力for i in range(m):xs, ys, d = input().split()x[i] = int(xs)y[i] = int(ys)r[i] = v[d]rl[r[i]] += 1# 数え上げans = 0ans += count_type1(m, rl, x, y, r, w, h, g)ans += count_type2(m, rl, x, y, r, w, h, g)ans += count_type3(m, rl, x, y, r, w, h, g)ans += count_type4(m, rl, x, y, r, w, h, g)ans += count_type451(m, rl, x, y, r, w, h, g)ans += count_type452(m, rl, x, y, r, w, h, g)ans += count_type5(m, rl, x, y, r, w, h, g)ans %= modreturn ansT = int(input())for _ in range(T):print(solve())