Codeforces Round 953 (Div 2.) 후기

원래는 블루 복귀를 한 이후로 코포를 레이팅 떨어지는게 무서워서 안 치려 했는데... 왠지 그러다간 실전 감각만 떨어질거 같기도 하고 UCPC 연습도 어차피 해야하고 모처럼 칠 시간이 있는 라운드라 참가를 했습니다.

?

근데 생각보다도?너무 잘 쳐버려서... 첫 딥2 5솔에 첫 2000이상 퍼포에 첫 딥2 퍼플 퍼포에 첫 500등 이내 등수라 좀 많이 기분이 좋습니다. D E가 평소에 비해 많이 쉽게 출제된 감이 있었는데 (개인적으로 각각 체감상 평소 딥2 B, C 수준. 실제로 배점도 평소에 비해 낮긴 했다.) 뒤에 문제라 안 도전하거나 늦게 잡은 사람들이 좀 있지 않았을까 추측해봅니다...

 

A - Alice and Books (00:03)

단순히 배열의 마지막 값과 마지막 값을 제외한 값 중 최댓값을 찾아 둘을 더해주면 됩니다. 코드는 생략하겠습니다.

보자 마자 답은 떠올랐는데 이게 정말 맞나? 에 대한 고민을 좀 했네요. 결론적으로 생각해보면 책들을 두 그룹으로 나눴을때 번호가 제일 큰 책들만 합에 기여하는데 그러면 $N$번째 책은 무조건 들어가게 되고 그 외에 하나 더 적용되는 책은 임의로 정할 수 있으니 됩니다 (적용 시킬거 빼고 다 $N$번째 책이랑 같이 두면 됨.).

B - New Bakery (00:16)

맨 앞의 $k$개의 빵에 가격 변경을 적용한다 하면 이때 이익은 다음과 같습니다.

$$-\frac{k(k+1)}{2} + (b - a + 1)k + aN$$

이는 2차 함수의 형태이므로 삼분 탐색을 통해 최댓값을 찾을 수 있습니다.

괜히 삼분 탐색 안 쓰는 풀이 고민하다 시간만 날렸네요...

 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int T; cin >> T;
    while(T--){
        ll N, A, B; cin >> N >> A >> B;
        ll ret = 0;
        ll tmp = A - B;
        ll l = 0, r = min(N, B);
        while(r - l >= 3){
            ll p = (l + l + r)/3, q = (l + r + r)/3;
            ll resp = B * p + p - (p)*(p + 1) / 2 + A * (N - p);
            ll resq = B * q + q - (q)*(q + 1) / 2 + A * (N - q);
            if(resp <= resq){
                l = p;
            } else r = q;
        }
        for(ll i=l; i<=r; i++){
            ll res = B * i + i - (i)*(i + 1) / 2 + A * (N - i);
            ret = max(res, ret);
        }
        
        cout << ret << endl;
    }
}

 

C - Manhattan Permutations (00:50)

이번 대회에서 유일하게 정당성 생각 안하고 푼 문제 같습니다. 일단 저는 길이 3, 4, 5, 6, 7의 모든 순열들과 이때 거리를 구해놓고 패턴을 찾았는데 발견 가능한 패턴은 다음과 같습니다.

 

1. 거리는 길이 $N$의 순열에 대해 최대 $\lfloor \frac{N^2}{2} \rfloor$ 이다.
2. 거리는 짝수만 가능하다. (여기까지 정보를 합치면 불가능 조건 유추 가능)
3. 거리가 최대인 순열은 유일하지 않다. (따라서 무조건 다 뒤집은 상태로 끝낸다고 생각하기 보단 실제로 최대인 것 중 하나를 어떻게 만들지에 집중하면 된다.)
4. $1 2 3 \dots N-1 N$에서 $N$을 왼쪽으로 한칸옮길때 마다 거리가 $2$늘어난다.
5. 4번 규칙을 끝까지 적용 시킨 $N 1 2 3 \dots N-2 N-1$ 에서 $N-1$을 $N-2$와 바꾸는건 거리가 늘어나지 않는다. 대신 $N-1$을 $N-3$앞으로 넣는건 거리를 $2$ 증가시키며 그 이후 한칸씩 왼쪽으로 ($N$이랑은 안 바꿈 주의할 것) 옮길때 마다 거리가 $2$ 늘어난다.
6. 5번 규칙 까지 전부 적용 시키면 $N-2$가 순열의 끝에 오게 되는데 이 경우 $N-2$를 $N-5$앞에 넣을때 부터 $2$씩 증가한다.
7. 4~6을 일반화 하면 $N - k$는 $N - 2k - 1$ 앞으로 넣을때 부터 거리가 $2$ 증가하는데 기여 함을 알 수 있다.

