A - Maximum GCD
Problem - A - Codeforces
codeforces.com
정수 \(n\)이 주어진다.
\(1\)이상 \(n\)이하인 서로 다른 정수 2개를 골랐을 때, \(\gcd (a,b)\)의 최대값을 구해야 한다.
당연하지만, \(\gcd (\lfloor \frac n2 \rfloor, \lfloor \frac n2 \rfloor \times 2) = \lfloor \frac n2 \rfloor\)가 답이다.
|
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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
cout << n / 2 << '\n';
}
}
|
B - GCD Compression
Problem - B - Codeforces
codeforces.com
\(2n\)개의 원소를 가진 배열 \(a\)가 있다.
이 배열에서 \(n-1\)쌍의 수들을 골라 각 쌍의 합의 최대공약수가 1보다 크도록 하려고 한다.
쌍을 이루는 인덱스들을 출력해야 한다.
최대공약수가 무조건 2가 되도록 할 수 있음을 알 수 있다.
\(a\)에 포함된 짝수의 수와 홀수의 수가 각각 짝수개일 경우, 짝수 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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
vector <int> a[2];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
a[0].clear(), a[1].clear();
cin >> n;
for (int i = 1; i <= n * 2; i++)
{
int x; cin >> x;
a[x % 2].push_back(i);
}
int cnt = 0;
for (int k = 0; k < 2; k++)
{
for (int i = 0; i < a[k].size() / 2 && cnt < n - 1; i++)
{
cout << a[k][i * 2] << ' ' << a[k][i * 2 + 1] << '\n';
cnt++;
}
}
}
}
|
C - Number Game
Problem - C - Codeforces
codeforces.com
두 사람이 게임을 한다.
수 \(n\)에서 시작해서, 본인 차례에 다음과 같은 행동을 할 수 있다.
1. \(n\)이 1보다 크다면, \(n\)의 홀수인 약수로 나눈다.
2. \(n\)이 1보다 크다면, 1을 뺀다.
본인 차례에 할 수 있는 행동이 없는 사람이 패배한다.
\(n\)이 주어지고 두 사람이 이상적으로 행동할 때, 누가 이길지 알아내야 한다.
다음과 같이 케이스를 나눌 수 있다. (if - else)
1. \(n=1\)이면 후공이 이긴다.
2. \(n=2\)이면 선공이 이긴다.
3. \(n\)이 홀수면 선공이 이긴다. (\(n\)으로 나누면 된다.)
4. \(n\)이 \(2^k\)꼴이라면, 후공이 이긴다. (1을 뺄 수 밖에 없다)
5. \(n\)이 \(2 \times \text{소수} \) 꼴이라면 후공이 이긴다.
6. \(n\)이 \(2 \times \text{합성수} \) 꼴이라면 선공이 이긴다. (4번 또는 5번 꼴로 만들 수 있다)
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const string WIN = "Ashishgup";
const string LOSE = "FastestFinger";
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll n; cin >> n;
if (n == 1) cout << LOSE << '\n';
else if (n == 2) cout << WIN << '\n';
else if (n % 2 == 1) cout << WIN << '\n';
else
{
n /= 2;
if (n % 2 == 1)
{
bool flag = true;
for (ll i = 2; i*i <= n; i++)
{
if (n % i == 0) flag = false;
}
if (flag) cout << LOSE << '\n';
else cout << WIN << '\n';
}
else
{
while (n % 2 == 0) n /= 2;
if (n == 1) cout << LOSE << '\n';
else cout << WIN << '\n';
}
}
}
}
|
D - Odd-Even Subsequence
Problem - D - Codeforces
codeforces.com
\(n\)크기의 배열 \(a\)가 주어진다.
\(a\)의 크기가 \(k\)인 부분 수열 \(s\)에 대해,
\(s\)의 홀수 인덱스 원소의 최대값과 짝수 인덱스 원소의 최대값중 작은 값이 최소가 되도록 하려고 한다.
이 때 그 값을 알아내야 한다.
홀수 인덱스 원소의 최대값을 어떤 수 \(x\)보다 작거나 같게 만든다고 해보자.
그러면 \(a\)를 앞에서부터 훑어가면서, 다음과 같이 \(s\)를 만들어 나갈 수 있다.
1. 현재 \(s\)에 홀수 인덱스를 넣을 차례이고, \(a_i\)가 \(x\)보다 작거나 같다면 \(s\)에 추가한다.
2. 현재 \(s\)에 짝수 인덱스를 넣을 차례라면, \(a_i\)의 값에 상관없이 \(s\)에 추가한다.
이 규칙으로 \(s\)를 만들었을 때 길이가 \(k\)보다 크거나 같으면 된다.
따라서 홀수 인덱스와 짝수 인덱스 각각에 대해서, \(x\)의 최소값을 이분탐색으로 찾을 수 있다.
그 중 최소값을 취하면 된다.
|
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
72
73
74
75
76
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll n, k;
ll a[200001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
ll ans = 2e9;
ll l = 0, r = 1e9;
int sz = 0;
while (l + 1 < r)
{
sz = 0;
ll m = (l + r) / 2;
for (int i = 1; i <= n; i++)
{
if (sz % 2 == 0)
{
if (a[i] <= m) sz++;
}
else
{
sz++;
}
}
if (sz >= k) r = m;
else l = m;
}
ans = min(ans, r);
l = 0, r = 1e9;
sz = 0;
while (l + 1 < r)
{
sz = 0;
ll m = (l + r) / 2;
for (int i = 1; i <= n; i++)
{
if (sz % 2 == 1)
{
if (a[i] <= m) sz++;
}
else
{
sz++;
}
}
if (sz >= k) r = m;
else l = m;
}
ans = min(ans, r);
cout << ans;
}
|
E - Binary Subsequence Rotation
Problem - E - Codeforces
codeforces.com
이진 문자열 \(s, t\)가 주어진다.
\(s\)의 부분 수열을 골라 시계방향으로 회전시키는 연산을 할 수 있을 때,
\(s\)를 \(t\)와 같도록 만들 수 있는지 여부를 확인하고, 가능하다면 최소 연산 횟수를 알아내야 한다.
각 인덱스에 대해, \(s_i = t_i\)면 건드릴 필요가 없다.
\(s_i \ne t_i\)인 인덱스에 대해, \(s\)에서의 값이 010101... 또는 101010... 형태가 되도록 최대한 많이 골라 시계방향으로 회전시키면 항상 최적임을 알 수 있다.
set등으로 구현후 시뮬레이션하면 된다.
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
string s, t;
set <int> st1, st2;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
cin >> s >> t;
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '1') cnt0++;
if (t[i] == '1') cnt1++;
if (s[i] != t[i])
{
if (s[i] == '0') st1.insert(i);
else st2.insert(i);
}
}
if (cnt0 != cnt1)
{
cout << -1;
return 0;
}
int ans = 0;
while (st1.size())
{
ans++;
if (*st1.begin() < *st2.begin())
{
auto idx = st1.begin();
while (idx != st1.end())
{
int t1 = *idx;
idx = st2.upper_bound(t1);
if (idx == st2.end()) break;
int t2 = *idx;
idx = st1.upper_bound(t2);
st1.erase(t1);
st2.erase(t2);
}
}
else
{
auto idx = st2.begin();
while (idx != st2.end())
{
int t2 = *idx;
idx = st1.upper_bound(t2);
if (idx == st1.end()) break;
int t1 = *idx;
idx = st2.upper_bound(t1);
st1.erase(t1);
st2.erase(t2);
}
}
}
cout << ans;
}
|
F - The Hidden Pair (Hard Version)
Problem - F2 - Codeforces
codeforces.com
\(n\)개의 노드를 가진 트리가 주어진다.
이 트리에서 프로그램이 정한 임의의 2개의 노드 \(s,f\)가 무엇인지 알아내야 한다.
쿼리를 최대 11번 사용할 수 있다.
각 쿼리마다 노드의 집합을 입력으로 주면, 그 중 \(s\)까지의 거리와 \(f\)까지의 거리의 합이 최소인 노드 중 하나와, 그 거리의 합을 출력해준다.
우선 모든 노드에 대해 위 쿼리를 한번 사용하자.
그러면 \(s\)에서 \(f\)사이 경로에 해당되는 점 중 하나 \(v\)와, 거리의 합의 최소값 \(d\)를 얻을 수 있다.
\(v\)에서 시작해 각 노드까지의 거리를 저장하면, \(s\)와 \(f\)중 \(v\)에서 먼 점 까지의 거리와 그 정점을 이분탐색으로 알 수 있다.
(최대 10쿼리 사용)
한 정점을 알았으니, 이 정점에서 \(d\) 떨어진 모든 정점에 대해 쿼리를 날리면 나머지 하나의 정점을 알 수 있다.
문제는 지금까지 최대 12쿼리를 사용하기 때문에, 쿼리 하나를 줄여야 한다는 것이다. (Easy는 이 방법으로 풀 수 있다)
\(v\)에서 \(s, f\)까지의 거리를 생각해 보자.
한 정점까지의 거리는 무조건 \(\lfloor \frac d2 \rfloor\)이하, 나머지 한 정점까지의 거리는 \(\lceil \frac d2 \rceil\)이상이다.
따라서 이분 탐색을 할 때 둘 중 하나의 정점만 찾는다면 범위를 절반으로 줄일 수 있고, 쿼리 하나를 아낄 수 있다.
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
vector <int> graph[1001];
int dist[1001];
int sz[1001];
int DFS(int v, int p, int d)
{
dist[v] = d;
sz[v] = 1;
for (int nv : graph[v])
{
if (nv == p) continue;
sz[v] += DFS(nv, v, d + 1);
}
return sz[v];
}
int isIn[1001];
void DFS2(int v, int p)
{
isIn[v] = 1;
for (int nv : graph[v])
{
if (nv == p) continue;
DFS2(nv, v);
}
}
vector <int> di[1001];
int qry[1001];
int main()
{
int t; cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; i++) graph[i].clear();
for (int i = 0; i < n - 1; i++)
{
int u, v; cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
cout << "? " << n;
for (int i = 1; i <= n; i++) cout << ' ' << i;
cout << endl;
int x, d; cin >> x >> d;
int minD = d;
DFS(x, 0, 0);
int subTree = -1;
int mx_sz = 0;
for (auto nv : graph[x])
{
if (sz[nv] > mx_sz)
{
mx_sz = sz[nv];
subTree = nv;
}
}
memset(isIn, 0, sizeof isIn);
DFS2(subTree, x);
int mx = 0;
for (int i = 0; i <= 1000; i++) di[i].clear();
for (int i = 1; i <= n; i++)
{
if (isIn[i]) continue;
di[dist[i]].push_back(i);
mx = max(mx, dist[i]);
}
memset(qry, -1, sizeof qry);
int l = 0, r = min(mx, d) + 1;
while (l + 1 < r)
{
int m = (l + r) / 2;
cout << "? " << di[m].size();
for (int v : di[m]) cout << ' ' << v;
cout << endl;
cin >> x >> d;
qry[m] = x;
if (d == minD)
{
l = m;
}
else
{
r = m;
}
}
if (qry[l] == -1)
{
cout << "? " << di[l].size();
for (int v : di[l]) cout << ' ' << v;
cout << endl;
cin >> x >> d;
qry[l] = x;
}
x = qry[l];
DFS(x, 0, 0);
vector <int> tmp;
for (int i = 1; i <= n; i++)
{
if (dist[i] == minD) tmp.push_back(i);
}
cout << "? " << tmp.size();
for (int v : tmp) cout << ' ' << v;
cout << endl;
int lx, ld; cin >> lx >> ld;
cout << "! " << x << ' ' << lx << endl;
string res; cin >> res;
if (res != "Correct") return 0;
}
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #654 (Div. 2) (0) | 2020.07.03 |
|---|---|
| Codeforces Round #652 (Div. 2) (0) | 2020.06.24 |
| Codeforces Global Round 8 (3) | 2020.06.19 |
| Codeforces Round #650 (Div. 3) (0) | 2020.06.17 |
| Codeforces Round #648 (Div. 2) (0) | 2020.06.08 |
