結果
問題 | No.1884 Sequence |
ユーザー |
![]() |
提出日時 | 2022-03-25 23:04:33 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,496 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 145,080 KB |
最終ジャッジ日時 | 2024-10-14 07:11:06 |
合計ジャッジ時間 | 6,998 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 WA * 2 RE * 9 |
ソースコード
from collections import CounterN=int(input())ori_A=list(map(int,input().split()))#0を除いてソートしつつ0の数を覚えておく#0にはできない#あとは等差を決め打ちして確認すればいいのでは?zero=0A=[]for a in ori_A:if a==0:zero+=1else:A.append(a)if len(A)==0:print("Yes")exit()A.sort()B=[]for i in range(len(A)-1):B.append(A[i+1]-A[i])cnt=Counter(B)#差が2種類以上あるときは等差数列になっていません。#差を増やすことはできないですが、zeroを使って差をへらすことはできるかもしれないです。具体的には差rがあったときはz個のzeroをつかってr//(z+1)に置き換えることができます。ただしこれは割り切れるときのみ可能です。#zeroを使ってCounterの中身を全部最小にできるか考えましょう#全部の差をtargetに一致させたいですね。target=min(cnt.most_common())[0]if len(cnt)<2:print("Yes")exit()for r,c in cnt.items():#rをtargetに一致させることができるかを考えますが、これはz=r//target-1if target*(z+1)==r:#このときはz個のzeroをつかってrをtargetに書き換えられます同じのがc個あることに注意してくださいzero-=c*zif zero<0:#zeroが足りなかったらだめprint("No")exit()continueelse:#これはもうrはtargetに一致させられない数なのでprint("No")exit()print("Yes")