Codeforces Round #815 (Div.2) 후기

 

 

이번이 두번째 코포이다. 솔직히 첫번째껀 Div.1 + Div.2라서 그런지 A번을 떠올리는데 오래걸렸다. 그리고 저건 친구 하는거 보고 따라한거라 각잡고 한것도 아니라 풀집중을 안하고 A번 풀고 놀면서 다른문제 읽었다. 결국 못떠올리고 A번만 풀긴 했지만..

 

하지만 이번에 참가한 Contest는 다르다. 무심코 참가한 첫번째 Contest로 인해서 Codeforces에 관심이 생기게 됐고 진지하게 레이팅에 관심이 생기게 되었다. Contest시작시간까지 외워두고 빡겜뛸 각오를 하고 참가했다.

 

 

제출 이력은 보면 알겠지만 A, B, C모두 풀이를 떠올렸다. A는 대회중엔 맞았다고 떴는데 자잘한 구현미스가 있어서 대회 끝나고 테케 빡세게 줘서 재채점할때 반례가 나왔다. (사실 내가 쓸데없이 복잡하게 짜긴 했다.) A를 너무 복잡하게 생각해서 50분이나 걸렸고 덕분에 C를 코딩하기 시작한게 대회 종료 20분전이다. 빠르게 코딩해서 제출했지만 처리 안해준 부분이 있어서 WA가 떴다. 그래서 처리해주다가 시간이 1분도 안남았길래 그냥 한번 더 제출해봤다. 당연히 맞을리는 없다.

 

비록 문제는 하나밖에 못맞았지만 Div.2문제를 3개나 제대로 접근했다는것에 의미를 두고 있다. 일단 레이팅을 올리기 위해서는 A, B, C를 빨리 푸는 연습을 하고 3솔을 어느정도 안정적으로 할 실력이 되면 그 뒤에 문제들을 건드려야 될것 같다.

보통 8시간 이상 진행해서 시간 생각 안하고 쉬면서 해도 되는 CTF랑은 다르게 알고리즘 대회는 시간제한이 적은만큼 문제를 푸는 능력 뿐만 아니라 빠르게 구현하는 능력도 중요한것 같다.

솔직히 코포가 CTF보다 더 재밌는것 같다. 이번에 SSL합격하면 커널 집중적으로 팔거라서 CTF는 자주 못할것 같지만 코포는 2시간이니까 짬내서 자주 해야겠다.

 

 

A - Burenka Plays with Fractions

 

Problem - 1720A - Codeforces

 

두 분수가 주어지고 두 분수중에 하나를 골라서 분모나 분자에 임의의 수를 곱할 수 있다. 두 분수가 같아지기 위해서 곱해야하는 숫자의 종류를 출력하면 된다. 분수가 같을 경우에는 곱할 필요가 없으니까 0을 출력하고 분수의 관계가 배수, 약수 관계라서 자연수를 곱하면 같아지는 상황에서는 분자에 자연수만 곱하면 되기 때문에 1을 출력하고 그게 아닌 경우에는 분자, 분모에 각각 다른 숫자를 곱해야 하니까 2를 출력하면 된다. 나는 약분 -> 통분 -> 분자 체크 + 예외처리 이러한 방식으로 풀이를 진행했었다. 유클리드 호제법 가지고 gcd, lcm구하고 지지고 볶고 했는데 예외처리할때 조건 잘못줘서 Contest도중에 테케는 다 맞았는데 Contest끝나고 테케 빡세게 줘서 재채점할때 6번째 테케에서 WA떴다. 애초에 if문에 너무 많은 조건을 때려넣긴 했다. 알고보니까 이 문제는 gcd, lcm쓸 필요도 없고 간단하게 곱셈 두변으로 판별할 수 있는 문제였다.

내 풀이는 쓸데없이 복잡하고 매우 이상하니까 간단한 풀이의 코드를 올리겠다.

 

#include <iostream>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long t, a, b, c, d;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> a >> b >> c >> d;
        if(a*d == c*b) cout << 0 << "\n";
        else if(!a || !c) cout << 1 << "\n";
        else if(!((a*d)%(b*c)) || !((b*c)%(a*d))) cout << 1 << "\n";
        else cout << 2 << "\n";
    }

    return 0;
}

 

 

B - Interesting Sum

 

Problem - 1720B - Codeforces

 

수열이 주어지고 임의의 l, r을 선택할 수 있다.

 

$$max(a_{1}, a_{2}, ..., a_{l-1}, a_{r+1}, a_{r+2}, ..., a_{n}) - min(a_{1}, a_{2}, ..., a_{l-1}, a_{r+1}, a_{r+2}, ..., a_{n})$$

$$ + max(a_{l}, ..., a_{r}) - min(a_{l}, ..., a_{r})$$

 

l, r을 선택하고 위와 같은 수식에 대입했을 때 최대값이 나오는 l, r을 찾아서 최대값을 출력하면 된다.

