Codeforces Round # 634(Div. 3) Solution

2020.04.13 저녁 23시 35분에 치룬, Codeforces Round #634 풀이를 해보겠습니다.

문제는 A~F까지 출제되었고, E는 E1,E2로 문제의 조건만 다르게 2문제로 출제되었습니다.

 

저는, E2와 F는 풀지 못했고.. 이번 풀이에서 다루지 않을 예정입니다.

 

대회 문제가 생각보다, 쉽게 나왔고 그덕분에 Blue(expert)에 도달했습니다. ㅎㅎ

와! 블루!

 

대회 문제 목록: https://codeforces.com/contest/1335

Dashboard - Codeforces Round #634 (Div. 3) - Codeforces

대회 에디토리얼: https://codeforces.com/blog/entry/75993

Codeforces Round #634 (Div. 3) Editorial - Codeforces

 

 

그럼, 바로 설명 ㄱㄱ

 

A. Candies and Two Sisters

풀이

문제 링크

쉽게 쉽게 생각하면 되게 좋은 문제입니다.

 

candy를 나누어주지 못하는 경우는 candy의 개수가 2보다 작거나 같은 경우입니다.

이 경우를 배제하고 나서, candy의 개수가 짝수이면 (candy/2 - 1)을 홀수면 (candy/2)를 출력하면됩니다.

 

코드(cpp)

#include <iostream>
using namespace std;
typedef long long ll;
ll tc,N;

ll f(ll a) {
    if(a<=2) {
        return 0;
    }
    if(a%2==0) {
        return a/2 -1;
    }
    return a/2;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> tc;
    while (tc--) {
        cin >> N;
        cout <<f(N) << "\n";
    }
}

 

B. Construct the String

풀이

문제 링크

이 문제는 괜히 복잡하게 생각하는 순간, 못 풉니다.

문제를 요약하자면, "n, a, b가 주어지고, n이라는 길이를 가지는 문자열을 만드는데, 단 그 안에 길이가 a인 모든 부분 문자열이 b 개 종류의 문자로 이루어져야 한다." 입니다.

 

제가 생각한 IDEA는 일단 길이가 a이고 b개의 종류의 문자로 이루어지는 문자열을 만듭니다.

그리고 나서, 길이가 n이 될때까지 계속 이 문자열을 반복하는 것입니다.

 

이 아이디어가 왜 성립할까요?

 

한번, "abc" 라는 문자열이 있다고 생각해볼까요?

 

그리고나서 "abca" , "abcab", "abcabc" .. 로 쭉 계속 이어진다고 할때, 길이가 3인 부분 문자열들의 구성요소는 항상 같게 됩니다. 이 때문에 이 아이디어는 성립합니다.

코드(python)

tc = int(input())
for _ in range(tc):
    a,b,c=map(int,input().split())
    s = ""
    for i in range(c):
        s += chr(97+i)
    s2 = ""
    for i in range(b):
        s2 += s[i%c]
    ans = ""
    for i in range(a):
        ans +=s2[i%b]
    print(ans)

 

C. Two Teams Composing

풀이

문제 링크

 

일단, 이 문제는 꼭 문제 지문을 다 이해하고 보시기 바랍니다.

 

일단, 사람들의 능력치 그 숫자마다의 개수를 세줍니다.

 

그리고 나서  O(n)으로 그 능력치 개수을을 훑으면서, ans = max(ans,max(min(해당 능력치 개수, 전체 개수 - 1), min(해당 능력치 개수-1, 전체 개수))) 를 수행해주면 됩니다.

 

min(해당 능력치 개수, 전체 개수 -1)은 첫번째 팀과 두번째 팀에 같은 능력치를 가진 사람이 없는 경우입니다.

min(해당 능력치 개수 -1, 전체 개수)는 첫번째 팀과 두번째 팀에 같은 능력치를 가진 사람이 있는 경우입니다.

코드

tc = int(input())
for _ in range(tc):
    n = int(input())
    L = list(map(int,input().split()))
    d = {}
    for i in L:
        try:
            d[i] +=1
        except:
            d[i] = 1
    cnt = len(d.items())
    L2 = list(d.items())
    ans = 0
    for i in L2:
        current = min(i[1], cnt-1)
        ans = max(ans,current)
        current = min(i[1]-1, cnt)
        ans = max(ans,current)
    print(ans)

 

