Codeforces Round #619 (Div. 2)

Date : 2020.02.13 - 2020.02.14

PM 11:35 ~ AM 1:35

Codeforces URL

Result

제한 시간 동안 6문제 중 5문제를 해결했다.

이번 코드포스 라운드는 6개의 문제로 이루어진 rated for div.2 라운드였다. 지금까지 풀어봤던 라운드 중에서도 특히 빠르고 정확한 구현을 요구하는 문제들이 많았다. 직관에서 비롯된 아이디어를 전혀 사용하지 않는 것은 아니지만 비중이 작은 편이니, 오랫동안 머리를 싸매고 고민하는 것이 싫거나 구현 연습을 하고 싶다면 돌아보는 것을 추천한다.

 

A. Three strings (solved at. 2 min, +)

오랜만에 div.2를 해서 그런지 타임스탬프에 00:02가 찍히는 희귀한 광경을 목격할 수 있었다. 당시 스코어보드에서 공동 21등이었던 것으로 기억하는데 2분보다 빨리 푼 사람이 20명 정도 있다는 사실이 놀라울 따름이다.

 

풀이

String의 i번째 문자마다 $A[i]==C[i]$ 또는 $B[i]==C[i]$ 를 만족하면 $A[i]==B[i]$가 되도록 바꿔줄 수 있다. 따라서 $O(n)$만에 조건을 만족하는지 확인해 줄 수 있다.

코드

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
const int MN = 2e5+5;
bool ch[MN];

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    int T;
    string A,B,C;
    cin >> T;
    while(T--){
        cin >> A >> B >> C;
        bool pos = 1;
        for(int i=0; i<A.size(); i++){
            if(A[i]==B[i]&&C[i]!=A[i]) pos = 0;
            if(A[i]!=C[i]&&B[i]!=C[i]&&A[i]!=B[i]) pos = 0;
        }
        if(pos) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

B. Motarack's Birthday (solved at. 8 min, +)

B번 문제 역시 쉬운 편이었고, 문제를 읽으면서 풀이를 떠올리고 바로 코딩에 들어갔다. A번에서 상당히 좋은 스타트를 끊었기 때문인지 평소보다 집중해서 구현했고, 다행히 놓친 부분 없이 한번에 AC를 받았다.

 

풀이

$|a_{i}-a_{i+1}|$의 값은 $a_{i}$와 $a_{i+1}$에 따라 세 가지 경우로 나누어 생각해 볼 수 있다.
둘 다 -1이 아닌 경우 : $O(n)$만에 전처리를 통해 최댓값을 미리 구해줄 수 있다.
둘 다 -1인 경우 : 두 수의 차이는 0이므로 무시해도 된다.
둘 중 -1이 한 개인 경우 : 이때 고려해줘야 하는 $|k-a_{i}|$들을 잘 생각해보면, -1과 인접한 $a_{i}$들 중에서 가장 작은 값과 가장 큰 값의 평균으로 $k$를 정하는 것이 $m$을 최소화하는 방법임을 알 수 있다. 따라서 그러한 $a_{i}$의 최솟값과 최댓값을 입력을 받으면서 $O(n)$만에 계산해 주면 된다.

코드

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
const int MN = 2e5+5;
int A[MN];
vector<int> V;
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        int N,M=0,L=1e9+1,H=-1;
        cin >> N;
        for(int i=1; i<=N; i++) cin >> A[i];
        for(int i=1; i<N; i++){
            if(A[i]==-1&&A[i+1]==-1) continue;
            if(A[i]>=0&&A[i+1]>=0) M = max(M,abs(A[i+1]-A[i]));
            else{
                if(A[i]==-1){
                    L = min(L,A[i+1]);
                    H = max(H,A[i+1]);
                }
                else{
                    L = min(L,A[i]);
                    H = max(H,A[i]);
                }
            }
        }
        if(H==-1) cout << M << ' ' << 0 << '\n';
        else{
            int K = (L+H)/2;
            M = max(M,H-K);
            cout << M << ' ' << K << '\n';
        }
    }
}

 

C. Ayoub's function (solved at. 14 min, +)

