Educational Codeforces Round 148

결과

링크 2023.05.12 DIV2
4솔, 536/13306 (4.02%) 1595 (+123) (퍼포1904)
 
A,B가 잘 맞아서 4솔까지 온 대회, 아직 3솔이 익숙한 단계가 아니라 3솔에 삽질을 많이 했다. 삽질하면서 멘탈이 말리고 D1도 접근은 쉽게 찾았는데 구현에서 많이 절은 것 같다.

---

A New Palindrome

개요

00:02:47
String
문자열의 일부 문자의 위치를 재배열하여 팰린드롬으로 만들 수 있는지 확인하기

접근

1. 우연히 저번 대회와 마찬가지로 A를 팰린드롬으로 시작했다. 직접 바꿔가며 찾을 것이냐? 절대 그렇지 않다.
2. 그럼 어떻게 하냐, 우선 길이가 홀수라면 가운데 원소는 아무 의미가 없다. 만약 바꿔서 팰린드롬이 된다? 하면 이미 양쪽 날개에 가운데 문자와 같은 것이 있다.
3. 그럼 가운데를 제외하고 이미 팰린드롬인 문자열이니 왼쪽 날개만 보는데, 안되는 경우만 생각해보면 모든 원소가 같은 경우이다. set을 사용해 unique size를 구해주자.

Source code

#include <bits/stdc++.h>
using namespace std;

#define sz size
#define all(a) a.begin(),a.end()
using str=string;

void test() {
    str s;cin>>s;
    int n=s.sz();
    str t=s.substr(0,n/2); // 왼쪽 날개
    set<char> c=set<char>(all(t));
    if (c.sz()==1) cout<<"NO";
    else cout<<"YES";
    cout<<"\n";
}

---

B Maximum Sum

개요

00:13:09
누적합, Bruteforce
최소 원소 2개, 최대 원소 1개 중 하나를 k번 지울때 최대 합

접근

1. 일단 최대합과 선택의 문제라는 점에서 그리디 냄새가 난다. k번 선택하고 각각 선택지가 2개니까 2^k개의 경우가 있는데 이걸 재귀문을 쓰면서 완탐을 돌린다? "미친짓"이다.

2. 그럼 우선 배열을 정렬해보자. 그럼 최솟값을 지울 때는 왼쪽 2개를, 최댓값을 지울 때는 오른쪽 1개를 지울 것인데, 투 포인터를 이용해서 s+=2, e-=1을 해줬더니 WA가 나왔다. 이게 왜 WA일까?

3. 대회 중간에 "B 예시에 문제없으니 질문좀 그만하세요" 하고 공지가 올라왔는데 아마 테케 5번에서 질문이 많이 들어왔겠지 싶었다.

    10 11 12 13 15 22
    // 10, 11, 12, 13 -> answer = 46
   
    // 21<22 -> 12, 13, 15, 22
    // 25>22 -> 12, 13, 15
    output = 40

   투 포인터로 풀면 40이 나오는데, 21과 22의 당장의 상황에서는 21을 빼는게 이득이지만, 다음에 나올 15를 생각하면 22를 같이 뽑아버리는게 이득이다. 이래서 이 문제가 그리디가 아니게 된다.

4. 그럼 완탐을 해보자. 어차피 k<2n이므로 어떤 선택을 해도 원소는 남아있다. 즉, 왼쪽이 오른쪽을 추월하는 상황이 발생하지 않는다. 왼쪽을 지운 횟수를 i라고 하고 0부터 k까지 완탐을 돌면서 max를 구하면 된다.

   1. 왼쪽 2개를 i번 지우면? 남은 경계의 왼쪽 끝은 2i+1이 된다.
   2. 그럼 오른쪽은 k-i번 지우게 되고, 오른쪽 경계의 끝은 n-(k-i)가 된다.
   3. 따라서 이때 남은 원소의 합은 2i+1 부터 n-k+i까지의 누적합이 된다.

Source code

#include <bits/stdc++.h>
using namespace std;