D. Anti-Sudoku

풀이

문제 링크

이 문제가 개인적으로 이번 대회에서 가장 재밌었고, 기억에 남는 문제인 것 같습니다.

D번 문제여서 좀 어려운 탐색을 요구하나 했는데, 그냥 아래 그림에 해당하는 위치의 숫자들만 변조해주면 됩니다.

왜냐하면,... 그림을 보시면, 해당 위치들은 서로 영향을 주지 않는 위치라는 것을 알 수 있습니다. 네, 뭐 그렇습니다.

(이 위치들은 무조건 이 위치는 아니지만, 생각해낼 때, 이 위치가 편합니다.)

아무튼 스도쿠를 표현한 그림임.

 

코드

tc = int(input())
for _ in range(tc):
    L = [list(map(int,list(input()))) for i in range(9)]
    D = [[0,0],[3,1],[6,2],[1,3],[4,4],[7,5],[2,6],[5,7],[8,8]]

    for i in D:
        Y = i[0]
        X = i[1]
        L[Y][X] = L[Y][X] +1
        if L[Y][X] == 10:
            L[Y][X] = 1
    
    for s in L:
        for x in s:
            print(x,end="")
        print()

 

 

E1. Three Blocks Palindrome (easy version)

풀이

문제 링크

 

E2는 이 풀이로 절대 안됩니다.

 

일단 사용되는 숫자가 1~26까지라는 사실에 집중하고 시작합시다.

 

그냥 전, 모든 구간을 싹 다 찾아냈습니다. (E1이니까요)

 

가상의 구간 3개(a, b, c)가 있다고 합시다.

 

그때 찾아내면 되는 값은 [min(a 구간에 포함된 k, b에 포함된 k) 중 최대값(k는 1부터 26 사이 숫자) ]+  [b 구간에 존재하는 숫자들 중 가장 많이 있는 숫자의 개수] 입니다.   

 

만약 이 숫자 개수를 그때 그때 구하면 TLE가 뜰 게 뻔하므로, prefix array를 활용해 숫자 개수들을 저장해놓아야 합니다. :)

코드

#include <iostream>
using namespace std;
int tc;
int N;
int ar[2200];
int D[2200][33];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> tc;
    while(tc--) {
        int ans = 1;
        cin >> N;
        for(int x=0; x<N; x++) {
            cin >> ar[x];   
        }


        for(int x=0; x<=N; x++) {
            for(int y=1; y<=26; y++) D[x][y]= 0;
        }



        D[0][ar[0]] = 1;


        for(int x=1; x<=N; x++) {
            for(int y=0; y<=26; y++) D[x][y] = D[x-1][y];
            if(x!=N) D[x][ar[x]]++;
            if(D[x][ar[x]] >ans) ans = D[x][ar[x]];
        }


        for(int x=0; x<N; x++) {
            for(int y=N; y>x; y--) {
                int Mx = 0;
                for(int k =1; k<=26; k++) {
                    int A = D[x][k];
                    int B = D[N][k] - D[y-1][k];
                    if(Mx < min(A,B)) {
                        Mx = min(A,B);
                    }
                }
                
                int Mx2 = 0;
                for(int k=1; k <= 26; k++) {
                    int A = D[y-1][k]-D[x][k];
                    if(Mx2 < A) {
                        Mx2 = A;
                    }
                }

                if(ans < Mx*2 + Mx2) {
                    ans = Mx*2 + Mx2;
                }
                // cout << x << " " << y << " " << Mx << " " << Mx2 << "\n"; 
            }
        }


        cout << ans << "\n";        
    }
}

 

E2와 F는 제가 못 풀었는데 어떻게 풀이해요!

아 멀라여 :)

 

아무튼, 이번 코포 Div3는 생각보다 쉬운 라운드였습니다.

(갓갓 tourist는 모든 문제를 20여분 내로 AC를 받아냈죠...그는 대체..)

 

이제 이 계정은 잠시 blue의 여흥을 즐기게 놔두고 부계정을 blue로 만들러가보겠습니다.