Codeforces Round #706

작성일 | In

Div2A. Split it!

앞 $K$글자와 뒤 $K$글자를 뒤집은 것이 같고, 가운데 다른 문자열이 들어갈 수 있는지 판별하면 됩니다.

1
2
3
4
5
6
7
8
void Solve(){
    string S; int N, K; cin >> N >> K >> S;
    for(int i=0; i<K; i++){
        if(S[i] != S[N-i-1]){ cout << "NO\n"; return; }
    }
    if(K+K < N) cout << "YES\n";
    else cout << "NO\n";
}

Div2B. Max and Mex

관찰 1. 만약 초기 multiset의 mex값이 $N$이라면 연산을 할 때마다 set의 크기가 증가합니다.
관찰 2. 그렇지 않다면 set의 크기는 $O(N)$번 증가합니다.
관찰 1은 자명하고, 관찰 2는 계속 크기가 증가하다가 어느 순간 기존에 존재하던 원소에 의해 막힌다는 것을 보이면 됩니다.

그러므로 $mex(a) = N$이면 $N + K$을 출력하고, 그렇지 않다면 문제에 나와있는 과정을 시뮬레이션하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll N, K, A[101010];

void Solve(){
    cin >> N >> K; for(int i=1; i<=N; i++) cin >> A[i];
    sort(A+1, A+N+1);
    set<int> st(A+1, A+N+1);

    bool chk = true;
    for(int i=1; i<=N; i++) if(A[i] != i-1) chk = false;
    if(chk){ cout << A[N] + K + 1<< "\n"; return; }

    int mex = 0;
    for(int i=1; i<=K; i++){
        while(st.count(mex)) mex++;
        int mx = *st.rbegin();
        int nxt = (mex + mx + 1) >> 1;
        if(st.count(nxt)) break;
        else st.insert(nxt);
    }
    cout << st.size() << "\n";
}

Div2C/Div1A. Diamond Miner

$x, y$좌표에 각각 절댓값을 취해도 답이 바뀌지 않는다는 것은 쉽게 알 수 있습니다. 일반성을 잃지 않고, $x \geq 0, y \geq 0$이라고 합시다. 어떤 매칭이 교차한다면 교차하지 않도록 풀어주는 것이 항상 이득이라는 것을 증명할 수 있습니다.
그러므로 $x, y$좌표에 각각 절댓값을 취하고 정렬한 뒤, 순서대로 매칭해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Solve(){
    vector<int> X, Y;
    int N; cin >> N;
    for(int i=0; i<N+N; i++){
        int x, y; cin >> x >> y;
        if(x) X.push_back(abs(x));
        else Y.push_back(abs(y));
    }
    sort(all(X)); sort(all(Y));

    long double ans = 0;
    for(int i=0; i<N; i++) ans += hypot(X[i], Y[i]);
    cout << fixed << setprecision(15) << ans << "\n";
}

Div2D/Div1B. Let’s Go Hiking

정신나간 CaseWork 문제

설명의 편의를 위해 $x, y$의 시작 지점을 각각 $x_0, y_0$이라고 합시다. 게임의 형태를 4가지 케이스로 분류할 수 있습니다.

  • case 1) y0 < x0 && y는 왼쪽으로 이동 (서로 거리가 멀어짐)
  • case 2) y0 > x0 && y는 오른쪽으로 이동 (서로 거리가 멀어짐)
  • case 3) y0 < x0 && y는 오른쪽으로 이동 (서로 거리가 가까워짐)
  • case 4) y0 > x0 && y는 왼쪽으로 이동 (서로 거리가 가까워짐)

4가지 케이스를 고려하면서, 어떤 $x_0$이 이기는 위치인지 Sub-linear Time에 판별하는 것이 목표입니다.

배열 6개를 정의합시다. 이 배열들은 투포인터(or 슬라이딩 윈도우) 느낌으로 $O(N)$에 전처리할 수 있습니다.

  • DecL[i] : i에서 시작해서 왼쪽으로 내려갈 수 있는 마지막 위치 (Qingshan이 i에서 시작해 갈 수 있는 가장 왼쪽)
  • DecR[i] : i에서 시작해서 오른쪽으로 내려갈 수 있는 마지막 위치
  • IncL[i] : i에서 시작해서 왼쪽으로 올라갈 수 있는 마지막 위치 (Daniel이 i에서 시작해 갈 수 있는 가장 왼쪽)
  • IncR[i] : i에서 시작해서 오른쪽으로 올라갈 수 있는 마지막 위치
  • CntL[i] : i - DecL[i] (i에서 시작해서 Qingshan이 왼쪽으로 이동할 수 있는 최대 거리)
  • CntR[i] : DecR[i] - i (i에서 시작해서 Qingshan이 오른쪽으로 이동할 수 있는 최대 거리)

