結果

問題 No.2343 (l+r)/2
コンテスト
ユーザー navel_tos
提出日時 2023-06-09 21:56:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,533 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 122,496 KB
最終ジャッジ日時 2025-01-02 02:57:47
合計ジャッジ時間 4,362 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder392A

'''
一応挑戦。

んー実験すれば解けないか？
えー　わからない　ギャグ問だと信じて投げてみる

→AC5 WA10 ギャグ問の予感！

えー AGCならA問題ということを思い出してぐっと操作すると
01010101･･･みたいな交互列なら大丈夫なので
交互列になればTrueを返すゴミコードを作ってみましょう

でも 0101 1010 は当然Trueになることを思い出すと、そう単純ではなさそう？
違うか 連続部があったら常にTrueになるのか
えー違いますね

01で今終わって良いか　もしくは10で今終わって良いかを管理すればいいのかな
もう少し詰めれば解けそう
'''

#実験コード
from random import randint as ri
from fractions import Fraction as Fc
def Naive(A):
    for _ in range(1000):
        X=A[:]
        while len(X)>1: a=ri(0,len(X)-2); X[a]=Fc(X[a]+X[a+1],2); X.pop(a+1)
        if X[0]==1/2: return 1
    else: return 0
def Testcase(N): return [ri(0,1) for _ in range(N)]
def RT(T,time):
    for _ in range(time): A=Testcase(T); print(A,Naive(A)==1)
def RT2(T,time):
    for _ in range(time):
        A=Testcase(T)
        if Naive(A)==0: print(A)


for _ in range(int(input())):
    N=int(input()); A=list(map(int,input().split()))

    #現在 (0で未完成, 1で未完成, 10で完成, 01で完成) の4状態を保持
    DP=[[0]*4 for _ in range(N)]; DP[0][A[0]]=1
    for i in range(1,N):
        if A[i]==0:
            #0で未完成があれば、引き続き0で未完成
            if DP[i-1][0]: DP[i][0]=1
            #1で未完成があれば、10で完成に遷移
            if DP[i-1][1]: DP[i][2]=1
            #10で完成は崩れない。しかも、0で未完成としてはじめることすら可能
            if DP[i-1][2]: DP[i][2]=1; DP[i][0]=1
            #01で完成があれば、これによって崩れ未完成になる
            if DP[i-1][3]: DP[i][0]=1
        if A[i]==1:
            #0で未完成があれば、01で完成に遷移
            if DP[i-1][0]: DP[i][3]=1
            #1で未完成があれば、そのまま遷移
            if DP[i-1][1]: DP[i][1]=1
            #10で完成があれば、崩れて未完成になる
            if DP[i-1][2]: DP[i][1]=1
            #01で完成も崩れない。しかも、1で未完成としてはじめることすら可能
            if DP[i-1][3]: DP[i][3]=1; DP[i][1]=1
    print('Yes') if any(DP[-1][k] for k in [2,3]) else print('No')
0