using ld=long long;
void test() {
    ld n,k;
    cin>>n>>k;
    ld a[n+1],s[n+1];
    s[0]=0;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++)
        s[i]=a[i]+s[i-1];
    ld ans=0;
    for (int i=0;i<=k;i++) {
        ld L = 2*i+1;
        ld R = n-k+i;
        ans=max(ans,s[R]-s[L-1]);
    }
    cout<<ans<<"\n";
}

---

C Contrast Value

개요

00:32:16
Greedy, 애드혹
배열의 일부 원소를 선택하여 인접한 원소의 차이의 합이 기존 배열과 같도록 만드는 최소 길이

접근

1. 디스크립션이 엄청 어려운 티를 내는데 생각보다 단순하다. 어떤 함수가 단조증가함수라면? 모든 인접한 원소의 차이가 양수가 된다. 그럼 그것들의 총합은? 끝-시작이 된다. 단조감소도 마찬가지.
2. 이 생각을 하는 순간 아 오르막 내리막 개수 세는거구나 하고 생각하면 된다. 852B랑 비슷하고, 최근에 풀어본 15670과도 같은 냄새를 풍긴다.
3. 오르막, 내리막의 개수를 세는 것에 대한 "생각"은 매우 단순한데, 이게 구현에서 사람을 말려 죽인다. 고민할 부분이 꽤나 많았다.
   1. 처음과 끝이 아닌 중간에 끼인 원소는 단순하다. 오르막이나 내리막의 시작점, 즉 극점을 만나면 정답에 1을 추가해준다.
   2. 그런데 i를 증가하게 루프를 돌릴테니 끝은 상관 없다 해도, 처음은 어떻게 하냐? 이게 참 어려운 부분인데, 만약 처음 두 원소가 내리막이라면 오름/내림의 초기값도 내리막으로 설정해야 하고, 오르막이면 오르막으로 설정해야 애먼 1이 추가가 안된다.
   3. 그런데 처음 두 원소가 같다면? 이때는 앞 부분에 원소가 계속 같은 구간을 통째로 덜어낸다. A,B는 테케가 친절해서 쉽게 반례를 생각할 수 있는데, C는 1 1 1 1 2 3 과 같은 케이스를 생각하기가 꽤 어려워서 헷갈렸다.

Source code

#include <bits/stdc++.h>
using namespace std;

using ld=long long;
void test() {
    ld n;
    cin>>n;
    ld a[n+1];
    for (int i=1;i<=n;i++)
        cin>>a[i];
    int ans=1;
    int s=1;
    while (a[s]==a[s+1]&&s<n) s++; // 앞같부분 덜어내기

    int d;
    if (a[s]>a[s+1]) a[0]=-1,d=0; // 오르막
    else if (a[s]<a[s+1]) a[0]=2e9,d=1; // 내리막

    for (int i=s;i<=n;i++) {
        if (a[i-1]<a[i]) {
            if (d==1) ans++; // 이전에 내리막인데 지금 오르막 (극소)
            d=0;
        } else if (a[i-1]>a[i]) { // 이전에 오르막인데 지금 내리막 (극대)
            if (d==0) ans++;
            d=1;
        }
    }
    cout<<ans<<"\n";
}

---

D1 Red-Blue Operations (Easy Version)

개요

01:55:11
Greedy
n개의 원소 중 하나에 대해 1부터 k까지 값을 더하고/빼는 것을 번갈아할 때 최솟값의 최댓값 구하기

접근

1. Bisect 태그가 붙어있는데 아마 최솟값과 가능 여부를 기준으로 돌리는 것 같다. 이건 생각 못하고 그냥 n 1000? 응 브루트포스 하고 마구잡이로 돌렸는데 어떻게 맞았다. 해킹에서 bisect 풀이가 엄청 터진 걸 운이 좋았다.
2. 문제로 돌아와서, 이게 문제가 엄청 그리디 한데, 이렇게 생각해보자.
   1. 일단 빼는 과정은 최소화 하는 것이 무조건 좋다. 왜냐? 어차피 값이 증가하기 때문에 빼려는 원소는 이전의 값보다 무조건 크다. 뺄 수록 손해다.
   2. 그렇다면 최대한 많이 덧셈을 해주고 싶은데, 당연히 가장 큰 값을 더해주는 것이 최선이다.
   3. 가장 큰 값에 +를 주면서 -의 개수를 최소화하는 방법에 대해 생각해보자. 맘같아선 모든 원소에 +를 주고 더해버리고 싶지만, -는 반드시 들어가야 한다.