어려워 보이지만 수식을 이해하고 조금만 생각해보면 풀이를 찾을 수 있다. l, r을 임의로 선택할 수 있다는건 결국 위 수식에서 max와 min으로 결정될 값들을 마음대로 선택할 수 있는 꼴이 된다. 덧셈은 가장 큰 값으로 하고 뺄셈은 가장 작은 값으로 해야 최적의 해가 나오므로 수열을 오름차순 정렬 하고 a[n-1] + a[n-2] - a[0] - a[1]의 결과를 출력하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> n;
        vector<long long> v(n);
        for(int j = 0; j < n; j++)
            cin >> v[j];
        sort(v.begin(), v.end());
        cout << v[n-1] + v[n-2] - v[0] - v[1] << "\n";
    }
 
    return 0;
}

 

인풋 최대가 10억이라 아무리 커도 결과가 20억으로 int최대값 안넘긴 하는데 그냥 안전하게 long long으로 해줬다.

 

 

C - Corners

 

Problem - C - Codeforces

 

$N\times{M}$의 행렬이 주어지고 행렬의 각 요소는 0과 1만으로 구성되어 있다. 한 작업 에서 하나 이상의 셀에 1이 포함된 L자 도형을 만들고 그 안에 있는 모든 숫자를 0으로 바꿔야 하고 주어진 행렬에서 이러한 작업을 최대 몇 번 수행할 수 있는지를 구하는 문제이다. 친절하게 아래에 예시까지 주어지니까 예시를 보면서 조금만 관찰을 해보면 바로 풀이가 보인다.

0이 상하좌우 대각선으로 하나라도 인접해 있을 경우에는 1을 1개만 없애면서 L을 만들 수 있고 끝까지 1개씩만 없애면서 쭉쭉 뻗어나갈 수 있다. 0이 존재하지만 상하좌우나 대각선으로 인접한 0이 단 1개도 존재하지 않는 경우에는 맨 처음에 1을 2개 없애서 L을 만들어야 하고 그 이후로는 1개씩 없애면서 1을 모두 지울 수 있다. 그리고 행렬에 1만 존재하는 경우에는 처음에 1을 3개 없애서 L을 만들어야 하고 그 이후에는 마찬가지로 1개씩 없애면서 진행할 수 있다.

 

즉 출력 결과는 1의 개수에서 0을 빼냐 1를 빼냐 2을 빼냐 이 3가지로 나뉘고 행렬 요소가 전부 0인 경우나 인접해있는 0이 하나도 없을 경우에 0을 빼서 출력하면 되고 인접해있는 0이 하나라도 존재하면 1을 빼서 출력하고 행렬의 요소가 전부 1이면 2를 빼서 출력하면 된다. 시간이 얼마 안남은 촉박한 시점에서 이러한 관찰을 했다는 사실이 매우 뿌듯하다. 물론 대회 당시에는 대각선을 처리해주지 않아서 WA를 받았고 코드 고치다가 대회 시간이 끝났다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    int t, n, m, c = 0;
    bool toogle = false;
    cin >> t;
    int dx[] = {0, 0, -1, 1, 1, -1, 1, -1};
    int dy[] = {1, -1, 0, 0, 1, -1, -1, 1};
    for(int i = 0; i < t; i++){
        toogle = false;
        c = 0;
        cin >> n >> m;
        vector<vector<int>> v(n, vector<int>(m));
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                scanf("%1d", &v[j][k]);
                if(v[j][k]) c++;
            }
        }
        if(!c){
            cout << 0 << "\n";
            continue;
        }
        else if(n*m == c){
            cout << c - 2 << "\n";
            continue;
        }
        for(int j = 0; j < n; j++){
            if(toogle) break;
            for(int k = 0; k < m; k++){
                if(toogle) break;
                if(!v[j][k]){
                    for(int l = 0; l < 8; l++){
                        int ny = j + dy[l];
                        int nx = k + dx[l];
                        if(nx >= 0 && ny >= 0 && nx < m && ny < n && !v[ny][nx]){
                            cout << c << "\n";
                            toogle = true;
                            break;
                        }
                    }
                }
            }
        }
        if(!toogle) cout << c - 1 << "\n";
    }

    return 0;
}

 

업솔빙한 정답 코드이다.

 

 

확실히 코포 한번 치고 업솔빙까지 해보면 체력이 많이 소모가 된다. 그만큼 실력도 많이 느는거 같다. 대회 시간을 못맞출 경우 이전에 진행했던 대회를 똑같이 재현해서 실제 대회 하듯이 해볼 수 있는 버추얼이라는 기능도 있으니까 많이 해봐야겠다.

 

다음에는 Div.2에서 3솔을 할 수 있을것 같다. 안정적으로 3솔만 해도 그레이는 탈출하는것 같던데 빨리 탈출해야지..