이 문제는 그리디한 풀이를 깊게 생각하지 않고 제출해 proof by AC를 했는데다 코드 길이는 A번보다 짧은데도 시간이 꽤 걸렸다. 그리디 풀이를 제출할 때는 항상 문제를 믿고(?) 빨리 제출하는 것과 틀렸을 때의 하이 리스크를 생각해 철저히 검증하는 것 사이에서 고민하게 되는데, 이번에는 그리디가 꽤 뻔한 해법일 수밖에 없어서 망설이지 말고 내는 것이 맞는 판단이었던 것 같다.

 

풀이

주어진 문제는 0....000과 같이 0이 연속한 각 구간의 길이의 제곱의 합을 최소화하는 배치를 찾는 것과 같고, 1을 한 개 놓을 수 있을 때 생각해보면 1의 양 옆 구간의 0개수의 차이가 최소가 되도록 하는 것이 최적이므로 1이 여러개일때도 마찬가지로 모든 0이 연속한 구간의 길이를 최대한 균등하게 분포하도록 하는 것이 그리디한 해법이라는 것을 알 수 있다.

코드

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
const int MN = 2e5+5;
ll X,Y,N,M;

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        N,M;
        cin >> N >> M;
        for(int i=0; i<=M; i++)
        X = (N-M)/(M+1);
        Y = (N-M)%(M+1);
        cout << N*(N+1)/2 - (X+1)*(X+2)/2*Y - X*(X+1)/2*(M+1-Y) << '\n';
    }
}

 

D. Time to Run (solved at. 44 min, +2) 

친절하게도 문제에 최대 간선 개수가 주어져 있어 코딩할 때 아무 생각없이 사용할 수 있었던 점이 꽤 좋았다. 하지만 N=1이나 M=1일때를 if문에서 제대로 고려하지 않아서 2번이나 틀렸다. 정작 N, M이 최대일 때는 직접 넣어서 확인했는데도 틀렸기 때문에 더욱 당황해서 첫 제출이 34분이었는데도 불구하고 +10분과 +2틀이라는 패널티를 떠안고 가게 되었다. 이때 조금만 침착했더라면 등수가 달라졌을 것 같아 무척이나 아쉬운 부분이다.

 

풀이

그림을 직접 그리거나 머릿속에서 생각으로 이리저리 왔다갔다 해보면 왠지 모든 간선을 다 사용하는 방법이 존재할 것 같다는 강력한 예감을 받을 수 있다. 굳이 그러지 않더라도 이처럼 방법을 출력하는 문제는 "X,Y,Z빼고 다 된다" 거나 "X,Y,Z만 된다"의 둘 중 하나인 경우가 많기 때문에 경험을 통해 파악할 수 있는 부분이기도 하다.

 

따라서 적당한 N, M에 대해 열심히 모든 간선을 사용하는 방법을 찾은 후에, 이를 모든 경우에 대해 일반화하고 3000번 안에 출력할 수 있도록 for문의 개수를 잘 조절하는 것이 핵심이다. 또한 처음 줄에서 앞으로 제시할 이동의 수를 출력해야 하는데, 어떻게 처리할지 고민하다가 그냥 이동 방법을 출력하는 부분을 복사해서 출력문(cout)을 cnt++로 대체하는 방식으로 제시할 이동의 수 cnt를 미리 구해주었다. 자세한 구현과 이동 경로는 코드에 나와있다.

코드

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
const int MN = 2e5+5;
bool ch[MN];
int N,M,K;
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> M >> K;
    int val = 4*N*M-2*N-2*M;
    if(K<=val){
        cout << "YES\n";
        int cnt = 0, X = K;
        for(int i=1; i<N; i++){
            if(X) X--, cnt++;
            if(M>1&&X) X -= min(X,M-1), cnt++;
            if(M>1&&X) X -= min(X,M-1), cnt++;
        }
        if(N>1&&X) X -= min(X,N-1), cnt++;
        for(int i=1; i<M; i++){
            if(X) X--, cnt++;
            if(N>1&&X) X -= min(X,N-1), cnt++;
            if(N>1&&X) X -= min(X,N-1), cnt++;
        }
        if(M>1&&X) X -= min(X,M-1), cnt++;

        cout << cnt << '\n';

        for(int i=1; i<N; i++){
            if(K) cout << 1 << " D\n", K--;
            if(M>1&&K) cout << min(K,M-1) << " R\n", K -= min(K,M-1);
            if(M>1&&K) cout << min(K,M-1) << " L\n", K -= min(K,M-1);
        }
        if(N>1&&K) cout << min(K,N-1) << " U\n", K -= min(K,N-1);

        for(int i=1; i<M; i++){
            if(K) cout << 1 << " R\n", K--;
            if(N>1&&K) cout << min(K,N-1) << " D\n", K -= min(K,N-1);
            if(N>1&&K) cout << min(K,N-1) << " U\n", K -= min(K,N-1);
        }
        if(M>1&&K) cout << min(K,M-1) << " L\n", K -= min(K,M-1);
    }
    else cout << "NO";
}

 

