結果

問題 No.2330 Eat Slime
ユーザー navel_tosnavel_tos
提出日時 2023-05-30 22:52:37
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,842 ms / 4,000 ms
コード長 3,123 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 11,124 KB
実行使用メモリ 96,908 KB
最終ジャッジ日時 2023-08-28 01:14:03
合計ジャッジ時間 42,732 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 133 ms
29,828 KB
testcase_01 AC 131 ms
29,812 KB
testcase_02 AC 131 ms
29,684 KB
testcase_03 AC 137 ms
29,848 KB
testcase_04 AC 132 ms
29,700 KB
testcase_05 AC 134 ms
29,844 KB
testcase_06 AC 132 ms
29,740 KB
testcase_07 AC 1,403 ms
92,592 KB
testcase_08 AC 838 ms
68,060 KB
testcase_09 AC 1,399 ms
90,576 KB
testcase_10 AC 455 ms
37,944 KB
testcase_11 AC 510 ms
33,740 KB
testcase_12 AC 1,384 ms
91,364 KB
testcase_13 AC 1,291 ms
92,460 KB
testcase_14 AC 785 ms
37,792 KB
testcase_15 AC 1,181 ms
67,512 KB
testcase_16 AC 1,229 ms
90,524 KB
testcase_17 AC 1,800 ms
96,800 KB
testcase_18 AC 1,796 ms
96,808 KB
testcase_19 AC 1,791 ms
96,808 KB
testcase_20 AC 1,799 ms
96,644 KB
testcase_21 AC 1,842 ms
96,620 KB
testcase_22 AC 1,801 ms
96,896 KB
testcase_23 AC 1,805 ms
96,592 KB
testcase_24 AC 1,796 ms
96,632 KB
testcase_25 AC 1,803 ms
96,672 KB
testcase_26 AC 1,782 ms
96,668 KB
testcase_27 AC 1,798 ms
96,560 KB
testcase_28 AC 1,777 ms
96,908 KB
testcase_29 AC 1,800 ms
96,880 KB
testcase_30 AC 1,785 ms
96,640 KB
testcase_31 AC 1,797 ms
96,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#MMA Contest 015 I

'''
一番左のスライムを食べる。
食べた後、左からi番目のスライムがBiならボーナス獲得。
最適化しろ。

愚直にシミュレーションしたいが、いやまて、制約がすごいことになっているぞ。
スライドさせたら答え出たりしないかな。

無理だな。捨て。

■AfterContest
畳み込みで解ける事が分かったので畳み込みます。
事前にスライムの配列を反転させておき、各色ごとに一致時にもらえる点数の配列も用意しておけば
各色で畳み込んで結果を合成することでACできそう。やってみよう。

NTT遅すぎるんだけど。なんだこれ。
やはりnumpyは全てを解決する。
'''
#MOD = 998244353 にのみ対応したFFT。それ以外では機能しません。
class NTT_998244353:
    def __init__(self,MOD=998244353): self._MOD=998244353
    def _FFT(self,f,fft_len,IDFT=False):
        h=0
        while 2**h < max(len(f),fft_len): h+=1
        f+=[0]*(2**h - len(f)); P=pow(3,119*2**(23-h),self._MOD)
        if IDFT: P=pow(P,2**h-1,self._MOD); rev=pow(2**h,self._MOD-2,self._MOD)
        for i in range(2**h):  #バタフライ演算の並び替え
            j=0
            for k in range(h): j|=(i>>k&1)<<(h-1-k)
            if i<j: f[i],f[j]=f[j],f[i]
        for x in range(h):
            b=2**x; Q=pow(P,2**(h-x-1),self._MOD); W=1  #W=Q^j
            for j in range(b):
                for k in range(0,2**h,2*b):
                    s,t=f[j+k],f[j+k+b]*W%self._MOD; f[j+k]=(s+t)%self._MOD; f[j+k+b]=(s-t)%self._MOD
                W=W*Q%self._MOD
        if IDFT:
            for i in range(2**h): f[i]=f[i]*rev%self._MOD
        return f
    def convolve(self,f,g):
        N=1; L=len(f)+len(g)-1
        while N<L: N*=2
        f=self._FFT(f,N); g=self._FFT(g,N); h=[f[i]*g[i]%self._MOD for i in range(N)]
        return self._FFT(h,N,True)[:L]


#FFT: MOD≒1e9, len(f,g)<2.5e5 程度なら巡回畳み込みせず計算可能。convolve2使用を推奨
import numpy as np
def convolve(f,g,fft_len=1):  #np.array()型で渡すとフーリエ変換を行う
    while fft_len < len(f)+len(g)-1: fft_len*=2
    FFT_F=np.fft.rfft(f,fft_len); FFT_G=np.fft.rfft(g,fft_len); FFT_H=FFT_F * FFT_G; return np.rint( np.fft.irfft(FFT_H,fft_len) ).astype('i8')[:len(f)+len(g)-1]
def convolve2(f,g,MOD): f1,f2=np.divmod(f,1<<15); g1,g2=np.divmod(g,1<<15); a=convolve(f1,g1)%MOD; c=convolve(f2,g2)%MOD; b=(convolve(f1+f2,g1+g2)-(a+c))%MOD; return ((a<<30)+(b<<15)+c)%MOD


f=lambda:list(map(int,input().split()))
NTT=NTT_998244353()

#入力受取  Cは反転  Color[i][j]: 色iがjにあれば1(True)
N,M,X=f(); C=f()[::-1]
Color=[[0]*N for _ in range(5)]; Score=[[0]*N for _ in range(5)]
for _ in range(M): a,b,y=f(); Score[b-1][a-1]+=y
for i in range(N): Color[C[i]-1][i]=1

#順に畳み込み
Convolved=[]
for i in range(5): Convolved.append(convolve(Color[i],Score[i]))
Result=[sum(Convolved[i][j] for i in range(5)) for j in range(len(Convolved[1]))][N-1::-1]+[0]
for i in range(N+1): Result[i]+=X*i
print(max(Result))
0