結果

問題 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  
実行時間 2,610 ms / 4,000 ms
コード長 3,123 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 109,016 KB
最終ジャッジ日時 2024-06-08 20:47:45
合計ジャッジ時間 62,854 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 523 ms
44,020 KB
testcase_01 AC 517 ms
44,524 KB
testcase_02 AC 525 ms
44,140 KB
testcase_03 AC 528 ms
44,140 KB
testcase_04 AC 533 ms
44,536 KB
testcase_05 AC 540 ms
44,304 KB
testcase_06 AC 524 ms
44,268 KB
testcase_07 AC 2,112 ms
105,236 KB
testcase_08 AC 1,386 ms
79,416 KB
testcase_09 AC 2,029 ms
103,708 KB
testcase_10 AC 909 ms
48,600 KB
testcase_11 AC 974 ms
44,400 KB
testcase_12 AC 2,046 ms
104,500 KB
testcase_13 AC 1,919 ms
105,672 KB
testcase_14 AC 1,288 ms
48,336 KB
testcase_15 AC 1,810 ms
79,084 KB
testcase_16 AC 1,846 ms
104,040 KB
testcase_17 AC 2,532 ms
108,764 KB
testcase_18 AC 2,569 ms
108,756 KB
testcase_19 AC 2,547 ms
108,908 KB
testcase_20 AC 2,584 ms
108,384 KB
testcase_21 AC 2,591 ms
108,764 KB
testcase_22 AC 2,558 ms
108,520 KB
testcase_23 AC 2,555 ms
108,264 KB
testcase_24 AC 2,565 ms
109,016 KB
testcase_25 AC 2,606 ms
108,768 KB
testcase_26 AC 2,552 ms
108,264 KB
testcase_27 AC 2,581 ms
108,764 KB
testcase_28 AC 2,563 ms
108,380 KB
testcase_29 AC 2,559 ms
108,404 KB
testcase_30 AC 2,577 ms
108,504 KB
testcase_31 AC 2,610 ms
108,388 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