A - Phoenix and Balance
무게가 \(2^1, 2^2, \dots, 2^n\)인 동전 \(n\)개가 있다. \(n\)은 짝수이다.
이 동전을 \(\frac n2\)개 씩 두 묶음으로 나눠서 두 묶음의 동전의 무게의 차가 최소가 되도록 해야 한다.
무게가 \(2^n\)인 동전 하나가 나머지 동전의 무게를 다 합친 것보다 무게가 많이 나간다.
따라서 \(2^n\)동전 하나와 가장 무게가 가벼운 동전 \(\frac n2 - 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
|
#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;
ll a = 0, b = 0;
for (int i = 0; i < n / 2 - 1; i++)
{
a += (1 << (i + 1));
b += (1 << (n / 2 + i));
}
a += (1 << n);
b += (1 << (n - 1));
cout << a - b << '\n';
}
}
|
B - Phoenix and Beauty
길이 \(n\)인 수열 \(b\)가 주어진다.
이 수열에 최대 \(10^4\)개의 수를 추가해서 만든 새로운 수열 \(a\)의 주기가 \(k\)가 되려고 한다.
이 조건을 만족하는 수열을 만드는 것이 가능한지 알아내야 한다.
가능하다면, 가능한 \(a\)를 아무거나 출력해야 한다.
먼저, \(b\)에 포함된 서로 다른 수의 개수가 \(k\)개보다 많으면 \(a\)를 만드는 것이 불가능하다는 것을 알 수 있다.
만드는 것이 가능하다면, \(b\)에 포함된 수를 적어도 하나씩 포함한 \(k\)길이의 수열을 적당히 하나 만든다.
이 수열을 \(n\)회 반복한 수열은 무조건 답이 된다.
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
|
#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 k, n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n >> k;
set <int> s;
for (int i = 0; i < n; i++)
{
int x; cin >> x;
s.insert(x);
}
if (s.size() > k)
{
cout << "-1\n";
continue;
}
cout << n * k << '\n';
for (int i = 0; i < n; i++)
{
for (auto x : s) cout << x << ' ';
for (int j = 0; j < k - s.size(); j++) cout << *s.begin() << ' ';
}
cout << '\n';
}
}
|
C - Phoenix and Distribution
\(n\)길이의 문자열 \(s\)가 주어진다.
\(s\)에 있는 모든 문자들을 \(k\)개의 문자열 \(a_1,a_2,\dots,a_k\)에 나눠서 배분하려고 한다.
이때 나눠진 문자열의 길이는 최소 \(1\)이어야 하고, 사전순으로 가장 큰 문자열을 사전순으로 가장 작게 만들어야 한다.
위 조건을 맞춰 \(k\)개의 문자열을 만들었을 때, 사전순으로 가장 큰 문자열을 출력해야 한다.
우선 문자열이 최소 \(1\)의 길이를 가져야 하므로, \(s\)에 있는 문자열 중 사전순으로 가장 작은 문자를 하나씩 배정하자.
여기까지 했을 때 \(k\)개의 문자열의 맨 앞글자가 모두 같지 않다면, 나머지 문자를 가장 작은 문자를 맨 앞글자로 가지는 문자열 뒤에 적당히 배정하면 된다.
ex) \(s = \) "aabcd", \(k = 3\)라면,
3개의 문자열은 각각
"a"
"acd" // c, d를 a뒤에 적당히 배정한다.
"b"
가 되고, 사전순으로 가장 큰 문자열은 "b"가 된다.
그렇지 않다면, 1글자씩 배정한 다음 남은 글자가 몇 종류 남았는지 확인해보자.
만약 남은 글자가 1종류라면, 최대한 고르게 나눠주면 된다.
ex) \(s = \) "aaabb", \(k = 3\)라면,
3개의 문자열은 각각
"a"
"ab"
"ab"
가 되고, 사전순으로 가장 큰 문자열은 "ab"가 된다.
남은 글자가 1종류보다 많다면, 남은 문자들을 사전순으로 죄다 한곳에 몰아주면 된다.
ex) \(s = \) "aaaabc", \(k = 3\)라면,
3개의 문자열은 각각
"aabc" // 남은 문자를 한곳에 다 몰아준다.
"a"
"a"
가 되고, 사전순으로 가장 큰 문자열은 "aabc"가 된다.
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
|
#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 k, n;
string s;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n >> k;
cin >> s;
map <char, int> mp;
for (auto c : s) mp[c]++;
int res = 0;
set <char> st;
for (auto it = mp.begin(); it != mp.end();)
{
char c = it->first;
int v = it->second;
st.insert(c);
for (int i = 0; i < v; i++)
{
mp[c]--;
if (++res == k) break;
}
it++;
if (mp[c] == 0) mp.erase(c);
if (res == k) break;
}
if (st.size() > 1)
{
cout << *prev(st.end()) << '\n';
continue;
}
if (mp.size() <= 1)
{
cout << *st.begin();
for (auto it : mp)
{
char c = it.first;
int v = it.second;
for (int i = 0; i < (v - 1) / k + 1; i++) cout << c;
}
cout << '\n';
continue;
}
cout << *st.begin();
for (auto it : mp)
{
char c = it.first;
int v = it.second;
for (int i = 0; i < v; i++) cout << c;
}
cout << '\n';
}
}
|
D - Phoenix and Science
질량이 \(1\)인 박테리아 \(1\)개가 있다.
매일 낮에 각각의 박테리아들은 분열하거나, 분열하지 않는다..
분열한다면 각각의 질량은 원래의 질량의 절반이 된다.
매일 밤에는 각 박테리아들의 질량이 1씩 늘어난다.
어떤 수 \(n\)이 주어졌을 때, 박테리아가 위의 규칙에 의해 총 질량이 \(n\)이 될 수 있는지 알아내야 한다.
가능하다면, 질량이 \(n\)이 되기 위해 필요한 최소 밤의 수를 출력하고, 각 밤마다 몇개씩의 박테리아가 분열하는지 출력해야 한다.
먼저, 박테리아가 계속 분열하지 않는다면 질량이 항상 \(1\)씩 증가하므로, 불가능한 경우는 없다는 것을 알 수 있다.
어떤 날 밤에 박테리아의 수가 \(x\)개이고, 박테리아의 총 질량이 \(m\)이라고 하자.
밤이 지나고 나면 박테리아의 총 질량은 \(m+x\)가 되는데,
따라서 어떤 날에 박테리아의 총 질량은 지금까지 낮에 존재했던 박테리아의 개수의 합임을 알 수 있다.
또, 어떤 날 낮에 박테리아의 수가 \(x\)개라면, 분열하고 나서 박테리아의 수는 최소 \(x\), 최대 \(2x\)가 되는데,
밤의 수를 최소화 해야 하므로, 일단 박테리아가 최대한 많은 분열을 한다고 생각해 보자.
박테리아의 수는 다음과 같이 된다.
\(a = \{1, 2, 4, 8, \dots \}\)
이 수들의 합 \(s\)가 \(n\)보다 커지지 않도록 최대한 많은 분열을 하자.
여기에서 총 질량이 \(n-s\) 늘어나기 위해서는, 낮에 박테리아의 수가 \(n-s\)개인 날이 하루 더 존재해야 함을 알 수 있다.
\(n-s\)를 \(a\)가 정렬된 상태를 유지하도록 \(a\) 중간에 적당히 넣어주자.
ex) \(n = 20\)이라면,
\(a = \{1, 2, 4, 5, 8\}\)이 된다.
그 후에 \(2 \le i \le len(a)\)에 대하여, \(a_i - a_{i-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
|
#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--)
{
ll n; cin >> n;
ll tmp = 1;
ll sum = 1;
multiset <ll> res;
res.insert(tmp);
while (true)
{
tmp *= 2;
if (sum + tmp > n) break;
sum += tmp;
res.insert(tmp);
}
ll rm = n - sum;
if (rm) res.insert(rm);
ll prev = -1;
vector <ll> ans;
for (ll it : res)
{
if (prev == -1)
{
prev = it;
continue;
}
ans.push_back(it - prev);
prev = it;
}
cout << ans.size() << '\n';
for (auto it : ans) cout << it << ' ';
cout << '\n';
}
}
|
E - Phoenix and Berries
\(n\)개의 관목이 있다. 각각의 관목은 \(a_i\)개의 빨간 열매와 \(b_i\)개의 파란 열매를 가지고 있다.
이 열매들을 바구니에 담으려고 한다. 각 바구니에는 정확히 \(k\)개의 열매를 담아야 하는데,
같은 바구니에 있는 열매들은 모두 같은 관목에서 나왔거나 모두 같은 색깔이어야 한다.
이 때 가득 채울 수 있는 바구니의 최대값을 구해야 한다.
DP식을 다음과 같이 정의하자.
\(DP(i, j) = \) \(1\)번부터 \(i\)번 관목까지 이용했을 때, 빨간 열매를 정확히 \(j\)개 남길 수 있는지 여부 (bool)
(\(j\)개를 제외한 빨간 열매는 모두 바구니에 꽉 찬 상태로 들어가야 한다.)
\(j\)가 \(k\)이상이라면 \(k\)개의 빨간 열매를 이용해 바구니 하나를 채울 수 있기 때문에,
\(0 \le j \le k-1\)이다.
그러면 현재 \(i\)번째 관목을 보고 있고 빨간 열매를 \(x\)개 더 남길 수 있다고 했을 때,
\(DP(i, j)\)는 가능한 모든 \(x\)에 대해 \(DP(i, (j+k-x) \bmod k)\)를 OR한 값이 된다.
그러면 DP테이블의 크기가 \(nk\)이고, 각 상황을 계산하는데 \(k\)번의 연산이 필요하기 때문에
\(O(nk^2)\)의 시간복잡도로 해결할 수 있게 된다.
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
|
#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[501], b[501];
bool dp[501][501];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
ll sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i] >> b[i];
sum += a[i] + b[i];
}
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < k; j++)
{
for (int x = 0; x <= min(k - 1, a[i]); x++)
{
if ((a[i] - x) % k == 0 || (a[i] - x) % k + b[i] >= k)
{
dp[i][j] |= dp[i - 1][(j + k - x) % k];
}
}
}
}
ll ans = 0;
for (int x = 0; x < k; x++)
{
if (dp[n][x])
{
ll res = (sum - x) / k;
ans = max(ans, res);
}
}
cout << ans;
}
|
F - Phoenix and Memory
\(n\)개의 수로 이루어진 순열이 있다.
수열 내에서 각각의 수의 인덱스가 \(a_i\)이상 \(b_i\)이하라고 할때,
모든 수가 위의 조건을 만족하는 수열이 유일한지 알아내야 한다.
유일하다면 그 수열을 출력하고,
그렇지 않다면 가능한 수열 2가지를 출력해야 한다.
먼저 가능한 수열을 한 가지 만들어야 하는데,
각각의 인덱스 \(i\)에 대해서, \(a_i\)가 \(1\)이상 \(i\)이하이면서 아직 사용하지 않은 수들 중에
\(b_i\)가 가장 작은 수를 사용하는 그리디한 방식으로 만들어 낼 수 있다.
위의 방식으로 수열을 만든 다음, 어떤 두 인덱스 \(i, j\)에 대해, \((i \lt j)\)
\(b_i \ge j\) 이고, \(a_i \le i\)인 \((i, j)\)가 존재한다면 두 위치에 있는 수를 서로 바꿔도 위의 조건을 모두 만족함을 알 수 있다.
각 인덱스에 대해 \(b_i\)를 저장하는 최댓값 세그먼트 트리를 이용하면 쉽게 구할 수 있다.
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
|
#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;
struct pos
{
int l;
int r;
int idx;
bool operator<(const pos p) const
{
if (r != p.r) return r < p.r;
else if (l != p.l) return l < p.l;
return idx < p.idx;
}
};
bool comp(pos p1, pos p2)
{
return p1.l < p2.l;
}
const int N = 200001;
pos p[N], tmp[N];
set <pos> st;
int ans1[N], ans2[N];
int ans_idx[N];
pii segTree[N * 4]; // max, idx
void update(int ptr, int l, int r, int i, pii val)
{
if (l > i || r < i) return;
if (l == r)
{
segTree[ptr] = val;
return;
}
update(ptr * 2, l, (l + r) / 2, i, val);
update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, val);
segTree[ptr] = max(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
pii getVal(int ptr, int l, int r, int i, int j)
{
if (l > j || r < i) return {0,0};
if (i <= l && r <= j) return segTree[ptr];
return max(
getVal(ptr * 2, l, (l + r) / 2, i, j),
getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j)
);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> p[i].l >> p[i].r;
p[i].idx = i;
tmp[i] = p[i];
}
sort(p, p + n, comp);
int ptr = 0;
bool isYes = true;
for (int i = 0; i < n; i++)
{
while (ptr < n && p[ptr].l == i + 1) st.insert(p[ptr++]);
pos cur = *st.begin();
st.erase(st.begin());
ans1[cur.idx] = i + 1;
ans2[cur.idx] = i + 1;
ans_idx[i + 1] = cur.idx;
}
for (int i = 1; i <= n; i++)
{
int idx = ans_idx[i];
pii v = { tmp[idx].r, idx };
update(1, 1, n, i, v);
if (i > 1 && isYes)
{
pii res = getVal(1, 1, n, tmp[idx].l, i - 1);
if (res.first >= i)
{
isYes = false;
swap(ans2[res.second], ans2[idx]);
}
}
}
if (isYes)
{
cout << "YES\n";
for (int i = 0; i < n; i++) cout << ans1[i] << ' ';
}
else
{
cout << "NO\n";
for (int i = 0; i < n; i++) cout << ans1[i] << ' ';
cout << "\n";
for (int i = 0; i < n; i++) cout << ans2[i] << ' ';
}
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
Codeforces Round #640 (Div. 4) (1) | 2020.05.10 |
---|---|
Codeforces Round #639 (Div. 1, Div. 2) (0) | 2020.05.08 |
Educational Codeforces Round 86 (0) | 2020.04.27 |
Codeforces Round #637 (Div. 1, Div. 2) (0) | 2020.04.24 |
Codeforces Round #636 (Div. 3) (0) | 2020.04.22 |