AtCoder ARC 069

작성일 | In

결과

CDF 풀고, E를 못 풀었습니다.
F는 정말 좋은 문제인 것 같습니다.

C. Scc Puzzle

S 1개와 C 2개를 묶어줍시다. C가 남았다면 C 4개를 묶어줍시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll a, b; cin >> a >> b;
    ll t = min(a, b/2); a -= t; b -= t+t;
    t += b/4;
    cout << t;
}

D. Menagerie

인접한 3마리의 동물의 종만 결정해주면 다른 동물들의 종을 모두 결정해줄 수 있습니다.
다른 동물들의 종을 정해주는 과정에서 모순이 생긴다면 인접한 3마리의 동물의 종을 다른 조합으로 시도해보면 됩니다.

$O(N)$짜리 프로세스를 최대 8번 진행하면 문제를 풀 수 있습니다.

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
#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())
using namespace std;

typedef long long ll;

int n, a[101010], res[101010];

int valid(int t1, int t2, int t3){
    res[1] = t1; res[2] = t2; res[3] = t3;
    for(int i=3; i<n; i++){
        if(res[i]){
            if(a[i]) res[i+1] = res[i-1];
            else res[i+1] = !res[i-1];
        }
        else{
            if(!a[i]) res[i+1] = res[i-1];
            else res[i+1] = !res[i-1];
        }
    }
    for(int i=1; i<=n; i++){
        int j = i-1 > 0 ? i-1 : n;
        int k = i+1 <= n ? i+1 : 1;
        if(res[i]){
            if(a[i] && res[j] != res[k]) return 0;
            if(!a[i] && res[j] == res[k]) return 0;
        }
        else{
            if(!a[i] && res[j] != res[k]) return 0;
            if(a[i] && res[j] == res[k]) return 0;
        }
    }
    for(int i=1; i<=n; i++) cout << (res[i] ? 'S' : 'W');
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        char c; cin >> c; a[i] = c == 'o';
    }

    for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) {
        if(valid(i, j, k)) return 0;
    }
    cout << -1;
}

E. Frequency

F. Flags

블로그에 따로 풀이를 올린 줄 알았는데 안 올렸네요.

가능한 가장 큰 값을 구하는 문제이니 파라메트릭 서치를 생각해봅시다.

각 깃발을 $x_i$ 혹은 $y_i$에 배치해야하고, 2-SAT을 생각해볼 수 있습니다. 간선을 $O(N^2)$개 만들어서 2-SAT을 하는 것은 생각하기 쉽지만 TLE나기도 쉽습니다. 간선 개수를 줄여야 합니다.

깃발들을 위치 순으로 정렬합시다. 어떤 깃발 $i$를 선택하면 구간 $[s_i, e_i]$ 에 있는 모든 깃발을 선택하면 안 된다고 표현할 수 있습니다.
구간을 $O(\log N)$개의 정점으로 나타내는 유명한 방법으로 세그먼트 트리가 있습니다. 깃발들을 직접 간선으로 잇는 대신, 세그먼트 트리의 정점과 이어주면 $O(N \log N)$개의 간선만 만들어지게 되고, 시간 내에 문제를 해결할 수 있습니다.

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
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

typedef pair<int, int> p;

namespace SCC{
    vector<int> g[1 << 17], r[1 << 17], dfn;
    int chk[1 << 17], pv;
    void dfs(int v){
        chk[v] = 1;
        for(auto i : g[v]){
            if(!chk[i]) dfs(i);
        }
        dfn.push_back(v);
    }
    void rdfs(int v, int color){
        chk[v] = color;
        for(auto i : r[v]){
            if(!chk[i]) rdfs(i, color);
        }
    }
    void getSCC(int n){
        memset(chk, 0, sizeof chk); dfn.clear();
        for(int i=0; i<n; i++) if(!chk[i]) dfs(i);
        memset(chk, 0, sizeof chk); pv = 0; reverse(all(dfn));
        for(auto i : dfn) if(!chk[i]) rdfs(i, ++pv);
    }
    void init(){
        for(int i=0; i<(1 << 17); i++){
            g[i].clear(), r[i].clear();
        }
    }
    void addEdge(int s, int e){
        g[s].push_back(e); r[e].push_back(s);
    }
};
using namespace SCC;

const int sz = 1 << 16, inv = 1 << 15;
int n, x[101010], y[101010], id[101010][2];
vector<p> pt;

void connect(int now, int l, int r, int node = 1, int s = 0, int e = sz-1){
    if(l > r) return;
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        addEdge(now, node); return;
    }
    int m = s + e >> 1;
    connect(now, l, r, node << 1, s, m);
    connect(now, l, r, node << 1 | 1, m+1, e);
}

int solve(int m){
    init();
    for(int i=1; i<(1 << 16); i++){
        addEdge(i, i << 1);
        addEdge(i, i << 1 | 1);
    }
    for(int i=0; i<n; i++){
        addEdge(id[i][0] | sz | inv, id[i][1] | sz);
        addEdge(id[i][1] | sz | inv, id[i][0] | sz);
    }
    for(int i=0; i<n; i++){
        int a = lower_bound(all(pt), p(x[i]-m+1, -1)) - pt.begin();
        int b = upper_bound(all(pt), p(x[i]+m, -1)) - pt.begin() - 1;
        connect(id[i][0] | sz, a | inv, id[i][0] - 1 | inv);
        connect(id[i][0] | sz, id[i][0] + 1 | inv, b | inv);
        a = lower_bound(all(pt), p(y[i]-m+1, -1)) - pt.begin();
        b = upper_bound(all(pt), p(y[i]+m, -1)) - pt.begin() - 1;
        connect(id[i][1] | sz, a | inv, id[i][1] - 1 | inv);
        connect(id[i][1] | sz, id[i][1] + 1 | inv, b | inv);
    }
    getSCC(1 << 17);
    for(int i=0; i<inv; i++) if(chk[i | sz] == chk[i | sz | inv]) return 0;
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> x[i] >> y[i];
        if(x[i] > y[i]) swap(x[i], y[i]);
        pt.push_back({x[i], i});
        pt.push_back({y[i], i+n});
    }
    sort(all(pt));
    for(int i=0; i<n; i++){
        id[i][0] = lower_bound(all(pt), p(x[i], i)) - pt.begin();
        id[i][1] = lower_bound(all(pt), p(y[i], i+n)) - pt.begin();
    }
    int l = 0, r = 1e9+7;
    while(l < r){
        int m = l + r + 1 >> 1;
        if(solve(m)) l = m;
        else r = m - 1;
    }
    cout << l;
}