티스토리 뷰

정보과학/Codeforces

Codeforces Round #578

leejseo 2019. 8. 12. 09:31

한국인 두 분(hyunuk, djm03178)께서 주최한 라운드라 직접 응시해봤다. 한동안 PS를 하지 않다가 다시 시작하는 상태라 구현이 느리고 사소한 오류를 잡기 힘든 상태라 레이팅이 떨어질 것 같았지만, 언제까지나 대회 치는걸 미룰 수는 없는 것 아닌가.

 

어쨌든 대회를 쳤고, A, B, C, E 4개의 문제를 풀었고, D는 사소한 코딩 미스 때문에 맞는 접근으로 WA를 받았고, 훨씬 간편하고 코딩 미스를 방지할 수 있는 구현을 대회 종료 몇 초 후에 떠올렸다는 점에서 너무나도 아쉬움이 크다. 게다가, E에서 해싱을 잘못 짠 것과 오타 때문에 8번의 불필요한 제출, 그리고 B에서 코딩 미스 때문에 2번의 불필요한 제출을 했다는 점도 너무나 아쉽다. 하지만, 이런 부분은 꾸준히 대회를 치면 잡힐거라 보기에 레이팅은 1910에서 1892로 떨어졌으나 쉽게 다시 올라갈 수 있을 것 같다.

 

참고로, 이 라운드는 Div. 2 라운드였다.

 

링크: https://codeforces.com/contest/1200

A. Hotelier

그냥 문제에 적힌 대로 구현하면 $O(N)$ 시간 복잡도에 해결할 수 있다. 아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
bool B[11];
char C[100005];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    cin >> C;
    for (int i=0; i<N; i++){
        if (C[i] == 'L'){
            for (int j=0; j<10; j++){
                if (!B[j]){
                    B[j] = 1; break;
                }
            }
        }
        else if (C[i] == 'R'){
            for (int j=9; j>=0; j--){
                if (!B[j]){
                    B[j] = 1; break;
                }
            }
        }
        else{
            B[C[i]-'0'] = 0;
        }
    }
    for (int i=0; i<10; i++) cout << (int)B[i];
    cout << endl;
}

B. Block Adventure

그리디 전략을 사용하여 접근할 수 있다. 블럭을 가져갈 수 있을 때는 한 번에 최대한 많은 블럭을 가져가고, 블럭을 내려놓아야 할 때는 한 번에 최소한의 블럭을 내려놓으면 된다. 그 이유는 운반 가능한 블럭의 양이 무수히 많기 때문이다. 이 전략을 구현해주면 $O(TN)$의 시간복잡도에 문제를 해결할 수 있다. 아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int T, N, M, K;
 
int H[100];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--){
        cin >> N >> M >> K;
        memset(H, 0, sizeof(H));
        for (int i=0; i<N; i++) cin >> H[i];
        bool suc = true;
        for (int i=1; i<N; i++){
            if (H[i-1]+K < H[i]){
                if (H[i-1]+M < H[i]-K){
                    suc = false;
                    break;
                }
                M -= max(0, H[i]-K-H[i-1]);
            }
            else{
                int goal = min(H[i-1], H[i-1]-H[i]+K);
                M += goal;
            }
        }
        if (suc) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}

C. Round Corridor

두 정수 $n, m$의 최대공약수를 $g$라 하자. 그러면, 원판은 서로 "단절된" $g$개의 구역으로 나뉘게 되고, 각 구역에는 연속한 $n/g$개의 안쪽 원판과 $m/g$개의 바깥쪽 원판이 속하게 된다. 두 점이 연결되어 있을 필요충분조건은 같은 구역에 속하는 것이기에, 이를 그대로 코드로 구현해주면 $O(Q+\log N+\log M)$에 문제를 해결할 수 있다. 아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
lld gcd(lld b, lld s){
    return s ? gcd(s, b%s) : b;
}
 
lld N, M;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    lld G = gcd(N, M);
    lld n = N/G, m = M/G;
    int Q;
    cin >> Q;
    while (Q--){
        int sx, ex; lld sy, ey;
        cin >> sx >> sy >> ex >> ey;
        --sy; --ey;
        int rs, re;
        if (sx == 1) rs = sy/n;
        else rs = sy/m;
        if (ex == 1) re = ey/n;
        else re = ey/m;
        cout << (rs == re ? "YES" : "NO") << '\n';
    }
}

D. White Lines

이 문제에서 가장 핵심이 되는 관찰은 행과 열을 독립적으로 간주할 수 있다는 것이다. $O(N^2)$ 시간 복잡도에 다음을 전처리 할 수 있다:

  • $A[i]$: $i$행에서 가장 왼쪽의 검은 칸의 위치

  • $B[i]$: $i$행에서 가장 오른쪽의 검은 칸의 위치

  • $C[j]$: $j$열에서 가장 위쪽의 검은 칸의 위치

  • $D[j]$: $j$열에서 가장 아래쪽의 검은 칸의 위치

  • 처음부터 하얀 칸으로만 이루어진 행/열의 갯수

