Processing math: 100%

Codeforces

Codeforces #619

yujaa 2021. 12. 23. 20:00

A. Three Strings

Problem - A - Codeforces

 

Problem - A - Codeforces

 

codeforces.com

길이 n의 문자열 a,b,c가 주어진다.

ai번째 문자를 ai라고 하자. (bi,ci도 동일하게 정의)

i(1in)에 대해, ciai 또는 bi와 바꾼다.

모든 swap이 끝났을 때 ab가 같아질 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

 

ciai && cibi를 만족하는 i가 존재하면 NO이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        string a, b, c;
        cin >> a >> b >> c;
 
        int len = a.size();
        bool flag = true;
        for (int i = 0; i < len; i++) {
            if (a[i] != c[i] && b[i] != c[i]) {
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES\n" : "NO\n");
    }
    return 0;
}
cs

 

 

B. Motarack's Birthday

Problem - B - Codeforces

 

Problem - B - Codeforces

 

codeforces.com

배열 an개의 non-negative integer로 구성된다.

ai1이면 i번째 숫자가 사라졌음을 의미한다. (적어도 하나의 1이 주어진다.)

배열 a에서 인접한 두 숫자의 차가 최소가 되도록 만들어야 한다.

 

1) 인접한 두 숫자가 모두 1이 아닌 경우
d=max(d,abs(aiai1))
2) 인접한 두 숫자가 모두 1인 경우
계산할 필요 없음
3) 인접한 두 숫자 중 하나가 1인 경우
1이 아닌 숫자를 배열 b에 추가한다.

배열 b가 비어있을 경우, 답은 0이다.

배열 b가 비어있지 않을 경우, 답은 max(d,bmaxbmin+12)이다.

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
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int diff = 0;
        vector<int> a;
        vector<int> v(n);
        cin >> v[0];
        for (int i = 1; i < n; i++) {
            cin >> v[i];
            if (v[i] != -1 && v[i-1!= -1) {
                diff = max(diff, abs(v[i] - v[i-1]));
            }
            else if (v[i] == -1 && v[i-1== -1) {
                continue;
            }
            else {
                a.push_back(v[i] ^ v[i-1] ^ (-1));
            }
        }
        if (a.empty()) {
            cout << 0 << ' ' << 0 << '\n';
        }
        else {
            int mx = *max_element(a.begin(), a.end());
            int mn = *min_element(a.begin(), a.end());
            int ans = max(diff, (mx - mn + 1/ 2);
            cout << ans << ' ' << (mx + mn) / 2 << '\n';
        }
    }
    return 0;
}
cs

 

 

C. Ayoub's function

Problem - C - Codeforces

 

Problem - C - Codeforces

 

codeforces.com

s가 binary string일 때, f(s)s의 substring 중 적어도 하나의 1을 포함하는 substring의 개수이다.

s의 길이와 s에 포함된 1의 개수가 주어졌을 때, f(s)의 최댓값을 구하는 문제이다.

 

s의 전체 substring 개수에서 0으로만 이루어진 substring들의 개수를 빼면 된다. (여사건)

참고: 길이 n인 문자열의 substring 개수 = n(n+1)2 (단, substring이 empty string인 경우 제외)

 

f(s) 최대가 되려면 0이 최대한 골고루 퍼져 있어야 한다.

0으로만 이루어진 구간의 최대 길이가 최소가 되어야 한다.

ex) 0이 5개, 1이 2개인 경우: 0010010

 

pf) n(n+1)2+m(m+1)2<(n+m)(n+m+1)2

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll f(ll k) {
    return k * (k + 1/ 2;
}
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        ll q = (n - m) / (m + 1);
        ll r = (n - m) % (m + 1);
        cout << f(n) - f(q+1* r - f(q) * (m + 1 - r) << '\n';
    }
    return 0;
}
cs

 

 

D. Time to Run

Problem - D - Codeforces

 

Problem - D - Codeforces

 

codeforces.com

간선을 최대 한 번씩만 사용하면서 k킬로미터를 이동할 수 있는지 묻는 문제이다.

k>4nm2n2m이면 이동이 불가능하다.

k4nm2n2m이면 아래 그림과 같은 방법으로 k킬로미터를 이동할 수 있다.

 

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
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int n, m, k, f;
    cin >> n >> m >> k;
 
    if (k > 4*n*- 2*- 2*m) {
        cout << "NO\n";
        return 0;
    }
    else {
        cout << "YES\n";
    }
    
    n--; m--;
    if (m == 0) {
        cout << (n >= k ? 1 : 2<< '\n';
        cout << min(n, k) << " D\n";
        k -= min(n, k);
        if (!k) return 0;
        cout << min(n, k) << " U\n";
        return 0;
    }
 
    vector<pair<intstring> > v;
    v.reserve(3002);
 
    // R -> L
    v.push_back({min(k, m), "R"});
    k -= min(k, m);
 
    if (!k) goto ed;
    v.push_back({min(k, m), "L"});
    k -= min(k, m);
 
    // D -> R -> UDL
    while (n-- && k) {
        if (!k) goto ed;
        v.push_back({1"D"});
        k--;
 
        if (!k) goto ed;
        v.push_back({min(k, m), "R"});
        k -= min(k, m);
 
        if (!k) goto ed;
        if (min(k/3, m)) {
            v.push_back({min(k/3, m), "UDL"});
            k -= min(k/3, m) * 3;
        }
        else {
            string s = "UDL";
            v.push_back({1, s.substr(0, k)});
            k = 0;
        }
    }
 
    // U
    if (!k) goto ed;
    v.push_back({k, "U"});
 
    ed:
    cout << v.size() << '\n';
    for (const auto& [num, path]: v) {
        cout << num << ' ' << path << '\n';
    }
    return 0;
}
cs

 

 

E. Nanosoft

Problem - E - Codeforces

 

Problem - E - Codeforces

 

codeforces.com

 

 

 

F. Super Jaber

Problem - F - Codeforces

 

Problem - F - Codeforces

 

codeforces.com

 

 

'Codeforces' 카테고리의 다른 글

Codeforces #763  (0) 2022.01.02
Codeforces Educational #120  (0) 2022.01.02
Codeforces Global #18  (0) 2021.12.26
Codeforces Educational #82  (0) 2021.12.26
Codeforces #728  (0) 2021.07.17