AtCoder ABC 187

작성일 | In

총평

D: 간단한 그리디
E: 노잼
F: 좋은 Bit DP 기초 문제

A. Large Digits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/******************************
Author: jhnah917(Justice_Hui)
******************************/

#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 f(int x){
    return x/100 + x/10%10 + x%10;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int a, b; cin >> a >> b;
    cout << max(f(a), f(b));
}

B. Gentle Pairs

기울기를 실수로 관리하는 이상한 행동은 지양합시다.

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
/******************************
Author: jhnah917(Justice_Hui)
******************************/

#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, X[1010], Y[1010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    int cnt = 0;
    for(int i=1; i<=N; i++) cin >> X[i] >> Y[i];
    for(int i=1; i<N; i++){
        for(int j=i+1; j<=N; j++){
            int dx = X[i] - X[j], dy = Y[i] - Y[j];
            if(abs(dx) >= abs(dy)) cnt++;
        }
    }
    cout << cnt;
}

C. 1-SAT

std::map 연습

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
/******************************
Author: jhnah917(Justice_Hui)
******************************/

#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;
map<string, int> mp;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=0; i<N; i++){
        int flag = 1; string s;
        cin >> s;
        if(s[0] == '!') flag = -1, s = s.substr(1);
        if(mp[s] == -flag){ cout << s; return 0; }
        mp[s] = flag;
    }
    cout << "satisfiable";
}

D. Choose Me

각 선거구마다 유세를 할 때 얻는 지지자와 하지 않을 때 빼앗길 지지자를 구합시다.
(유세를 할 때 얻는 지지자) + (하지 않을 때 빼앗길 지지자)가 큰 선거구부터 유세를 하는 것이 최적임을 알 수 있습니다.

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
/******************************
Author: jhnah917(Justice_Hui)
******************************/

#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;
typedef pair<ll, ll> p;

int N;
vector<p> V;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        int a, b; cin >> a >> b;
        V.emplace_back(a+b, -a);
    }
    sort(all(V), [](const p &a, const p &b){ return a.x-a.y > b.x-b.y; });
    ll A = 0, B = 0;
    for(const auto &i : V) A -= i.y;
    for(int i=0; i<N; i++){
        if(A < B){ cout << i; return 0; }
        B += V[i].x; A += V[i].y;
    }
    cout << N;
}

E. Through Path

Euler Tour Trick 연습 문제
서브 트리 갱신은 Segment Tree + Lazy Propagation을 사용해도 되고, 단순히 루트에 기록해둔 다음 DFS를 하면서 정답을 구해도 됩니다.

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
/******************************
Author: jhnah917(Justice_Hui)
******************************/

#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;
const int S = 1 << 18;

int N, Q, A[202020], B[202020], I[202020], O[202020], C;
vector<int> G[202020];
ll T[1 << 19], L[1 << 19];

void Push(int node, int s, int e){
    T[node] += L[node] * (e-s+1);
    if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
    L[node] = 0;
}

void Update(int l, int r, ll x, int node=1, int s=1, int e=N){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        L[node] += x; Push(node, s, e);
        return;
    }
    int m = s + e >> 1;
    Update(l, r, x, node<<1, s, m);
    Update(l, r, x, node<<1|1, m+1, e);
    T[node] = T[node<<1] + T[node<<1|1];
}

ll Query(int l, int r, int node=1, int s=1, int e=N){
    Push(node, s, e);
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return T[node];
    int m = s + e >> 1;
    return Query(l, r, node<<1, s, m) + Query(l, r, node<<1|1, m+1, e);
}

void DFS(int v, int b = -1){
    I[v] = ++C;
    for(auto i : G[v]) if(i != b) DFS(i, v);
    O[v] = C;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<N; i++){
        cin >> A[i] >> B[i];
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    DFS(1);
    cin >> Q;
    for(int i=1; i<=Q; i++){
        int t, e, x; cin >> t >> e >> x;
        int a, b;
        if(t == 1) a = B[e], b = A[e];
        else a = A[e], b = B[e];
        if(I[a] <= I[b] && I[b] <= O[a]) Update(I[b], O[b], x);
        else Update(1, N, x), Update(I[a], O[a], -x);
    }
    for(int i=1; i<=N; i++) cout << Query(I[i], I[i]) << "\n";
}

F. Close Group

bit가 Clique인지 여부를 저장하는 배열 Check[bit]를 전처리합시다. $O(N^2 \cdot 2^N)$에 모두 구할 수 있습니다.
이후, D[bit]를 정점을 bit처럼 선택했을 때의 정답으로 정의해서 Bit DP를 합시다. 시간 복잡도는 $O(\sum i \cdot {N \choose i})$로 계산할 수 있고, 이항 정리에 의해 $O(3^N)$입니다.
$O(N^2 \cdot 2^N + 3^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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -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())
using namespace std;

typedef long long ll;

int N, M, D[1<<18];
bool G[18][18], Check[1<<18];

bool Clique(const vector<int> &arr){
    for(auto i : arr) for(auto j : arr) if(i != j && !G[i][j]) return false;
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++){
        int s, e; cin >> s >> e; s--; e--;
        G[s][e] = G[e][s] = true;
    }
    for(int bit=1; bit<(1<<18); bit++){
        vector<int> v;
        for(int i=0; i<N; i++) if(bit & (1 << i)) v.push_back(i);
        Check[bit] = Clique(v);
    }
    memset(D, 0x3f, sizeof D);
    D[0] = 0;
    for(int bit=1; bit<(1<<N); bit++){
        if(Check[bit]) D[bit] = 1;
        for(int i=bit; i; i=(i-1)&bit) D[bit] = min(D[bit], D[i] + D[bit^i]);
    }
    cout << D[(1<<N)-1];
}