A - Meximization
Problem - A - Codeforces
codeforces.com
\(n\)길이의 배열 \(a\)가 주어진다.
이 \(a\)의 원소들의 순서를 재배열해서, 모든 prefix의 MEX값의 합이 최대가 되도록 해야 한다.
큰 MEX값이 최대한 빨리 나와야 함을 알 수 있다.
앞에서부터 \(a_i = i\) (0-index)가 되도록 최대한 수를 채우면 된다.
|
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;
typedef complex<double> cpdb;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
int cnt[101];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
memset(cnt, 0, sizeof cnt);
cin >> n;
for (int i = 0; i < n; i++)
{
int a; cin >> a;
cnt[a]++;
}
for (int i = 0; i <= 100; i++)
{
if (cnt[i])
{
cout << i << ' ';
cnt[i]--;
}
else break;
}
for (int i = 0; i <= 100; i++)
{
for (int j = 0; j < cnt[i]; j++) cout << i << ' ';
}
cout << '\n';
}
}
|
B - M-arrays
Problem - B - Codeforces
codeforces.com
\(n\)길이의 배열 \(a\)가 주어진다.
어떤 배열의 모든 연속된 두 원소의 합이 \(m\)으로 나눠 떨어지면, 이 배열을 \(m\)-divisible array라고 한다.
\(a\)를 몇 개의 배열로 나눠서 각 배열들이 모두 \(m\)-divisible array가 되도록 할 때, 나눈 후 배열 개수의 최소값을 알아내야 한다.
\(a\)의 각 원소를 \(m\)으로 나눈 나머지 (\([0,m-1]\))가 몇 개씩인지 저장하자.
나머지가 0인 원소들과, \(n\)이 짝수일 때 나머지가 \(n/2\)인 원소들은 그 원소들끼리 배열을 만들면 된다.
그 외는 나머지가 \(x\)인 원소와 \(n-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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cpdb;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n, m;
int cnt[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
memset(cnt, 0, sizeof cnt);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int a; cin >> a;
cnt[a % m]++;
}
int ans = 0;
if (cnt[0]) ans++;
for (int i = 1; i < (m + 1) / 2; i++)
{
int lc = cnt[i], rc = cnt[m - i];
if (lc == 0 && rc == 0) continue;
if (lc > rc) swap(lc, rc);
if (lc == 0)
{
ans += rc;
continue;
}
ans += 1 + max(0, rc - (lc + 1));
}
if (m % 2 == 0 && cnt[m / 2]) ans++;
cout << ans << '\n';
}
}
|
C - k-LCM (hard version)
Problem - C2 - Codeforces
codeforces.com
양의 정수 \(n\)이 주어질 때, 다음을 만족하는 \(k\)개의 양의 정수 \(a_1, a_2, \cdots, a_k\)를 구해야 한다.
\(a_1 + a_2 + \cdots + a_k = n\)
\(LCM(a_1,a_2,\cdots,a_k) \le \frac n2\)
먼저 \(k=3\)일 때를 풀어보자.
\(n\)이 홀수라면, \((\lfloor \frac n2 \rfloor, \lfloor \frac n2 \rfloor, 1)\)이 답이다.
\(n\)이 짝수이면서 4로 나눠 떨어지지 않는다면, \((\frac n2 -1, \frac n2 -1, 2)\)가 답이다.
\(n\)이 짝수이면서 4로 나눠 떨어진다면, \((\frac n2, \frac n4, \frac n4)\)가 답이다.
\(k\)가 3보다 크다면, \(n\)과 \(k\)가 각각 \(n-(k-3), 3\)일 때를 푼 다음, \(k-3\)개의 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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cpdb;
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, k; cin >> n >> k;
ll p = k - 3;
n -= p;
if (n % 2) cout << n / 2 << ' ' << n / 2 << ' ' << 1 << ' ';
else
{
if (n / 2 % 2) cout << n / 2 - 1 << ' ' << n / 2 - 1 << ' ' << 2 << ' ';
else cout << n / 2 << ' ' << n / 4 << ' ' << n / 4 << ' ';
}
for (int i = 0; i < p; i++) cout << "1 ";
cout << '\n';
}
}
|
D - Genius
Problem - D - Codeforces
codeforces.com
\(n\)개의 서로 다른 문제가 있다. \(i\)번째 문제의 복잡도 \(c_i\)는 \(2^i\)이다.
\(i\)번째 문제를 풀고 난 다음 \(j\)번째 문제를 풀기 위해서는 다음을 만족해야 한다.
1. \(IQ < |c_i-c_j|\)
2. \(tag_i \ne tag_j\)
\(j\)번째 문제를 푼 후의 \(IQ\)는 \(|c_i-c_j|\)가 되고, \(|s_i-s_j|\)점을 얻게 된다.
초기에 \(IQ=0\)일 때, 얻을 수 있는 최대 점수를 알아내야 한다.
먼저, 서로 다른 두 문제 \(i, j\) (\(i < j\))에 대해, \(c_j - c_i\)의 값은 모두 다름을 알 수 있다.
다음과 같은 DP를 정의하자.
\(dp_i :\) \(i\)번째 문제를 마지막으로 풀었을 때 최대 점수
DP배열의 초기값을 0으로 설정하자.
\(c_j - c_i\)이 작은 문제부터 풀어나가는 것이 무조건 유리하므로, 이 순서대로 문제를 풀어나가며 DP배열을 갱신하면 된다.
|
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;
typedef complex<double> cpdb;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll n;
ll tag[5001];
ll s[5001];
ll dp[5001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n;
for (int i = 0; i < n; i++) cin >> tag[i];
for (int i = 0; i < n; i++) cin >> s[i];
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i++)
{
for (int j = i - 1; j >= 0; j--)
{
if (tag[i] == tag[j]) continue;
ll sj = dp[j], si = dp[i];
ll point = llabs(s[i] - s[j]);
dp[j] = max(dp[j], si + point);
dp[i] = max(dp[i], sj + point);
}
}
cout << *max_element(dp, dp + n) << '\n';
}
}
|
E - Square-free division (hard version)
Problem - E2 - Codeforces
codeforces.com
\(n\)개의 원소를 가진 배열 \(a\)가 주어진다.
이 배열을 몇개의 연속된 부분배열로 나누려고 한다.
나눠진 배열 안에는 어떤 두 원소의 곱도 제곱수가 되어서는 안된다.
이 작업 전에 \(a\)의 원소중 최대 \(k\)개의 수를 원하는 다른 수로 바꿀 수 있다고 할 때,
나눈 후 부분 배열의 개수의 최소값을 알아내야 한다.
먼저 \(a\)의 각 원소를 소인수분해해서, 소인수의 지수가 짝수라면 모두 없애버리자.
그러면 나눠진 배열안에 중복된 수가 없어야 되는 문제로 생각할 수 있다.
\(k\)번의 작업은 고른 수를 배열에 존재하지 않는 소수로 바꾸는 작업이 될 것이다.
어떤 원소 \(a_i\)에서 시작해서, 수를 바꾸는 연산을 하지 않았을 때 최대 몇 번 인덱스까지 같은 배열에 들어갈 수 있는지는 쉽게 계산할 수 있다.
같은 방법으로 1번, 2번, ... ,\(k\)번 연산했을 때 몇 번 인덱스까지 같은 배열에 들어갈 수 있는지를 계산할 수 있다.
이를 투포인터와 적절한 set같은 자료구조로 관리하면, 모든 \(a_i\)에 대해, \([0, k]\)번 수를 바꾸는 연산을 했을 때 최대 몇번 인덱스까지 같은 배열에 들어갈 수 있는지, \(O(n\log n)\)에 계산할 수 있다.
계산한 결과로 \(O(nk)\) DP를 돌리면 된다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cpdb;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int ett[10001];
vector <int> p;
int n, k;
int a[200001];
int rmx[21][200001];
int dp[21][200001];
int solve(int idx, int rk)
{
if (idx >= n) return 0;
int& ret = dp[rk][idx];
if (ret != -1) return ret;
ret = 1e9;
for (int i = 0; i <= rk; i++)
{
int res = 1 + solve(rmx[i][idx], rk - i);
ret = min(ret, res);
}
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for (int i = 2; i <= 10000; i++)
{
if (ett[i] == 0)
{
p.push_back(i);
for (int j = i + i; j <= 10000; j += i) ett[j] = 1;
}
}
int t; cin >> t;
while (t--)
{
cin >> n >> k;
for (int i = 0; i <= k; i++) for (int j = 0; j < n; j++)
dp[i][j] = -1;
for (int i = 0; i < n; i++)
{
cin >> a[i];
int c = a[i];
for (int j = 0; j < p.size() && p[j] * p[j] <= a[i]; j++)
{
while (c % (p[j] * p[j]) == 0) c /= p[j] * p[j];
}
a[i] = c;
}
set <int> mp;
set <pii> midx; // {num, idx}
set <int> st;
int rptr = 0;
for (int i = 0; i < n; i++)
{
while (rptr < n && midx.size() <= k)
{
if (st.find(a[rptr]) != st.end())
{
midx.insert({ a[rptr], rptr });
mp.insert(rptr);
}
else st.insert(a[rptr]);
rptr++;
}
auto it = mp.begin();
for (int j = 0; j <= k; j++)
{
if (it == mp.end()) rmx[j][i] = n;
else
{
rmx[j][i] = *it;
it++;
}
}
auto jt = midx.lower_bound({ a[i], 0 });
if (jt != midx.end() && jt->first == a[i])
{
int idx = jt->second;
mp.erase(idx);
midx.erase(jt);
}
else st.erase(a[i]);
}
int res = solve(0, k);
cout << res << '\n';
}
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #711 (Div. 2) (0) | 2021.03.30 |
|---|---|
| Educational Codeforces Round 106 (1) | 2021.03.20 |
| Codeforces Round #707 (Div. 1, Div. 2) (0) | 2021.03.14 |
| Codeforces Round #703 (Div. 2) (0) | 2021.02.19 |
| Educational Codeforces Round 103 (0) | 2021.02.02 |