E. Nanosoft (solved at. 84 min, +2)

D번 문제가 꽤 구현할 부분이 있어서인지 E를 읽고는 '또 구현이야?' 하며 잠시 충격을 먹었다. 일단 2차원 행렬을 통해 각 문자를 관리하고 어떻게든 각각의 value를 저장해야 할텐데, for문을 잔뜩 사용해야 할 것 같아 풀기 전부터 잔뜩 귀찮아했던 것 같다. 이번에도 꼼꼼하게 확인했다고 생각했는데 결국 두번이나 틀려버렸다.

 

풀이

문제의 핵심은 쿼리가 들어왔을 때 주어진 직사각형 영역 안에 존재하는 로고의 최대 넓이를 구하는 것이다. 이때, 한 변의 길이가 $2k$인 로고는 변의 길이가 $2k$이하인 로고를 모두 포함하기 때문에, 이분탐색을 사용하면 주어진 직사각형 영역에서 길이 $2k$ 로고의 존재 여부를 판별하는 문제로 바꿀 수 있다.

 

만약 길이가 $2k$인 로고가 영역 $r\leq x\leq r+2k-1,c\leq y\leq c+2k-1$에 존재한다면 $(r,c)$에 표시를 하자. 그렇다면 우리는 직사각형 $r1\leq x\leq r1-2k+1,c1\leq y\leq c2-2k+1$안에 표시된 칸이 존재하는지 확인함으로써 길이 $2k$인 로고의 존재 여부를 판별할 수 있다. 그렇다면 길이 $2k$짜리 로고가 존재하는 위치는 어떻게 찾을 수 있을까?

 

주어진 로고는 한 변의 길이가 $k$인 서로 다른 색깔 정사각형 4개를 합친 모양이라는 것을 생각하자.

먼저 각 칸 $(r,c)$에 대해 '해당 칸을 왼쪽 위 꼭짓점으로 하고, 각 칸의 색이 모두 같은 정사각형의 최대 길이'를 저장해 줄 것이다. 이 작업은 DP를 통해 $O(N^3)$만에 시행할 수 있다.

 

그리고 $(r,c),(r+k,c),(r,c+k),(r+k,c+k)$를 왼쪽 위 꼭짓점으로 하는 길이 $k$짜리 빨강, 노랑, 초록, 파랑색 정사각형이 존재한다면 $(r,c)$를 왼쪽 위 꼭짓점으로 하는 길이가 $2k$인 로고가 존재한다는 것을 알 수 있게 된다. 

 

그리고 구한 로고들을 변의 길이에 따라 DP의 일종인 2차원 부분합으로 $O(N^3)$ 전처리를 해주면 쿼리가 들어왔을 때 직사각형 $r1\leq x\leq r1-2k+1,c1\leq y\leq c2-2k+1$안에 표시된 칸이 존재하는지 $O(1)$만에 확인할 수 있고, 이분탐색을 사용했으므로 총 시간복잡도는 전처리 $O(N^3)$, 쿼리 $O(QlgN)$으로 총 $O(N^3+QlgN)$만에 해결할 수 있다.

