結果
問題 | No.2283 Prohibit Three Consecutive |
ユーザー | buey_t |
提出日時 | 2023-04-29 11:54:24 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,444 bytes |
コンパイル時間 | 127 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 211,528 KB |
最終ジャッジ日時 | 2024-11-18 09:33:30 |
合計ジャッジ時間 | 6,128 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 119 ms
89,376 KB |
testcase_01 | AC | 128 ms
89,508 KB |
testcase_02 | WA | - |
testcase_03 | AC | 679 ms
211,528 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 377 ms
150,764 KB |
testcase_09 | AC | 368 ms
151,108 KB |
testcase_10 | AC | 382 ms
150,780 KB |
testcase_11 | AC | 383 ms
150,816 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
ソースコード
from math import sqrt,sin,cos,tan,ceil,radians,floor,gcd,exp,log,log10,log2,factorial,fsumfrom heapq import heapify, heappop, heappushfrom bisect import bisect_left, bisect_rightfrom copy import deepcopyimport copyimport randomfrom random import randrangefrom collections import deque,Counter,defaultdictfrom itertools import permutations,combinationsfrom decimal import Decimal,ROUND_HALF_UP#tmp = Decimal(mid).quantize(Decimal('0'), rounding=ROUND_HALF_UP)from functools import lru_cache, reduce#@lru_cache(maxsize=None)from operator import add,sub,mul,xor,and_,or_,itemgetterimport sysinput = sys.stdin.readline# .rstrip()INF = 10**18mod1 = 10**9+7mod2 = 998244353#DecimalならPython#再帰ならPython!!!!!!!!!!!!!!!!!!!!!!!!!!def calc(N,S):t = []for s in S:if s == "?":t.append(2)else:t.append(int(s))for init in range(4):flag = Truefor i in range(2):if t[i] == 2 or t[i] == ((init >> (1 - i)) & 1):passelse:flag = Falseif flag == False:continuedat = [0] * 4dat[init] = 1for j in range(2,N):nx = [0] * 4if t[j] == 2 or t[j] == 1:for bit in range(3):nx [((bit << 1) | 1) & 3] |= dat[bit]if t[j] == 2 or t[j] == 0:for bit in range(1,4):nx [(bit << 1) & 3] |= dat[bit]dat = nxfor bit in range(4):if dat[bit]:flag = Truetmp = (bit << 1) | (init >> 1)if tmp == 0 or tmp == 7:flag = Falseelse:passtmp = ((bit & 1) << 2) | initif tmp == 0 or tmp == 7:flag = Falseelse:passif flag:#print(bit,tmp,init)return Truereturn False'''dpだとは思う直前の二個を記録すればいいかな1周回ってきたときに、最初の?をなにで解釈したか考えないといけない最初の?が1じゃないとダメなとき、11が後ろにあったらダメ3文字メモしておかないとだめ?'''for _ in range(int(input())):N = int(input())S = list(input().rstrip())dp = [[[[0]*2 for _ in range(2)] for _ in range(2)] for _ in range(N+1)]for i in range(2):for j in range(2):for k in range(2):dp[0][i][j][k] = 1for i in range(1,N+1):if S[i-1] == '0':for j in range(2):for k in range(2):for l in range(2):if j == k == 0:continuedp[i][j][k][0] = max(dp[i][j][k][0], dp[i-1][l][j][k])elif S[i-1] == '1':for j in range(2):for k in range(2):for l in range(2):if j == k == 1:continuedp[i][j][k][1] = max(dp[i][j][k][1], dp[i-1][l][j][k])else:for j in range(2):for k in range(2):for l in range(2):if j == k == 0:continuedp[i][j][k][0] = max(dp[i][j][k][0], dp[i-1][l][j][k])for j in range(2):for k in range(2):for l in range(2):if j == k == 1:continuedp[i][j][k][1] = max(dp[i][j][k][1], dp[i-1][l][j][k])f = 0for i in range(2):for j in range(2):for k in range(2):if dp[N][i][j][k] == 1:if j == k:for l in range(2):for m in range(2):if dp[3][(j+1)%2][l][m] == 1:f = 1else:for l in range(2):for m in range(2):if dp[3][m][(m+1)%2][l] == 1:f = 1if f:print('Yes')else:print('No')