結果

問題 No.2343 (l+r)/2
ユーザー navel_tosnavel_tos
提出日時 2023-06-09 22:15:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 874 ms / 2,000 ms
コード長 4,332 bytes
コンパイル時間 555 ms
コンパイル使用メモリ 86,660 KB
実行使用メモリ 104,216 KB
最終ジャッジ日時 2023-08-30 13:27:11
合計ジャッジ時間 6,726 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 235 ms
82,124 KB
testcase_01 AC 874 ms
87,108 KB
testcase_02 AC 330 ms
85,708 KB
testcase_03 AC 486 ms
88,524 KB
testcase_04 AC 275 ms
97,468 KB
testcase_05 AC 266 ms
91,052 KB
testcase_06 AC 262 ms
89,356 KB
testcase_07 AC 269 ms
90,792 KB
testcase_08 AC 269 ms
90,120 KB
testcase_09 AC 266 ms
89,284 KB
testcase_10 AC 251 ms
89,600 KB
testcase_11 AC 268 ms
99,868 KB
testcase_12 AC 261 ms
97,288 KB
testcase_13 AC 254 ms
93,284 KB
testcase_14 AC 273 ms
104,216 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