結果

問題 No.2343 (l+r)/2
ユーザー navel_tos
提出日時 2023-06-09 22:15:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 713 ms / 2,000 ms
コード長 4,332 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 121,844 KB
最終ジャッジ日時 2025-01-02 03:23:43
合計ジャッジ時間 4,313 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder392A

'''
一応挑戦。

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

→AC5 WA10 ギャグ問の予感！

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

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

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

うーん、良い線いってそうなんだけどな。反例を探すか。

えー　本当にカス答案になりそう
文字の変化が累計8回以上になると常にTrueを返すカスコードが通るのか
'''

#実験コード
from random import randint as ri
from fractions import Fraction as Fc
def Naive(A):
    for _ in range(1000):
        X=A[:]; Y=[]
        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 Naive2(A):
    for _ in range(1000):
        X=A[:]; Y=[]
        while len(X)>1: a=ri(0,len(X)-2); X[a]=Fc(X[a]+X[a+1],2); X.pop(a+1); Y.append(a)
        if X[0]==1/2: return 1,Y
    else: return 0,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)
def solve(N,A):
    DP=[[0]*5 for _ in range(N)]; DP[0][A[0]]=1
    for i in range(1,N):
        DP[i][4]=DP[i-1][4]+(A[i]!=A[i-1])
        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
    return (any(DP[-1][k] for k in [2,3]) or DP[-1][4]>=8)
def RT3(T,time):
    for _ in range(time):
        A=Testcase(T); X,X2=Naive2(A); Y=solve(T,A)
        if X!=Y: print(A,X,Y,X2)


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

    #現在 (0で未完成, 1で未完成, 10で完成, 01で完成) の4状態を保持
    DP=[[0]*5 for _ in range(N)]; DP[0][A[0]]=1
    for i in range(1,N):
        DP[i][4]=DP[i-1][4]+(A[i]!=A[i-1])
        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]) or DP[-1][4]>=8 else print('No')
0