이들을 전처리 하고 나면, "$i$행에 정사각형의 왼쪽 위 꼭짓점이 위치할 때, $j$열의 검은 칸들이 모두 하얀 칸이 되는가?" 와 "$j$열에 정사각형의 왼쪽 위 꼭짓점이 위치할 때, $i$행의 검은 칸들이 모두 하얀 칸이 되는가?"와 같은 질의를 하나당 $O(1)$ 시간에 계산할 수 있다. 이를 활용하면 총 $O(N^2)$ 시간에 답을 구할 수 있다. 구현은 따로 첨부하지 않는다.

E. Compress Words

KMP와 $\pi$ 배열을 활용하는 풀이로 처음에는 접근했으나, KMP에 대한 이해도가 낮은 관계로 해싱을 이용하여 해결하였다. Rabin-Karp 알고리즘에서 활용하는 것과 마찬가지로 해싱을 이용했고, modulo는 총 3개를 활용하였다. 상수가 다소 큰 $O(N)$ 시간 복잡도로 문제를 해결할 수 있다. 아래는 나의 C++ 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long lld;
 
int M = 3;
 
const lld mod[]= {1000000007, 998244353, 1000000009, 2013265921};
const lld bas[] = {2, 3, 63, 89};
string S[100005];
int N;
 
lld p[1000005][4], q[1000005][4];
 
lld modmul[1000005][4];
 
lld sv[4], tv[4];
 
string ret = "";
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i=0; i<N; i++) cin >> S[i];
    ret = S[0];
    int n = S[0].size();
    for (int j=0; j<M; j++) modmul[0][j] = 1;
    for (int i=1; i<1000001; i++){
        for (int j=0; j<M; j++){
            modmul[i][j] = modmul[i-1][j] * bas[j];
            modmul[i][j] %= mod[j];
        }
    }
    for (int i=0; i<n; i++){
        for (int j=0; j<M; j++){
            p[i+1][j] = p[i][j]*bas[j] + ((int)S[0][i]);
            p[i+1][j] %= mod[j];
        }
    }
    for (int tt=1; tt<N; tt++){
        string &t = S[tt];
        int m = t.size();
        for (int i=0; i<m; i++){
            for (int j=0; j<M; j++){
                q[i+1][j] = q[i][j]*bas[j] + ((int)t[i]);
                q[i+1][j] %= mod[j];
            }
        }
        bool done = false;
        int mlap = -1;
        for (int k=1; k<=min(n, m); k++){
            bool eqv = true;
            for (int j=0; j<M; j++){
                lld diff = p[n-k][j]*modmul[k][j];
                diff %= mod[j];
                sv[j] = (p[n][j] - diff +mod[j])%mod[j];
                tv[j] = q[k][j];
                if (sv[j] != tv[j]){
                    eqv = false;
                    break;
                }
            }
            if (eqv){
                if (true){
                    done = true;
                    mlap = k;
                }
            }
        }
        if (done){
            for (int k=0; k<m-mlap; k++){
                for (int j=0; j<M; j++){
                    lld diff = q[mlap][j] * modmul[k+1][j];
                    diff %= mod[j];
                    p[n+k+1][j] = (q[mlap+k+1][j] - diff + mod[j]) % mod[j];
                    p[n+k+1][j] += (p[n][j] * modmul[k+1][j])%mod[j];
                    p[n+k+1][j] %= mod[j];
                }
            }
            ret.append(t, mlap, m);
            n += m-mlap;
        }
        else{
            for (int k=0; k<m; k++){
                for (int j=0; j<M; j++){
                    p[n+k+1][j] = q[k+1][j];
                    p[n+k+1][j] += (p[n][j] * modmul[k+1][j]) % mod[j];
                    p[n+k+1][j] %= mod[j];
                }
            }
            ret.append(t);
            n += m;
        }
    }
    cout << ret << endl;
}

여담

좋은 라운드를 만들어주신 두 분 및 검수진들께 감사하다는 말을 전하고 싶다. 무엇보다 공지의 아래와 같은 말이 귀엽고 반가웠다. 그리고 한국에서 참여하기 좋은 이른 시간대에 개최된다는 점도 좋았다.

안녕하세요, 코드포스! (Hello, Codeforces!)

'정보과학 > Codeforces' 카테고리의 다른 글

Educational Codeforces Round 71  (1) 2019.08.23
Codeforces Round #580  (1) 2019.08.19
Codeforces Round #578  (0) 2019.08.12
Codeforces Round #492  (0) 2019.08.06
Codeforces Round #576  (0) 2019.08.04
Codeforces Round 526 (Div 2) 후기  (0) 2018.12.11
댓글
댓글쓰기 폼