AtCoder ABC 185

작성일 | In

총평

노잼
E: 단순 DP
F: Do you know Segment Tree?

A. ABC Preparation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/******************************
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 main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << min({a, b, c, d});
}

B. Smartphone Addiction

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
/******************************
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 F, N, M, T, A[1010], B[1010];

void Check(){
    if(N <= 0){ cout << "No"; exit(0); }
}
void Update(int x){
    N = min(F, N+x);
    Check();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> T; F = N;
    for(int i=1; i<=M; i++) cin >> A[i] >> B[i];
    for(int i=1; i<=M; i++){
        Update(B[i-1] - A[i]);
        Update(B[i] - A[i]);
    }
    Update(B[M] - T);
    cout << "Yes";
}

C. Duodecim Ferra

nCr

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
/******************************
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;
ll D[222][222];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    D[0][0] = 1;
    for(int i=1; i<=N; i++) D[i][0] = 1;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=i; j++) D[i][j] = D[i-1][j] + D[i-1][j-1];
    }
    cout << D[N-1][11];
}

D. Stamp

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
/******************************
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;
vector<int> A;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M; A.resize(M);
    for(auto &i : A) cin >> i;
    A.push_back(0); A.push_back(N+1);
    sort(all(A));
    vector<int> V;
    for(int i=1; i<A.size(); i++) if(A[i]-A[i-1]-1 > 0) V.push_back(A[i] - A[i-1] - 1);
    if(V.empty()){ cout << 0; return 0; }
    sort(all(V));
    int K = V[0], sum = 0;
    for(auto i : V) sum += (i + K - 1) / K;
    cout << sum;
}

E. Sequence Matching

단순 DP 문제입니다.
$D(i, j)$: $A$의 $i$번째 글자까지, $B$의 $j$번째 글자까지 고려했을 때의 정답

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)
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;
int A[1010], B[1010];
int D[1010][1010];

int f(int i, int j){
    int &res = D[i][j];
    if(res != -1) return res;
    if(i == 0 || j == 0) return res = i + j;
    return res = min({f(i-1, j)+1, f(i, j-1)+1, f(i-1, j-1) + int(A[i] != B[j])});
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=M; i++) cin >> B[i];
    memset(D, -1, sizeof D);
    cout << f(N, M);
}

F. Range Xor Query

Do you know Segement Tree / Fenwick Tree?

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
/******************************
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, Q, T[303030];
void Update(int x, int v){
    for(x++; x<303030; x+=x&-x) T[x] ^= v;
}
int Query(int x){
    int ret = 0;
    for(x++; x; x-=x&-x) ret ^= T[x];
    return ret;
}
int Query(int l, int r){
    return Query(r) ^ Query(l-1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++){
        int t; cin >> t; Update(i, t);
    }
    for(int i=1; i<=Q; i++){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1) Update(a, b);
        else cout << Query(a, b) << "\n";
    }
}