Codeforces Round 799 (Div. 4)

Dashboard - Codeforces Round 799 (Div. 4) - Codeforces

 

E

방법 1 - two pointer

index	0	1	2	3	4	5	6	7	8
val	1	0	1	1	0	1	0	0	1

길이가 7인 1-based 배열이 주어졌다고 하자. 위 배열로부터 값이 1인 index를 저장하고 있는 배열을 구하자.
[0, 2, 3, 4, 8]

이로부터 합이 2인 maximum segment를 구할 수 있다.(합이 4가 되는 segment에서 양 끝 index에서 1씩 줄이면 된다.)
[0, 2, 3, 4, 8] → 구간 [0+1, 4-1]
[0, 2, 3, 4, 8] → 구간 [2+1, 8-1]

 

방법 2 - prefix array + binary search

길이가 N인 1-based 배열의 누적합을 생각하자. 이를 이용하여 답의 왼쪽 끝점이 임의의 l(for every 1 ≤ l ≤ N)인 경우 가장 길이가 큰 segment를 이분탐색으로 찾아주면 된다.

 

H

index	1	2	3	4	5	6	7
A	8	8	9	8	3	3	9
B	1	1	-1	1	-1	-1	-1

위와 같이 길이가 7인 배열 A가 주어졌다고 하자. 만약 a:=8에 대해서 도박을 한다고 하면 다음과 같이 정의된 배열 B에 대해, 합이 최대가 되는 부분배열에서 도박을 하면된다.
B[i] := 1 if B[i] = a, -1 otherwise. 

이때 a는 뭘로 결정해줘야 하는지 알 수 없으므로 배열 A에 등장한 모든 정수에 대해서 따져봐야 한다. 한편, 배열 B는 a와 같은지 아닌지 여부로만 결정되기 때문에 값이 a인 배열 A의 index만 알아도 배열 B가 정의된다.(따라서 아래 서술할 모든 방법에서는 배열 B를 index로만 다룬다.)

 

방법 1 - 누적합

임의의 a ∈ (배열에 등장한 정수)에 대해 합이 최대가 되는 배열 B의 부분배열을 구하자.

이때 누적합을 아이디어를 사용한다

index	1	2	3	4	5	6	7
A	8	8	9	8	3	3	9
B	1	1	-1	1	-1	-1	-1
ACC of B	1	2	1	2	1	0	-1

예를 들어 a := 8이라고 한다면 배열 B와 배열 B의 누적합은 위와 같다. 이제 배열 B의 최대 부분배열(합이 최대인 부분배열)을 구해보자. 필요없는 부분은 제거하고 다음 정보만 사용하자

index	1	2	4
A	8	8	8
B	1	1	1
ACC of B	1	2	2

각 index(∈ {1, 2, 4})가 최대 부분배열의 오른쪽 끝인 경우로 분류하여 구하면 된다.
i) index 1이 오른쪽 끝인 최대 부분배열 := B[1...1]
i) index 2가 오른쪽 끝인 최대 부분배열 := B[1...2]
i) index 4가 오른쪽 끝인 최대 부분배열 := B[1...4]

이때 각각의 경우에서 최대 부분배열의 왼쪽 끝점이 되는 부분은 누적합이 최소가 되는 index이다. 

 

 

방법 2 - dp

배열 d에 대해, lis[i] := (오른쪽 끝이 index i인 최대 부분배열) 이라고 하자. 
그러면 lis[i] := lis[i] + d[i] 이거나 d[i] 이다.

 

 

방법 3 - Segment tree + dp

 

 

방법 4 - 완탐 + 약간의 최적화

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define all(v) v.begin(), v.end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef array<int, 6> I;
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    int T; cin >> T;
    while(T--){
        int N; cin >> N;
        vector<int> d(N+1);
        for(int i = 1; i <= N; ++i) cin >> d[i];
 
        list<I> lis; // {num, l, maxacc, maxr, acc, r}
        int ansacc = -1;
        int ansl = -1, ansr = -1;
        for(int i = 1; i <= N; ++i){
            bool exist = false;
 
            for(auto it = lis.begin(); it != lis.end();){
                auto& [num, l, maxacc, maxr, acc, r] = *it;
                if(num == d[i]){
                    exist = true;
 
                    acc += 1;
                    r = i;
 
                    if(maxacc < acc){
                        maxacc = acc;
                        maxr = r;
                    }
 
                    ++it;
                }
                else{
                    if(acc == 1){
                        if(maxacc > ansacc){
                            ansacc = maxacc;
                            ansl = l;
                            ansr = maxr;
                        }
                        lis.erase(it++);
                    }
                    else{
                        acc -= 1;
                        r = i;   
                        ++it;
                    }
                     
                }
            }
 
 
            if(!exist){
                // {num, l, maxacc, maxr, acc, r}
                lis.push_back(I{d[i], i, 1, i, 1, i});
            }
        }
 
        for(auto it = lis.begin(); it != lis.end(); ++it){
            auto& [num, l, maxacc, maxr, acc, r] = *it;
            if(ansacc < maxacc){
                ansacc = maxacc;
                ansl = l;
                ansr = maxr;
            }
        }
 
        cout << d[ansl] << ' ' << ansl << ' ' << ansr << endl;
    }
 
    return 0;
}cs