이제 위 규칙을 전부 합치면 다음과 같이 construction을 해볼 수 있다.

 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    int T; cin >> T;
    while(T--){
        ll N, K; cin >> N >> K;
        if(K % 2 == 1 || (N*N)/2 < K) {
            cout << "NO" << endl;
            continue;
        } else {
            vector<ll>ans;
            ll cur = N; ll x = 1; ll inv = 0;
            while(1){
                if(inv == K) break;
                if(inv + 2LL * (cur - x) < K){
                    ans.push_back(cur);
                    inv += 2LL * (cur - x);
                } else {
                    ll y = (K - inv) / 2;
                    for(int i=1; i<cur - x - (y - 1); i++){
                        ans.push_back(i);
                    } ans.push_back(cur);
                    for(int i=cur - x - (y - 1); i<cur; i++){
                        ans.push_back(i);
                    }
                    inv = K;
                }
                cur--; x++;
            }
            if(ans.empty()){
                ans.resize(N);
                iota(all(ans), 1);
            }
            cout << "YES" << endl;
            for(auto i:ans) cout << i << ' ';
            cout << endl;
        }
    }
}

 

혹시라도 정당성 증명을 아시는 분은 댓글 바랍니다.

 

여기까지 풀고 나서 아 그래도 블루는 뜨겠구나 했는데 D가 풀리는 속도가 뭔가 심상치 않아서 바로 D로 갔습니다.

 

D - Elections (01:03)

다행히 금방 풀렸습니다. 아이디어가 생각한거보다 간단해서 오히려 의심이 들 정도 (약간 이게 D인가? 느낌). 

 

우선 당연한거부터 생각해보자면 아무 변경 없이도 이기는 사람에 대해 답은 $0$입니다. 이제 이 사람이 나타나는 번호를 $p$라고 합시다.

 

번호가 $p$가 아닌 사람은 적어도 자신 앞에 있는 사람이 전부 떨어져야 가능성이 있습니다 (그러지 않으면 그 투표수가 전부 자신 앞에 있는 누군가한테 가니까.). 그러니 번호가 $i$일때 최소 $a_1 ~ a_{i-1}$ 까지 전부 더한걸 $a_i$에 더해야 하고 이것 마저 부족하다면 $a_p$ 까지 더해줘야 합니다. 이 때 $i > p$라면 이미 $a_p$가 더해졌을거고 이는 최대임을 보장합니다 (이미 최대였던거 + @ 니까 최대일 수 밖에 없다는 느낌). 

 

따라서 $i=p$면 답은 $0$, $i < p$면 $i-1$ 또는 $i$, $i > p$면 $i-1$입니다.

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    int T; cin >> T;
    while(T--){
        ll N, C; cin >> N >> C;
        vector<ll>v(N+1), pre(N+1, 0);
        for(int i=1; i<=N; i++){
            cin >> v[i];
        } v[1] += C;
        for(int i=1; i<=N; i++){
            pre[i] = pre[i-1] + v[i];
        }
        ll mx = *max_element(all(v));
        ll mxpos;
        for(int i=1; i<=N; i++){
            if(v[i] == mx) {
                mxpos = i; 
                break;
            }
        }
        vector<ll>ans(N+1);
        ans[mxpos] = 0;
        for(int i=1; i<=N; i++){
            if(i == mxpos) continue;
            else {
                if(i < mxpos){
                    if(pre[i-1] + v[i] >= mx){
                        ans[i] = i - 1;
                    } else {
                        ans[i] = i;
                    }
                } else {
                    ans[i] = i - 1;
                }
            }
        }
        for(int i=1; i<=N; i++){
            cout << ans[i] << ' ';
        } cout << endl;
    }
}

 

여기까지 풀고 나서는 아 그래도 퍼플 퍼포는 뜨겠다 하고 좋아 했는데 이번엔 E 풀리는 속도가 뭔가 심상치 않더라고요. 결국 아 E도 봐야겠구나 하고 E로 넘어갔습니다. 여기까지만 해도 풀 수 있을거란 생각은 안하고 실제로 한 10분 동안은 걍 멍 때리면서 아 이거 뭐지 세근가?? 이러고 있었는데...

