Interval Mod (CF R 1092 - A)

https://codeforces.com/contest/2215/problem/A

Problem - A - Codeforces

---

아이디어

모든 연산이 끝난 후, 모든 값은 다음 두가지중 하나가 됩니다.

1. 원래 수에서 %p한 값
2. 원래 수에서 %q한 값에서 %p한 값

 

이때 전체 배열에 연산을 끝내면 가능한 경우가 다음과 같습니다.

• 어떠한 구간 [t,t+k-1]에 대해서 모든 수가 1번 혹은 2번 연산으로 되어있다.

증명은 다음과 같습니다.

pf) 배열에 연산을 끝냈을 때 어떠한 상태가 가능함을 A, 위 조건을 만족함을 B라고 합시다.

• A->B 증명: A->~B가 모순임을 보입시다. 첫 연산이 %p인 경우 1번 구간이 생기므로 모순이며, 첫 연산이 %q인 경우 결국 그 구간도 %p가 되므로 2번 구간이 생기게 됩니다. 
• B->A 증명: 그 구간에서 시작을 합시다. %q와 %p를 조합하여 그 구간의 수를 최종 상태로 만들어놓습니다. 그러면 그 구간에는 어떤 연산을 하더라도 수가 바뀌지 않으므로 옆으로 한칸씩 나아가면서 옆 수들에 원하는 연산을 취해줄 수 있습니다.

그러므로 구간에 대해서 %p, %q %p를 한 값의 누적합을 구하고, 남은 구간에 대해서는 최적값을 저장하는 누적합을 만들면 O(N)에 문제를 해결할 수 있습니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll arr[101010]={0},psum[101010]={0},pqsum[101010]={0},mnsum[101010]={0};
void solve()
{
    ll N,k,p,q,i,x;

    cin>>N>>k>>p>>q;

    for (i=1;i<=N;i++)
    {
        cin>>arr[i];
        psum[i]=psum[i-1]+arr[i]%p;
        pqsum[i]=pqsum[i-1]+(arr[i]%q)%p;
        mnsum[i]=mnsum[i-1]+min(arr[i]%p,(arr[i]%q)%p);
    }

    ll Ans=pqsum[N]; //일단 다 %q 후 %p를 하는거로 고려
    for (i=k;i<=N;i++)
    {
        Ans=min(Ans,(mnsum[N]-mnsum[i]+mnsum[i-k])+(psum[i]-psum[i-k])); //중간에 길이 k의 %p를 넣기
        Ans=min(Ans,(mnsum[N]-mnsum[i]+mnsum[i-k])+(pqsum[i]-pqsum[i-k])); //중간에 길이 k의 %q %p를 넣기
    }

    cout<<Ans<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T;
    cin>>T;
    while (T--)
        solve();
}