A. Three Strings
Problem - A - Codeforces
codeforces.com
길이 n의 문자열 a,b,c가 주어진다.
a의 i번째 문자를 ai라고 하자. (bi,ci도 동일하게 정의)
i(1≤i≤n)에 대해, ci를 ai 또는 bi와 바꾼다.
모든 swap이 끝났을 때 a와 b가 같아질 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.
ci≠ai && ci≠bi를 만족하는 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
codeforces.com
배열 a는 n개의 non-negative integer로 구성된다.
ai가 −1이면 i번째 숫자가 사라졌음을 의미한다. (적어도 하나의 −1이 주어진다.)
배열 a에서 인접한 두 숫자의 차가 최소가 되도록 만들어야 한다.
1) 인접한 두 숫자가 모두 −1이 아닌 경우
d=max(d,abs(ai−ai−1))
2) 인접한 두 숫자가 모두 −1인 경우
계산할 필요 없음
3) 인접한 두 숫자 중 하나가 −1인 경우
−1이 아닌 숫자를 배열 b에 추가한다.
배열 b가 비어있을 경우, 답은 0이다.
배열 b가 비어있지 않을 경우, 답은 max(d,bmax−bmin+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
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
codeforces.com
간선을 최대 한 번씩만 사용하면서 k킬로미터를 이동할 수 있는지 묻는 문제이다.
k>4nm−2n−2m이면 이동이 불가능하다.
k≤4nm−2n−2m이면 아래 그림과 같은 방법으로 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*m - 2*n - 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<int, string> > 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
codeforces.com
F. Super Jaber
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 |