코드

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
const int MN = 501;
int L[MN][MN],r1,c1,r2,c2,N,M,Q;
int A[MN][MN][251];
char C[MN][MN];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> M >> Q;
    int X = min(N/2,M/2);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            cin >> C[i][j], L[i][j] = 1;
    for(int k=2; k<=X; k++){
        for(int i=1; i+k-1<=N; i++){
            for(int j=1; j+k-1<=M; j++){
                if(L[i][j]<k-1) continue;
                char c = C[i][j];
                if(L[i][j]==k-1&&L[i][j+1]==k-1&&L[i+1][j]==k-1&&L[i+1][j+1]==k-1)
                    if(C[i+1][j]==c&&C[i][j+1]==c&&C[i+1][j+1]==c)
                        L[i][j] = k;
            }
        }
    }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++){
            int k = L[i][j];
            if(i+2*k-1>N||j+2*k-1>M) continue;
            if(C[i][j]!='R'||C[i+k][j]!='Y'||C[i][j+k]!='G'||C[i+k][j+k]!='B') continue;
            if(L[i+k][j]<k||L[i][j+k]<k||L[i+k][j+k]<k) continue;
            A[i][j][k]++;
        }
    for(int k=1; k<=X; k++){
        for(int i=1; i+2*k-1<=N; i++)
                for(int j=1; j+2*k-1<=M; j++)
                    A[i][j][k] += A[i][j-1][k]+A[i-1][j][k]-A[i-1][j-1][k];
    }
    for(int i=1; i<=Q; i++){
        cin >> r1 >> c1 >> r2 >> c2;
        int s = 0, e = X, k;
        e = min(e,min((r2-r1+1)/2,(c2-c1+1)/2));
        while(s<e){
            k = (s+e+1)/2;
            if(A[r1-1][c1-1][k]+A[r2-2*k+1][c2-2*k+1][k]-A[r1-1][c2-2*k+1][k]-A[r2-2*k+1][c1-1][k]) s = k;
            else e = k-1;
        }
        cout << 4*s*s << '\n';
    }
}

 

F. Super Jaber

앞의 문제를 모두 풀고 남은 시간이 36분이어서 풀이를 빠르게 찾으면 올솔도 가능하겠다는 생각이 들었다. 문제를 보고 나서 DP를 통해 각 칸으로부터 특정한 색깔로 가는 데 걸리는 시간을 잘 구해주면 되겠다는 관찰을 한 후 코딩에 들어갔으나 시간 문제로 디버깅을 완료하지 못한 채 라운드가 끝나고 말았다. 결과적으로 그 당시 접근법은 시간복잡도가 커서 결국 TLE를 받았을 것이지만 아쉬운 느낌이 드는 것은 어쩔 수 없다.

 

풀이

어떤 방식으로 구현하든, 핵심은 결국 같은 색깔의 칸끼리 이동할 수 있다는 사실을 어떻게 처리하느냐에 달려 있다. 가장 먼저 드는 생각은 각 색깔별로 더미 노드를 만들어서 최단 거리를 관리해주는 것이다. 예를 들어, 색깔 k인 정점에서 '색이 k인 더미노드'로 가는 데 시간이 1 소요되고, '색이 k인 더미노드'에서 색깔이 k인 임의의 정점으로 가는 데 시간이 0 소요된다고 생각하더라도 문제에는 아무런 영향을 주지 않는다.

 

이처럼 같은 색깔 사이의 이동을 더미 노드를 통해 표현할 경우, 정점 A에서 정점 B로 가는 경로에 더미 노드가 존재하지 않는다면 그 경로에 소요되는 시간은 두 정점 사이의 택시 거리이다. 만약 경로 상에 더미노드 k가 존재한다면 소요 시간은 (A -> 더미노드 k) + (더미노드 k ->B)일 것이므로, 우리는 각각의 더미 노드로부터 모든 칸까지 가는 데 걸리는 시간을 전처리해준 뒤 모든 더미 노드에 대해 위 값을 계산해주는 방식으로 각 쿼리를 $O(K)$만에 처리할 수 있을 것이다.

 

이제 문제는 정점 k개에 대해 각 정점으로부터 나머지 모든 정점까지의 최단거리를 구하는 것으로 바뀐다. 좌표계에서 인접한 두 칸 사이의 길이 1짜리 양방향 간선, 각각의 칸들로부터 자신과 같의 색의 더미노드로 가는 길이 1짜리 방향이 있는 간선과 그 더미노드로부터 각각의 칸으로 가는 길이 0짜리 방향이 있는 간선으로 구성된 그래프를 생각하면 그래프의 정점과 간선은 $O(N^2)$개이며, 0-1 BFS를 통해 $K$개 더미 노드로부터 다른 정점까지 최단거리를 $O(N^2K)$만에 구할 수 있다.

 

