Educational Codeforces Round 149

결과

링크 2023.05.25 DIV2
4솔, 3725/16830 (22.1%) 1611 (-69)
(퍼포1353)
 
오랜만에 망친 대회. D를 4000명이 풀었는데 내가 8트만에 풀어서 퍼포가 작살이 났다. C까지 20분대에 풀어버려서 D도 빨리 풀어야 한다는 압박감에 실수를 한 것 같다.

---

A Grasshopper on a Line

개요

00:02:00
수학
k로 나누어 떨어지지 않으면서 x까지 이동하는 최소한의 방법 출력

접근

1. A,B,C까지 쉽다. 나누어 떨어지지 않는 방법으로 가야 하니까 만약 x가 k의 배수가 아니면? x만큼 이동하고, k의 배수라면 k의 배수가 아닌 서로 다른 두 수의 합으로 나타내면 된다.
2. 어차피 k가 2 이상이므로 x-1과 1로 나타내면 간단하게 해결할 수 있다.

Source code

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

void test() {
    int x,k;
    cin>>x>>k;
    if (x%k) cout<<1<<"\n"<<x<<"\n";
    else cout<<2<<"\n"<<x-1<<" "<<1<<"\n";
}

---

B Comparison String

개요

00:23:06
수학, 구성적
부등호 방향에 맞게 숫자를 구성했을 때 서로 다른 수의 개수가 최소한이 되도록 구성하기

접근

1. TC오류로 조금 절었다. 대회 도중 테케가 수정되는 건 처음 본 요상한 문제. 일단 문제의 핵심은 연속된 같은 부등호의 최대 개수가 된다. 왜냐하면 그래프를 그린다고 할 때, 나머지는 구간은 최대 길이 구간 안에 있는 수로 모두 구성할 수 있다.
2. 서로 다른 수라는 개념에 집착하지 않고 1씩 차이 난다고 생각하고 접근하면 크게 어렵지 않다.

Source code

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

void test() {
    int n;
    str s;
    cin>>n>>s;
    int c=0,m=0;
    for (int i=0;i<n;i++) {
        c=1;
        while (i<n&&s[i]==s[i+1]) {
            c++;
            i++;
        }
        m=max(c,m);
    }
    cout<<1+m<<"\n";
}

---

C Best Binary String

개요

00:20:35
String, Greedy
?를 0또는 1로 대체하여 사전순으로 배열하기 위해 연속 부분문자열을 뒤집는 횟수를 최소한으로 만들기

접근

1. 문제가 엄청 어려워 보이는데 그렇지 않다. 일단 뒤집는 것을 최소로 하려면 연속된 구간의 길이가 최대한 길어야 한다. 0과 1이 너무 많이 반복되면 뒤집을 일이 많아진다.
2. 그럼 0과 0 사이의 물음표는 전부 0, 1과 1은 1로 만들면 되고, 0과 1은 어떻게 하냐? 그냥 앞의 것을 따라주면 된다. 어차피 0과 1 사이에 물음표를 어떤 방식으로 채워도 한번의 뒤집기는 추가되어야 한다.

Source code

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

using str=string;
#define sz size

void test() {
    str s,ans;
    cin>>s;
    int n=s.sz();
    s='0'+s; //앞은 무조건 0이 오는게 이득
    ans=s;
    int ch=0;
    for (int i=1;i<=n;i++) {
        // 앞이 무엇이냐?
        if (s[i-1]=='0') {
            ch=0;
        } else if (s[i-1]=='1') {
            ch=1;
        }
        while(s[i]=='?') {
            ans[i]=ch+'0'; // 앞의 것을 따라감
            i++;
        }
    }
    ans=ans.substr(1);
    cout<<ans<<"\n";
}

---

D Bracket Coloring

개요

01:49:21
구성적, Greedy
Regular하고 beautiful한 괄호를 만들면서 최소한의 종류로 괄호를 분류하기

접근

1. 티어를 떨굴뻔한 주범. 확실히 다른 대회의 D보다는 쉬웠고, 그럼에도 나는 잘 못 풀었다. 골3 쯤 수준인데 내가 골랜디를 잘 안해서 이런 문제를 잘 못푼다. 패널티가 234인데 7번 제출을 안하고 1트에 맞았으면 164, 퍼포는 1525쯤 나온다. 어차피 랭크 점수는 떨어졌겠지만 한 20점 정도만 떨구지 않았을까...
2. 문제 접근은 이렇게 해주면 간단하다. 먼저 문제를 차분히 이해하는 것이 필요한데,
   1. Regular하다는 것은 열린 괄호가 제 때에 모두 닫히기만 하면 된다. 먼저 닫힌다에 대해 생각하면, "("를 +1, ")"를 -1이라 하고 전체 문자열을 더했을 때 0이 되면 된다. 그리고 제 때에 닫힌다 라는 건 뭐냐? 하면 ")"가 "("보다 먼저 나오면 안된다는 것이다. 열지도 않았는데 닫으면 안된다는 것이다. 그럼 값을 더해줄 때 음수가 나오면 안된다.
   2. 문제는 Beautiful인데, 뒤집었을 때 regular 하면 된다. 이번에는 먼저 닫은 다음에 열려도 된다. 그럼 여기서 뒤집는다에 대해 잘 이해하는 것이 매우 중요한데, 위에서 "("는 +1, ")"는 -1로 설정하고 구하는 누적합을 그래프로 나타내보자.
3. 아래 길이 24짜리 예시에 대해 그래프를 그려보자.

    )))())((((()((()()))))((

   

   1. 그래프로 나타내니 직관적으로 변했다. 이때 우리가 경계할 부분은 빨간색 부분, 즉 음수가 나오는 부분이다.
   2. 이 부분을 뒤집어 regular하게 만들어주려면 사실 그래프를 90도 회전해 위로 올려주면 된다.
      

      

      
      단순히 대칭이동해서 뒤집는 것이 아니라 90도 회전한다는 개념이 생각하기 어려운데 이 부분만 이해하면 이 문제는 아주 쉽게 끝난다.
   3. 음수인 부분을 모두 뒤집어주면 다음은 음수는 음수끼리, 양수는 양수끼리 이어 붙여주면 된다. 그래서 최대 색깔의 개수는 음수 한 개, 양수 한 개로 두 개가 된다.

음수와 양수가 변하는 지점을 찾는 것이 중요하므로 1832C와 매우 유사한 문제가 되겠다. 그래프를 그리는데에 사용한 엑셀파일을 첨부한다.

1837D.xlsx

20.1 kB

Source code

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

using vec=vector<int>;
void test() {
    int n; str s;
    cin>>n>>s;
    vec c(n+1,1),a(n+1,0);
    int v=0;
    for (int i=0;i<n;i++) {
        v+=s[i]=='('?1:-1;
        a[i]=v;
    }
    if (v) {
        cout<<-1<<"\n";
        return;
    }
    int d=s[0]=='(',t=1,ans=1;
    for (int i=0;i<n;i++) {
        if (a[i]<0&&d||a[i]>0&&!d) {
            t=3-t,d=!d,ans=2;
        }
        c[i]=t;
    }

    cout<<ans<<"\n";
    for (int i=0;i<n;i++)
        cout<<c[i]<<" ";
    cout<<"\n";
}