yukicoder : No.1977 Extracting at Constant Intervals

細かいところを合わせるのに割と手間取った。
https://yukicoder.me/problems/no/1977

問題

長さNの整数列Aと、整数M,Lが与えられる。
AをM回繰り返した数列をBとする。
C[i] = sum(B[i+n*L]) で表現できる長さLの数列Cを考える。
Cの最大値を求めよ。

解法

NとLが互いに素であることを仮定する。
(そうでない場合、G=GCD(N,L)として、AをG個の数列に分解してそれぞれ考えればよい)

D[i]=A[i*L%N] とすると、C[i]はDの区間和になる。

• Lが小さい場合、C[i]を総当たりすればよい。
• Lが大きい場合、imin,imaxをk=i (mod L)となる最小・最大のkとする。
  • 各0≦i＜Nに対し、k=i (mod L)対するC[k]はC[imin]とC[imax]のどちらかしかとらないので、C[imin]とC[imax]だけ考えればよい。

ll N,M,L;
int A[101010];
int B[101010];
ll S[201010];

ll hoge(ll N,ll L) {
	
	ll sum=0;
	int i;
	FOR(i,N) sum+=B[i];
	FOR(i,2*N) {
		S[i+1]=S[i]+B[(__int128)i*L%N];
	}
		
	ll ret=0;
	ll M2=M%L;
	if(M2) {
		ret=-1LL<<60;
		if(L<=N) {
			FOR(i,N) {
				ll x=(__int128)i*L%N;
				if(x<L) {
					ll y=(1LL*N*M2-x-1)/L;
					ret=max(ret,S[i+y+1]-S[i]);
					
				}
			}
		}
		else {
			FOR(i,N) {
				ll x=(__int128)i*L%N;
				vector<ll> cand={M2,M2-(L/N-(x>=(L%N)))};
				FORR(c,cand) {
					if(c<=0) {
						ret=max(ret,0LL);
					}
					else {
						ll y=((__int128)N*c-x-1)/L;
						ret=max(ret,S[i+y+1]-S[i]);
					}
				}
			}
		}
	}
	return ret+(sum*(M/L));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>L;
	FOR(i,N) cin>>A[i];
	int g=__gcd(N,L);
	ll ret=-1LL<<60;
	FOR(i,g) {
		FOR(j,N/g) B[j]=A[j*g+i];
		ret=max(ret,hoge(N/g,L/g));
	}
	cout<<ret<<endl;
}

まとめ

考え方はわかっても、細かいところを詰めるのがしんどいなぁ。