case 1은 $y < x_0$인 모든 $y$에 대해, $y - IncL[y] < \max(CntL[x_0], CntR[x_0])$인지 확인하면 됩니다.
case 2는 $y > x_0$인 모든 $y$에 대해, $IncR[y] - y < \max(CntL[x_0], CntR[x_0])$인지 확인하면 됩니다.
Prefix/Suffix Maximum을 관리하면 $O(1)$에 처리할 수 있고, Maximum Segment Tree를 이용하면 $O(\log N)$에 처리할 수 있습니다.

case 3, 4도 비슷하게 처리할 수 있으면 좋았겠지만, 아쉽게도 두 사람이 모두 도달할 수 있는 위치가 존재하기 때문에 다양한 경우가 생겨 이 풀이를 그대로 적용할 수 없습니다. case 3부터 봅시다. 5가지 케이스로 나눌 수 있습니다.

  • case 3-1) 구간이 만남 + x는 왼쪽으로 이동
    • case 3-1-1) x0과 y0의 거리는 짝수
    • case 3-1-2) x0과 y0의 거리는 홀수
  • case 3-2) 구간이 만남 + x는 오른쪽으로 이동
  • case 3-3) 구간 안 만남 + x는 왼쪽으로 이동
  • case 3-4) 구간 안 만남 + x는 오른쪽으로 이동

case 3-1-1에서 $x_0$은 무조건 이기는 위치가 됩니다. 비슷하게, 3-1-2에서는 무조건 지는 위치입니다.
case 3-2는 $y < x_0$인 모든 $y$에 대해, $IncR[y] - y < CntR[x_0]$인지 확인하면 됩니다.
case 3-3은 $y < x_0$인 모든 $y$에 대해, $IncR[y] - y < CntL[x_0]$인지 확인하면 됩니다.
case 3-4는 case 3-2와 동일하게 처리해도 됩니다.

그러므로,
구간이 만나는 $y_0$에 대해서는 거리가 짝수이면 승리, 홀수이면 오른쪽으로 이동해서 $IncR[y_0] - y_0 < CntR[x_0]$인지 확인하면 됩니다.
구간이 만나지 않는 $y_0$에 대해서는 $IncR[y_0] - y_0 < \max(CntL[x_0], CntR[x_0])$인지 확인하면 됩니다.
이때 구간이 만나는 $y_0$의 범위는 $[DecL[x_0], x_0)$이며, 구간이 만나지 않는 $y_0$의 범위는 $[1, DecL[x_0])$입니다.

비슷하게 case 4도 5가지의 케이스로 나누어서 해결할 수 있습니다.
구간이 만나는 $y_0$에 대해서는 거리가 짝수이면 승리, 홀수이면 왼쪽으로 이동해서 $y_0 - IncL[y_0] < CntL[x_0]$인지 확인하면 됩니다.
구간이 만나지 않는 $y_0$에 대해서는 $y_0 - IncL[y_0] < \max(CntL[x_0], CntR[x_0])$인지 확인하면 됩니다.
이때 구간이 만나는 $y_0$의 범위는 $(x_0, DecR[x_0]]$이며, 구간이 만나지 않는 $y_0$의 범위는 $(Dec[x_0], N]$입니다.

case 3, 4는 Maximum Segment Tree를 이용해 $O(\log N)$에 해결할 수 있습니다.

총 12가지 케이스를 모두 고려해주면 투포인터와 세그먼트 트리를 이용한 $O(N \log N)$ 풀이를 얻을 수 있고, 그대로 코딩하면 문제를 해결할 수 있습니다.

이런 환상적인 문제를 세팅한 Setter와 Tester분들께 존경을 표합니다…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

