結果

問題 No.2330 Eat Slime
ユーザー navel_tos
提出日時 2023-05-30 22:52:37
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 3,382 ms / 4,000 ms
コード長 3,123 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 109,032 KB
最終ジャッジ日時 2024-12-28 13:17:16
合計ジャッジ時間 68,402 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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