Codeforces Round 872

결과

링크 2023.05.08 DIV2
3솔, 2591/8805 (29.4%) 1472 (-33) (퍼포1295)
 
막바지에 겨우 3솔, 반복문을 쓰지 않고 최적의 조합을 생각하는 그리디 문제가 많이 출제됐다.

밀린 코포 후기가 엄청나게 많은데 일단 방금 풀은 코포를 까먹기 전에 방금것부터 적어보고 가려고 한다. C를 너무 늦게 풀었는데 그리디 연습 좀 해야 할 듯.

---

A LuoTianyi and the Palindrome String

개요

00:09:08
String
팰린드롬이 아닌 최대 부분문자열 길이 구하기

접근

1. 팰린드롬이 아니다 라는걸 잘 간파하는 것이 중요한 문제. 이게 생각보다 엄청 간단한데, 만약 팰린드롬이면 문자 하나만 빼주면 팰린드롬이 아니게 되고, 팰린드롬이 아니라면? 그냥 전체 문자열을 쓰면 된다. 이걸 생각하는데에 꽤 시간이 걸렸다.
2. 마지막으로 전체 문자열이 하나의 문자의 반복이라면 어떻게 부분문자열을 구성해도 팰린드롬이 된다.
3. 문자열이 팰린드롬인지 확인하려면 뒤에서부터 (i, n-i)를 비교하기보다, 그냥 생각하기 편하게 뒤집은 문자열을 하나 만들어서 앞에서부터 비교해주면 된다.

Source code

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

#define pb push_back
#define sz size
using ld=long long;
using lf=double;
using str=string;
#define all(a) a.begin(),a.end()

bool palindrome(str &s) {
    str t=s;
    reverse(all(t)); // 뒤집은 문자열과 비교
    for (int i=0;i<s.sz();i++)
        if (t[i]!=s[i])
            return 0;
    return 1;
}

void test() {
    str s;cin>>s;
    int n=s.sz();
    set<char> ss=set<char>(all(s));
    if (ss.sz()==1) cout<<-1<<"\n"; // 전체가 한가지면 -1
    else if (!palindrome(s)) cout<<n<<"\n"; // 팰린드롬 아니면 n
    else cout<<n-1<<"\n"; // 팰린드롬이면 n-1
}

---

B LuoTianyi and the Table

개요

00:42:49
Greedy
(1,1)부터 (i,j)의 최솟값과 최댓값의 차이의 총합이 최대가 되도록 2차원 배열 재배치하기

접근

1. 문제가 엄청 어려워보이는데 핵심 트릭이 있다. 우선 (i,j)까지의 최소 최대가 만약 전체의 최소, 최대라고 가정해보자. 그럼 (i,j)까지의 차이 d는 (i,j)부터 (n,m)까지 사용될 것이다. 즉 사용횟수는 (n-i+1)×(m-j+1)
2. 이걸 이용하면 된다. d의 최댓값은 최댓값-최솟값이 될테고, d가 가장 많이 사용되도록 배치하면 되는데, 가장 많이 사용되는 건 (1,2)에 있거나 (2,1)에 있는 것이 된다.
3. 그럼 아래처럼 정렬하고 d구해서 개수 곱해주면 되나?

    x = input();
    sort(x)
    int d=x.last-x.first
    int a21=d*(n-1)*m // (2,1)
    int a12=d*n*(m-1) // (1,2)

4. (1,2)에서 최대 차이를 갖도록 배치하면 (2,1)부터 (n,1)을 고려해야 한다. 즉 (1,2)를 포함하지 않는 (n-1)개의 사각형이 존재한다. 그래서 이걸 d2라고 하고 아래처럼 해주면 되는데,

    x = input();
    sort(x)
    int d1=x.last-x.first
    int d2=???
    int a21=d1*(n-1)*m+d2*(m-1) // (2,1)
    int a12=d1*n*(m-1)+d2*(n-1) // (1,2)

   문제가 생긴다. d2가 무엇이냐 하는 문제가 있다. 바로 d2는 (뒤에서 2번째 원소)-(처음)과 (마지막)-(앞에서 두번째 원소) 의 최댓값이 된다. 다 와서 여기에서 틀리면 정말 억울할만한 문제.

Source code

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

#define pb push_back
#define sz size
#define all(a) a.begin(),a.end()
using ld=long long;
using vec=vector<ld>;
using mat=vector<vec>;

/*
// Value를 구하는 함수도 만들어서 썼다. 전혀 필요 없음.
ld value(mat &a,int n,int m) {
    mat M1(n+1,vec(m+1,2e9)),M2(n+1,vec(m+1,-2e9));
    M1[1][1]=M2[1][1]=a[1][1];
    ld v=0;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (i==1&&j==1) continue;
            M1[i][j]=min(a[i][j],min(M1[i-1][j],M1[i][j-1]));
            M2[i][j]=max(a[i][j],max(M2[i-1][j],M2[i][j-1]));
            v+=M2[i][j]-M1[i][j];
        }
    }
    return v;
}
*/