struct SegmentTree{
    static const int S = 1 << 17;
    int T[S << 1];
    void Update(int x, int v){
        x |= S; T[x] = v;
        while(x >>= 1) T[x] = max(T[x << 1], T[x << 1 | 1]);
    }
    int Query(int l, int r){
        l |= S; r |= S; int ret = 0;
        while(l <= r){
            if(l & 1) ret = max(ret, T[l++]);
            if(~r & 1) ret = max(ret, T[r--]);
            l >>= 1; r >>= 1;
        }
        return ret;
    }
};

int N, A[101010];
int DecL[101010], DecR[101010];
int IncL[101010], IncR[101010];

int CntL[101010], CntR[101010];
SegmentTree segL[3], segR[3];

void Init(){
    int dec = 1, inc = 1;
    for(int i=1; i<=N; i++){
        dec = max(dec, i); inc = max(inc, i);
        while(dec < N && A[dec] > A[dec+1]) dec++;
        while(inc < N && A[inc] < A[inc+1]) inc++;
        DecR[i] = dec; IncR[i] = inc;
    }

    dec = inc = N;
    for(int i=N; i>=1; i--){
        dec = min(dec, i); inc = min(inc, i);
        while(dec > 1 && A[dec] > A[dec-1]) dec--;
        while(inc > 1 && A[inc] < A[inc-1]) inc--;
        DecL[i] = dec; IncL[i] = inc;
    }

    for(int i=1; i<=N; i++){
        segL[i&1].Update(i, i - IncL[i]);
        segR[i&1].Update(i, IncR[i] - i);

        segL[2].Update(i, i - IncL[i]);
        segR[2].Update(i, IncR[i] - i);

        CntL[i] = i - DecL[i];
        CntR[i] = DecR[i] - i;
    }
}

bool chk(int x){
    if(segL[2].Query(1, x-1) >= max(CntL[x], CntR[x])) return false; // case 1: y0 < x0 && y goes left
    if(segR[2].Query(x+1, N) >= max(CntL[x], CntR[x])) return false; // case 2: y0 > x0 && y goes right

    if(segR[~x&1].Query(DecL[x], x-1) >= CntR[x]) return false; // case 3-1,2: y0 < x0 && y goes right && players can meet
    if(segL[~x&1].Query(x+1, DecR[x]) >= CntL[x]) return false; // case 4-1,2: y0 > x0 && y goes left && players can meet

    if(segR[~x&1].Query(1, x-1) >= max(CntL[x], CntR[x])) return false; // case 3-3,4: y0 < x0 && y goes right && players never meet
    if(segL[~x&1].Query(x+1, N) >= max(CntL[x], CntR[x])) return false; // case 4-3,4: y0 > x0 && y goes left && players never meet

    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N; for(int i=1; i<=N; i++) cin >> A[i];
    Init();

    int ans = 0;
    for(int i=1; i<=N; i++) ans += chk(i);
    cout << ans;
}

Div2E/Div1C. Garden of Sun

대회 중에는 Manhattan MST로 접근했다가 망했습니다. 대회 끝나고 Aeren님께 풀이를 들었습니다.

$i \mod 3 \equiv 0$인 행을 모두 칠하고, 이렇게 칠한 부분을 “줄기”라고 합시다.
$i \mod 3 = 1\ or\ 2$인 행에 'X'가 있을텐데, 이런 칸들은 “줄기”에서 “가지”를 뻗어서 연결하면 됩니다.

혹시 $3K$번째 행과 $3K+3$번째 행을 연결하는 가지를 뻗지 못했다면 임의로 한 지점을 잡아서 연결하면 됩니다.

$N$이 3의 배수인 경우를 조심합시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int N, M;
char A[555][555];

void Solve(){
    cin >> N >> M;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) cin >> A[i][j];
    for(int i=1; i<=N; i+=3){
        for(int j=1; j<=M; j++) A[i][j] = 'X';
        if(i == 1) continue;

        for(int j=1; j<=M; j++){
            if(j == M || A[i-1][j] == 'X' || A[i-2][j] == 'X'){
                A[i-1][j] = A[i-2][j] = 'X'; break;
            }
        }
    }

    if(N % 3 == 0){
        for(int j=1; j<=M; j++) if(A[N][j] == 'X') A[N-1][j] = 'X';
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) cout << A[i][j];
        cout << "\n";
    }
}