3. -는 어떻게 들어가나? 하고 생각하면 +의 개수에 맞게 들어간다. 즉 앞에서부터 +와 -를 세어보면 -의 최소범위와 최대범위가 존재한다. 이게 핵심인데 생각하기가 정~말 어렵다.
   1. 먼저 1은 무조건 +라는 건 쉽게 생각할 수 있다.
   2. -의 최소범위, 즉 +의 최대범위는 k보다 작은 i에 대해 [1,i]의 모든 구간 내에서 무조건 -보다 n개를 넘어갈 수 없다. 즉 p-m<=n인데 왜냐?
   3. 처음에 n개 원소에 모두 +를 해주면 모든 원소가 -로 변한다. 그럼 여기에 +를 추가할 수는 없다. -와 +가 몇 번 번갈아 나오는 와중에도 +는 (-의 개수)+n을 초과할 수 없다.
   4. 다음 -의 최대 범위, 처음 모든 원소는 +이니까, +와 -를 번갈아 사용하면 모든 원소가 +인 상태를 유지한다. 여기서 -를 먼저 쓸 수는 없으니 -는 항상 +의 개수보다 작다. 즉 p-m>=0이고, 이것도 i<k, [1,i]에 모두 적용된다.
   5. 정리하면 아래와 같다. 추가로 생각할 부분은 +,-는 짝수개가 있을 테니, 홀수라면 짝수로 만들어주는 것이다.

       // +를 최대한 뒤로 보내면서 모든 구간에서 0<=p-m<=n을 만족하게
       12345....
       +-+-+-+-.... ++++++
       // 끝에 딸려오는 +는 최대 n개

4. 이제 구현, 구현은 먼저 작은 원소부터 끝부분의 +를 더해준다. while(s--) v[i]+=k--와 같은 식으로 생각해주면 된다.
5. 그리고 (+,-)의 덩어리는 결국 -1을 시키는 것이랑 같으니까, 최대 원소부터 해주는 것이 이득인데, 이걸 k-n번쯤 해준다? 무조건 시간에서 터진다. 편의상 -1을 d번 해준다고 하자.
   1. 그럼 계산을 잘 해줘야 하는데, 끝의 +를 더하고 난 원소들을 정렬해서 그래프를 그린다고 생각하자.
   2. X축에 평행하고 Y값이 최솟값인 직선을 그린다. 이때 윗부분의 총합이 d보다 크다면? 최솟값보다 큰 원소들로 -1들이 커버가 된다는 것이다.
   3. 아니라면? 커버의 한계를 뚫고 들어와 최솟값을 얼마나 감소시키는지 생각해야 하는데, 빼야할 값을 커버를 치고 나면 모든 값이 같아진다. 그래프에서 X축에 평행한 직선의 윗부분을 날려버린 것이다.
   4. 그럼 남은 부분은 비가 내리듯 균일하게 값들에 하나씩 쏟아지고, d/n만큼 전체 높이를 감소시킨다. 그리고 나머지가 남아있다면? 1을 더 감소시키면 된다.

그리디 생각이 꽤나 까다로워서 길고 복잡하게 풀었는데 이 풀이로 D2는 못 풀것이다. 너무 오래걸려서

Source code

#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
using ld=long long;
using vec=vector<ld>;

void test() {
    ld n,q;
    cin>>n>>q;
    vec a(n);
    for (auto&x:a) cin>>x;
    sort(all(a));
    ld k;
    while(q--) {
        vec v=a;
        cin>>k;
        ld s=min(k,n),d=k-s;
        if (d>0&&d%2) s--,d++; // 짝수만들기
        for (ld i=0;i<s;i++)
            v[i]+=k-i; // 끝부분+하고 정렬
        sort(all(v));

        if (n<k) {
            d/=2;
            ld dd=0;
            for (auto x:v)
                dd+=x-v[0]; // 커버
            if (dd<d) {
                d-=dd; // 남은값
                v[0]-=(d/n); // 균일하강
                if (d%n) v[0]--; // 나머지
            }
        }
        cout<<v[0]<<" ";
    }
}