結果

問題 No.2343 (l+r)/2
ユーザー navel_tosnavel_tos
提出日時 2023-06-09 22:15:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 759 ms / 2,000 ms
コード長 4,332 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 121,040 KB
最終ジャッジ日時 2024-06-10 13:28:22
合計ジャッジ時間 4,502 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 137 ms
88,756 KB
testcase_01 AC 759 ms
90,788 KB
testcase_02 AC 221 ms
90,888 KB
testcase_03 AC 372 ms
91,924 KB
testcase_04 AC 183 ms
109,584 KB
testcase_05 AC 156 ms
91,644 KB
testcase_06 AC 153 ms
90,576 KB
testcase_07 AC 168 ms
93,888 KB
testcase_08 AC 174 ms
93,320 KB
testcase_09 AC 169 ms
91,264 KB
testcase_10 AC 149 ms
90,440 KB
testcase_11 AC 161 ms
103,756 KB
testcase_12 AC 155 ms
100,240 KB
testcase_13 AC 152 ms
94,772 KB
testcase_14 AC 182 ms
121,040 KB
権限があれば一括ダウンロードができます

ソースコード

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