E - Computing Machine (01:35)

캬 이게 풀리네

 

일단 $A$ $B$에 대한 변경이 없다고 가정하면 쿼리의 답은 $A$를 배열로 생각했을 때 $l$에서 $r$까지 누적합입니다. 

 

그리고 $A$에 최대한 많은 $1$을 만들려면 $B$에 최대한 $1$이 많아야 한데 $B$에 $1$을 만들려면 $A$에 $0$이 있어야 하니 $A \rightarrow B$ 연산을 $B \rightarrow A$연산보다 먼저 진행해야 함은 자명합니다. $A \rightarrow B$연산과 $B \rightarrow A$연산으로 인해 $A$와 $B$에 새로 $1$이 생긴 위치를 각각 표시해 둡시다(이하 $incA$, $incB$). 이제 변경이 있을 때에 대한 답을 생각해봅시다.

• $incA$의 누적합을 계산해 봅시다. 그러면 $x$를 $l ~ r$ 에 있는 새로 생긴 $1$들이라 하면 구간합을 통해 $\mathcal{O}(1)$에 구할 수 있습니다. 기본적으로는 기존 구간합에 $x$를 더하는 식으로 답을 구해볼 수 있지 않을까? 란 생각이 가능합니다.
• 다만 여기서 $l$과 $r$의 경계에 있는 새로 생긴 $1$들은 애초에 이 구간내에 존재하지 않는 값들로 부터 만들어졌을 수도 있습니다.
• $incA[l] = 1$이라면 $x$에서 $1$을 빼줘야 합니다.
• $incA[r] = 1$이라면 $x$에서 $1$을 빼줘야 합니다. 단, $l = r$이라면 빼주면 안됩니다.
• $incB[l] = 1$ 이고 $incA[l+1]=1$이라면 $x$에서 $1$을 빼줘야 합니다. 단 $l + 2 > r$이라면 위 두 조건들에서 이미 걸러졌을 테니 조심해야합니다.
• $incB[r] = 1$ 이고 $incA[r-1]=1$이라면 $x$에서 $1$을 빼줘야 합니다. 위와 마찬가지로 $l + 2 > r$ 주의. 추가적으로 $l + 2 = r$ 주의.

따라서 전처리 $\mathcal{O}(N)$에 쿼리당 $\mathcal{O}(1)$에 해결 가능합니다.

 

 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    int T; cin >> T;
    while(T--){
        int N; cin >> N;
        vector<int>A(N+2, 1), B(N+2, 0),
        preA(N+2, 0), incA(N+2, 0), incB(N+2, 0), pa(N+2, 0);
        for(int i=1; i<=N; i++){
            char c; cin >> c;
            A[i] = c - '0';
            pa[i] = pa[i-1] + A[i];
        }
        for(int i=1; i<=N; i++){
            char c; cin >> c;
            B[i] = c - '0';
        }
        for(int i=1; i<=N; i++){
            if(A[i-1] + A[i+1] == 0){
                if(!B[i]) {
                    B[i] = 1;
                    incB[i] = 1;
                }
            }
        }
        for(int i=1; i<=N; i++){
            if(B[i-1] + B[i+1] == 2){
                if(!A[i]) incA[i] = 1;
            }
        }
        for(int i=1; i<=N+1; i++){
            preA[i] = preA[i-1] + incA[i];
        }
        int Q; cin >> Q;
        while(Q--){
            int l, r; cin >> l >> r;
            int x = preA[r] - preA[l-1];
 
            if(incA[l] == 1) x--;
            if(incA[r] == 1 && !(incA[l] == 1 && l == r)) x--;
            if((incB[l] == 1 || incB[r] == 1) && (incA[l+1] == 1 || incA[r-1] == 1) && l+2<=r){
                if(l+2==r){
                    x--;
                } else {
                    if(incB[l] == 1 && incA[l+1] == 1) x--;
                    if(incB[r] == 1 && incA[r-1] == 1) x--;
                }
            }
            cout << pa[r] - pa[l-1] + x << endl;
        }
    }
}

 

마치며

정말 오랜만에 아쉽다는 생각 하나도 없이 끝난 라운드네요. 앞으로도 이러기만 하면 좋겠다만... 그건 욕심일거고. 그래도 퍼플 퍼포가 뜨기 시작했다는거에 만족하고 앞으로도 퍼플 가기 위해 노력해봐야 할거 같습니다.