혹은 굳이 더미 노드를 명시적으로 추가하지 않더라도 최단거리를 구하는 방법 또한 존재한다. 더미노드 k와 색깔 k인 칸 사이의 최단거리를 0으로 두고, 이들을 모두 Queue에 넣은 후 BFS를 실행하되, 현재 보고 있는 칸의 거리가 $dis$, 색깔이 $col$이고, $col$이 BFS에서 처음 등장하는 색깔이라면, 색깔이 $col$인 모든 칸의 최단거리와 $dis+1$을 비교해 Queue에 업데이트해주면 된다. 이는 주어진 조건을 간선으로 만들지 않고 BFS 과정에서 해결해주는 방법으로, 위의 것과 같은 시간복잡도를 가진다. 하단에 제시된 코드는 이처럼 간선을 만들지 않고 BFS하는 방법으로 구현되어 있다.

 

따라서 총 시간복잡도 $O(N^2K+QK)$만에 문제를 해결할 수 있다.

코드

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
const int MN = 1005;
int N,M,K,A[MN][MN],D[MN][MN][41],F[MN][MN],Q,r1,c1,r2,c2,ans;
bool ch[41];
queue<ppi> Qu[41];
vector<pii> V[41];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> M >> K;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++){
            for(int k=1; k<=K; k++)
                D[i][j][k] = 200;
            int c;
            cin >> c;
            A[i][j] = c;
            D[i][j][c] = 0;
            Qu[c].emplace(pii(i,j),0);
            V[c].emplace_back(i,j);
        }
    for(int k=1; k<=K; k++){
        for(int i=1; i<=K; i++) ch[i] = 0;
        while(Qu[k].size()){
            pii p = Qu[k].front().va;
            int c = A[p.va][p.vb], dis = Qu[k].front().vb;
            Qu[k].pop();
            if(!ch[c]){
                for(pii q: V[c]){
                    if(D[q.va][q.vb][k]!=200) continue;
                    D[q.va][q.vb][k] = dis+1;
                    Qu[k].emplace(q,dis+1);
                }
                ch[c] = 1;
            }
            if(p.vb<M&&D[p.va][p.vb+1][k]==200){
                D[p.va][p.vb+1][k] = dis+1;
                Qu[k].emplace(pii(p.va,p.vb+1),dis+1);
            }
            if(p.vb>1&&D[p.va][p.vb-1][k]==200){
                D[p.va][p.vb-1][k] = dis+1;
                Qu[k].emplace(pii(p.va,p.vb-1),dis+1);
            }
            if(p.va<N&&D[p.va+1][p.vb][k]==200){
                D[p.va+1][p.vb][k] = dis+1;
                Qu[k].emplace(pii(p.va+1,p.vb),dis+1);
            }
            if(p.va>1&&D[p.va-1][p.vb][k]==200){
                D[p.va-1][p.vb][k] = dis+1;
                Qu[k].emplace(pii(p.va-1,p.vb),dis+1);
            }
        }
    }
    cin >> Q;
    for(int i=1; i<=Q; i++){
        cin >> r1 >> c1 >> r2 >> c2;
        ans = abs(r2-r1)+abs(c2-c1);
        for(int k=1; k<=K; k++){
            ans = min(ans,D[r1][c1][k]+D[r2][c2][k]+1);
        }
        cout << ans << '\n';
    }
}

 

총평

for문이 많고 기본적으로 구현량이 꽤 있는 D와 E에서 2번이나 틀렸다. ICPC 셋을 진행할 때도 매번 실수를 해서 패널티를 많이 받았었는데, 이번을 계기로 코딩의 정확도가 많이 떨어진다는 것을 뼈저리게 느낄 수 있었으며, 적당한 난이도의 구현 문제를 한 번에 짜서 맞는 연습을 할 필요가 있을 것 같다.

 

목표 : 코딩이 완료된 후에 2~3분 동안 예제를 몇 개 만들어 넣어본 뒤에 제출해서 한 번에 맞는 연습하기 (0/10)