https://codeforces.com/contest/1328/problems
Problems - Codeforces
codeforces.com
A. Divisibility Problem
a와 b를 입력받는다.
a를 a++원하는 만큼 하여 a를 b로 나눠 떨어지게 하고 싶어하고 이때 ++횟수를 최소화 하고 싶어한다.
b - a%b를 하면되는데 a%b==0 일경우 b번더하게 됨으로 예외를 준다.
|
1
2
3
4
5
6
7
8
9
10
|
int T;
cin >> T;
while (T--) {
int a, b;
cin >> a >> b;
if (0 == a % b)
cout << 0<<'\n';
else
cout << b - a % b << '\n';
}
|
B. K-th Beautiful String
n-2개의 a와 2개의 b가 주어질때 n 과 k를 입력받아 k번째 문자열을 출력하는 문제 n 이 10^5이기 때무네 이분탐색으로 좁혀가 수학적으로 찾아준다 (1+2+3+....+n = n(n+1)/2)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int T;
cin >> T;
while (T--) {
ll a, b;
cin >> a >> b;
ll l = 1;
ll r = a;
while (l <= r) {
ll mid = (l + r) / 2;
if (b <= mid * (mid - 1) / 2)
r = mid - 1;
else
l = mid + 1;
}
for (int i = a; i > 0; i--) {
if (i == l || i == b - (l - 2) * (l - 1) / 2)
cout << 'b';
else
cout << 'a';
}
cout << '\n';
}
|
C. Ternary XOR
3진수를 입력받아 2개로 2 개로 쪼갤건데 그 값의 차이가 최소가 되게 나눠야한다.
2값이라면 동등하게 1씩나누면 되고 0이라면 둘다 0을하면되지만 1이라면 하나의 값에 1을 줘야하고 하나엔 0을 줘야한다.
이후에는 모든 값들을 위에서 1대신 0을 준 값에게 몰아주면 된다.
string 을 사용하는게 더 편하다.
|
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
|
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
string s,b,c;
cin >> s;
int che = 0;
for (int i = 0; i < n; i++) {
if (che == 0) {
if (s[i]-'0' == 1)
{
b += '1';
c += '0';
che = 1;
}
else if (s[i] - '0' == 2) {
b += '1';
c += '1';
}
else if (s[i] - '0' == 0) {
b += '0';
c += '0';
}
}
else {
b += '0';
c += s[i];
}
}
cout << b << '\n' << c << '\n';
}
|
D. Carousel
영어를 못해서 해석을 하는데 좀 애 먹었다. 이문제 공지만 2개 올라온거 보면 나 뿐만 아니라 다른 외국인들도 힘들었나 보다.
문제를 간단히 하면 "나와 붙어있는 다른 동물과는 다른 색을 가져야 한다." 이다.
문제를 원형이 아닌 선형으로 생각하면 매우 쉬워진다. 1개 혹은 2개의 색으로 모든 경우를 만족 할 수 있다.
동물의 종류가 바뀔때 마다 1<-> 2 를 해주면된다.
하지만 원형일 경우 처음것과 마지막것의 접촉도 고려해줘야 하고 그 둘이 다른 동물이고 같은 색이라면(36줄)
마지막 동물을 3으로 칠해주면된다. (같은동물이 접촉해 있는데 다른핵으로 칠하는 것은 상관 없음)
하지만 해당 경우 일때 항상 3을 칠해야 하는 것은 아니다. 해당 색을 2로 칠 할수 있다면 처음것과 다른색을 칠할수 있으므로 만족 할수 있게 된다. 이러한 조건은 같은 색이 연속으로 등장하는 구간이 있는지 확인하고 이러한 구간이 있었다면 해당 칸을 1이면 2로 2면 1로 칠한 후 그칸부터 다시 색을 칠하면 마지막칸의 색은 뒤바뀌게 된다. (중복칸부터 마지막 칸까지 색을 전부 뒤집음)
|
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
|
int arr[MAXN];
int brr[MAXN];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int tem = 1;
brr[0] = 1;
int che2 = 0;
int same = 0;
for (int i = 1; i < n; i++) {
if (arr[i - 1] != arr[i]) {
che2 = 1;
if (tem == 1)
tem = 2;
else if (tem == 2)
tem = 1;
}
else
same = i;
brr[i] = tem;
}
int che;
if (che2)
che = 2;
else
che = 1;
if (brr[n - 1] == 1 && arr[n - 1] != arr[0]) {
if (same) {
if (brr[same] == 1)
tem = 2;
else
tem = 1;
for (int i = same; i < n; i++) {
if (arr[i - 1] != arr[i]) {
che2 = 1;
if (tem == 1)
tem = 2;
else if (tem == 2)
tem = 1;
}
brr[i] = tem;
}
}
else {
che = 3;
brr[n - 1] = 3;
}
}
cout << che << '\n';
for (int i = 0; i < n; i++)
cout << brr[i] << ' ';
cout << '\n';
}
}
|
E. Tree Queries
div 3라 그런지 E인데도 1000명가까이 풀었다.
서버가 터져서 제출은 못했는데 아마 맞을거 같다.
경로를 선택해서 입력받은 노드들이 경로로 부터 한칸 거리 이내 있으면 되는 문제이다.
트리의 특성을 생각하면 노드들의 부모가 경로에 속하면 만족하는 것이다. 그리고 그 경로는 1에서 가장 깊은 노드의 부모이다.
가장 깊은 숫자를 찾고 각 노드들의 부모와 가장 깊은 노드의 부모를 비교한다. LCA까지는 사용하지 않고 가장 깊은 노드의 부모를 비교하고자 하는 노드의 부모 dep까지 올렸을때 비교하고자 하는 노드의 부모라면 같은 경로이고 아니면 경로 밖에 있는 것이다.
올라오는 방법을 log로 하지 않고 (par[20][MAXN])한칸씩 올라갈 경우 시간초과가 난다.
|
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
|
vector<int> adj[MAXN];
int dep[MAXN];
int par[20][MAXN];
void dfs(int node, int pre, int d) {
dep[node] = d;
par[0][node] = pre;
for (int there : adj[node]) {
if (there == pre)
continue;
dfs(there, node, d + 1);
}
}
int LCA(int a, int b) {
for (int i = 19; i >= 0; i--) {//같은 dep으로 올리기 b가 제일 깊음
if (dep[b] - dep[a]>=1<<i) {
b = par[i][b];
}
}
return b;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 1, 1);
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
while (k--) {
vector<int> v;
int m;
cin >> m;
int depnum=0;
int depg=0;
int che = 0;
for (int i = 0; i < m; i++) {//가장 깊은 숫자 찾기
int tem;
cin >> tem;
tem = par[0][tem];
v.push_back(tem);
if (dep[tem] >= depg) {
depg = dep[tem];
depnum = tem;
}
}
for (int i = 0; i < m; i++) {//가장 깊은 숫자와 LCA
if (LCA(v[i], depnum) != v[i])
che = 1;
}
if (che)
cout << "NO\n";
else
cout << "YES\n";
}
}
|
'알고리즘 > 대회' 카테고리의 다른 글
| Codeforces Round #633 (Div. 2) 코드포스 #633 (0) | 2020.04.13 |
|---|---|
| Codeforces Round #632 (Div. 2) 코드포스 후기 (0) | 2020.04.10 |
| Codeforces Round #631 (Div. 2) 다시 돌아온 블루 (0) | 2020.04.05 |
| Codeforces Round #630 (Div. 2) 민트의 왕이라네~ (0) | 2020.04.01 |
| Educational Codeforces Round 84 (Rated for Div. 2) (0) | 2020.03.25 |