void test() {
    int n,m;
    cin>>n>>m;
    mat a(n+1,vec(m+1,0));
    vec v;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            cin>>a[i][j];
            v.pb(a[i][j]);
        }
    sort(all(v));
    int d1,d2,a1,a2,ans;
    int k=v.sz();
    d1=v[k-1]-v[0];
    d2=max(v[k-1]-v[1],v[k-2]-v[0]);
    a1=d1*n*(m-1)+d2*(n-1);
    a2=d1*m*(n-1)+d2*(m-1);
    ans=max(a1,a2);
    cout<<ans<<"\n";
}

---

C LuoTianyi and the Show

개요

01:48:57
Greedy
-1이면 최소 원소의 왼쪽, -2이면 최대 원소의 오른쪽, 양수이면 그 위치에 값을 추가할 때, 무작위 순서에서 최대 값의 개수 구하기

접근

1. 낑낑대며 겨우 풀었던 문제. 미친 중꺾마 운영으로 끝나기 12분전에 AC를 받았다. 이것도 루프는 한번만 쓰면 되는 문제였다.
2. 일단 까다로운 케이스부터 해결해주자. -1,-2의 개수를 세어주고, 양수만 배열에 추가해준다. 양수 배열은 어차피 겹치는 원소는 사용하지 못하므로 vector(set(vector))로 겹치는 것을 제외해주자. 또 모든 정답은 m (자리개수)보다 크면 안되니 return 전에 min(m,ans) 를 해주자.
   1. 양수가 없다면? 왼쪽 혹은 오른쪽의 개수 중 큰 값을 return한다.
   2. 왼쪽이 없다면? 오른쪽을 처음부터 막 쓰다가 양수가 들어갈 자리면 양수를 넣어주면서 계속 오른쪽을 쓰면 된다. 그러니 rightCount + 배열길이.
   3. 오른쪽이 없다면? 마찬가지로 leftCount + 배열길이
3. 여기까지가 까다로운 케이스고, 이제 일반케이스로 오면 왼쪽, 오른쪽, 양수가 전부 다 있다. 테케의 일반케이스에는 배열길이가 1인 케이스밖에 없어서 틀리기 쉬웠다. 편의상 배열길이를 length라고 하자.
   1. 우선 오른쪽이나 왼쪽이 너무 많은 경우, 오른쪽만 쓰거나 왼쪽만 쓰는 것이 이득일 수 있다. 정답을 max(leftCount+length, rightCount+length)로 초기화하자.
   2. 여기서부터가 핵심인데, 배열 내의 하나의 원소를 중심으로 한다고 생각하자. 그럼 그 원소의 왼쪽에서는 왼쪽만쓰고, 오른쪽에서는 오른쪽만 쓴다.
   3. 그럼 왼쪽은 어느 순간부터 왼쪽카드가 다 떨어지면서 듬성듬성 비어있는 왼쪽 날개가 완성되고, 오른쪽도 마찬가지이다.
   4. 원소를 array[i]=x라고 하면 왼쪽 자리의 개수는 x-1개, 카드는 leftCount+i개가 되고, 오른쪽 자리의 개수는 m-x개, 카드는 rightCount+(length-1-i) 개가 된다. 자리보다 더 많은 카드가 들어갈 수 없으니 각각의 최솟값을 더해준다.

하나의 원소를 중심에 둔다는 생각이 나한테는 엄청 까다로워서 꽤 오래 걸렸는데, 핵심을 잡으면 크게 어렵지 않았을 것 같다. 핵심을 잡으면 앞서 처리했던 예외 케이스 세 가지도 전부 빼버려도 된다.

Source code

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

#define pb push_back
#define sz size
#define all(a) a.begin(),a.end()
using ld=long long;
using vec=vector<int>;
using snt=set<ld>;

int test() {
    int n,m,x;
    cin>>n>>m;
    vec a;
    int cl=0,cr=0;
    for (int i=0;i<n;i++) {
        cin>>x;
        if (x==-1) cl++;
        else if (x==-2) cr++;
        else a.pb(x);
    }
    snt s=snt(all(a));
    a=vec(all(s));
    int k=a.sz();
    /*
    예외케이스 세가지, 전부 빼도 똑같이 작동한다.
    if (k==0) {
        return min(m,max(cl,cr));
    } else if (cl==0) {
        return min(m,cr+k);
    } else if (cr==0) {
        return min(m,cl+k);
    }
    */
    int ans=max(cl+k,cr+k);
    for (int i=0;i<k;i++) {
        int x=a[i];
        int v=min(cl+i,x-1)+1+min(cr+(k-1-i),m-x);
        ans=max(ans,v);
    }
    ans=min(m,ans);
    return ans;
}