結果

問題 No.2283 Prohibit Three Consecutive
コンテスト
ユーザー yabit
提出日時 2023-07-07 14:11:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,059 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 91,392 KB
最終ジャッジ日時 2024-07-21 09:20:41
合計ジャッジ時間 3,368 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

binary_dict = {
    '00': [0],
    '01': [1],
    '10': [2],
    '11': [3],
    '?0': [0, 2],
    '?1': [1, 3],
    '0?': [0, 1],
    '1?': [2, 3],
    '??': [0, 1, 2, 3]
}
T = int(input())
for t in range(T):
    N = int(input())
    S = list(input())
    dp = [[0,0,0,0] for _ in range(N)]
    # dp[i][S]: i番目まで見たとき、S(0 0, 0 1, 1 0, 1 1)が構成可能か
    # print(S[0]+S[1], binary_dict[S[0]+S[1]])
    for b in binary_dict[S[0]+S[1]]:
        dp[0][b] = 1
    # print(dp)
    for i in range(1, N+1):
        if i == N:
            for j in range(4):
                dp[0][j] = 0
        p = (i-1)%N
        r = i%N
        q = (i+1)%N
        if S[q] != '0': # 1の場合
            if dp[p][0]: dp[r][1] = 1
            if dp[p][1]: dp[r][3] = 1
            if dp[p][2]: dp[r][1] = 1
        if S[q] != '1': # 0の場合
            if dp[p][1]: dp[r][2] = 1
            if dp[p][2]: dp[r][0] = 1
            if dp[p][3]: dp[r][2] = 1
    # print(dp)
    if any([d for d in dp[0]]):
        print('Yes')
    else:
        print('No')
0