A - Domino on Windowsill
Problem - A - Codeforces
codeforces.com
\(2 \times n\)크기의 격자가 있다.
첫번째 열의 첫 \(k_1\)개 칸과 두번째 열의 첫 \(k_2\)개 칸이 흰색으로 칠해져 있고,
그 외의 칸은 검은색으로 칠해져 있다.
\(w\)개의 흰색 도미노와 \(b\)개의 검은색 도미노가 있다.
도미노의 크기는 모두 \(2 \times 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
|
#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, k1, k2; cin >> n >> k1 >> k2;
int w, b; cin >> w >> b;
bool ans = true;
if (k1 + k2 < w * 2) ans = false;
if (n + n - k1 - k2 < b * 2) ans = false;
if (ans) cout << "Yes\n";
else cout << "No\n";
}
}
|
B - Binary Removals
Problem - B - Codeforces
codeforces.com
\(n\)길이의 이진 문자열 \(s\)가 주어진다.
\(s\)의 임의의 문자들을 바꾸어서, \(s\)가 정렬되어 있을 수 있는지 알아내야 한다.
단, 연속된 문자들은 바꿀 수 없다.
정렬된 상태로 가능한 경우가 총 \(n+1\)가지이다.
각각의 경우를 \(O(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
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; }
string s;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> s;
bool ans = false;
for (int k = 0; k <= s.size(); k++)
{
int last = -123;
bool flag = true;
for (int i = 0; i < s.size(); i++)
{
if (k > i)
{
if (s[i] == '1')
{
if (last + 1 >= i) flag = false;
last = i;
}
}
else
{
if (s[i] == '0')
{
if (last + 1 >= i) flag = false;
last = i;
}
}
}
if (flag) ans = true;
}
if (ans) cout << "YES\n";
else cout << "NO\n";
}
}
|
C - Minimum Grid Path
Problem - C - Codeforces
codeforces.com
좌표평면 위의 점 \((0,0)\)에서 시작해, \((n, n)\)까지 이동하려고 한다.
이동은 \(x\)가 증가하는 방향 (오른쪽), \(y\)가 증가하는 방향 (위쪽)으로만 이동할 수 있다.
한번 이동할 때마다 1이상은 이동해야 하는데, \(i\)번째 이동할 때는 1당 \(c_i\)의 비용이 든다.
또, 한번 이동을 마쳤으면 다음에 이동할 때는 무조건 이동 방향을 바꾸어야 하고, 방향은 최대 \(n-1\)번 바꿀 수 있다.
\((n,n)\)까지 도착하는데 필요한 비용의 최소값을 구해야 한다.
우선 최소 2번은 이동해야 한다.
또, 오른쪽과 위쪽 각 방향으로 이동할 때 비용이 최소일 때 최대한 많이 이동하면 된다는 것을 알 수 있다.
\([2, 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
44
45
46
47
48
|
#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 ll INF = 1e18;
ll n;
ll c[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n;
ll ans = INF;
int cnt[2] = { 0,0 };
ll sum[2] = { 0,0 };
ll mn[2] = { INF, INF };
for (int i = 1; i <= n; i++)
{
cin >> c[i];
cnt[i % 2]++;
sum[i % 2] += c[i];
mn[i % 2] = min(mn[i % 2], c[i]);
if (i == 1) continue;
ll res = sum[0] - mn[0] + mn[0] * (n - cnt[0] + 1)
+ sum[1] - mn[1] + mn[1] * (n - cnt[1] + 1);
ans = min(ans, res);
}
cout << ans << '\n';
}
}
|
D - The Number of Pairs
Problem - D - Codeforces
codeforces.com
양의 정수 \(c,d,x\)가 주어진다.
\(c \cdot lcm(a,b) - d \cdot gcd(a,b) = x\)를 만족하는 \((a,b)\)쌍의 개수를 구해야 한다.
\(g = gcd(a,b)\)일 때, \(a = gA, b = gB\)로 바꾼다음 식을 정리하면,
\(AB = k, g = \frac{x}{ck-d}\)라는 식을 얻을 수 있다.
\(g\)는 정수이므로 \(x\)는 \(ck-d\)로 나누어 떨어져야 하고, 여기에서 가능한 \(k\)를 모두 알아낼 수 있다.
\(A, B\)는 서로소이므로, \(k\)의 소인수가 \(p\)개라면 \(2^p\)를 모두 더하면 된다.
|
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
|
#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 ett[20000001];
vector <ll> p;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for (int i = 2; i <= 20000000; i++)
{
if (!ett[i])
{
ett[i] = 1;
p.push_back(i);
for (int j = i + i; j <= 20000000; j += i) ett[j]++;
}
}
int t; cin >> t;
while (t--)
{
ll c, d, x; cin >> c >> d >> x;
ll ans = 0;
vector <ll> div;
for (ll i = 1; i * i <= x; i++)
{
if (x % i == 0)
{
div.push_back(i);
if (i * i != x) div.push_back(x / i);
}
}
for (ll y : div)
{
if ((d + y) % c) continue;
ll k = (d + y) / c;
ans += 1ll << ett[k];
}
cout << ans << '\n';
}
}
|
E - Chaotic Merge
Problem - E - Codeforces
codeforces.com
두 문자열 \(x,y\)가 주어진다.
두 문자열을 merge해 새로운 문자열 \(z\)를 만들려고 한다.
문자열 \(z\)의 인접한 두 문자가 모두 서로 다르다면, \(z\)를 Chaotic하다고 한다.
\(f(l_1, r_1, l_2, r_2)\)를 \(x[l_1,r_1]\)와 \(y[l_2,r_2]\)를 merge했을 때 Chaotic하게 만드는 서로 다른 merge방법의 수라고 할 때,
\(\sum \limits_{1 \le l_1 \le r_1 \le |x| \\ 1 \le l_2 \le r_2 \le |y|} f(l_1, r_1, l_2, r_2)\)를 구해야 한다.
다음과 같은 DP를 정의해 해결하면 된다.
\(DP(k, i, j) : \) \(z\)의 마지막 문자가 \(k\)고, \(x\)의 \(i\)번째 문자, \(y\)의 \(j\)번째 문자부터 merge를 시작했을 때, 문제의 답
\(x, y\)에서 최소 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
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
|
#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 ll MOD = 998244353;
string x, y;
ll dp[27][1001][1001];
ll solve(int c, int xi, int yi)
{
if (xi == x.size() && yi == y.size()) return 1;
ll& ret = dp[c][xi][yi];
if (ret != -1) return ret;
ret = 1;
if (xi < x.size() && c != x[xi] - 'a')
{
ret += solve(x[xi] - 'a', xi + 1, yi);
ret %= MOD;
}
if (yi < y.size() && c != y[yi] - 'a')
{
ret += solve(y[yi] - 'a', xi, yi + 1);
ret %= MOD;
}
return ret;
}
ll dp2[27][1001];
ll solve2(int c, int xi, string& x)
{
if (xi == x.size()) return 1;
ll& ret = dp2[c][xi];
if (ret != -1) return ret;
ret = 1;
if (xi < x.size() && c != x[xi] - 'a')
{
ret += solve2(x[xi] - 'a', xi + 1, x);
ret %= MOD;
}
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(dp, -1, sizeof dp);
cin >> x >> y;
ll ans = 0;
for (int i = 0; i < x.size(); i++) for (int j = 0; j < y.size(); j++)
{
ll res = solve(26, i, j);
ans += res;
ans %= MOD;
}
memset(dp2, -1, sizeof dp2);
for (int i = 0; i < x.size(); i++)
{
ll res = solve2(26, i, x) * y.size() % MOD;
ans += (MOD - res);
ans %= MOD;
}
memset(dp2, -1, sizeof dp2);
for (int i = 0; i < y.size(); i++)
{
ll res = solve2(26, i, y) * x.size() % MOD;
ans += (MOD - res);
ans %= MOD;
}
ans += (ll)x.size() * y.size() % MOD;
ans %= MOD;
cout << ans;
}
|
F - Diameter Cuts
Problem - F - Codeforces
codeforces.com
\(n\)개의 정점을 가진 트리가 주어진다.
이 트리의 \(n-1\)개의 간선중에서, 임의의 간선들을 선택해 모두 없애자.
트리가 여러개로 분할될텐데, 분할된 모든 트리의 지름이 \(k\)이하가 되도록 하는 경우의 수를 구해야 한다.
다음과 같은 DP를 정의하자.
\(DP(v, len) : \) \(v\)를 루트로 하는 서브트리에서, \(v\)에서 시작하는 트리의 최장경로의 길이가 \(len\)일 때, 문제의 답
각 정점 \(v\)의 자식 \(u\)에 대해, DP값을 각각 merge해 나간다고 생각하면,
한번의 merge당 \(O(k^2)\)이므로 총 \(O(nk^2)\)의 복잡도를 가지는데, 이는 너무 느리다.
이를 \(sz(v) \times sz(u)\)에 해주면 총 연산 수가 \(O(n^2)\)로 줄어들게 된다. (\(sz(v) :\) \(v\)를 루트로 하는 서브트리의 크기)
|
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; }
const ll MOD = 998244353;
int n, k;
vector <int> graph[5001];
ll dp[5001][5001];
// dp[v][len] : v의 서브트리에서, v에서 시작하는 최장경로가 len일 때의 답
int h[5001];
ll tmp[5001];
void DFS(int v, int p)
{
dp[v][0] = 1;
h[v] = 1;
ll ans = 0;
for (int nv : graph[v])
{
if (nv == p) continue;
DFS(nv, v);
memset(tmp, 0, sizeof tmp);
for (int i = 0; i <= h[v]; i++) for (int j = 0; j <= h[nv]; j++)
{
if (i + j + 1 <= k)
{
tmp[max(i, j + 1)] += dp[v][i] * dp[nv][j] % MOD;
tmp[max(i, j + 1)] %= MOD;
}
if (i <= k && j <= k)
{
tmp[i] += dp[v][i] * dp[nv][j] % MOD;
tmp[i] %= MOD;
}
}
h[v] = max(h[v], h[nv] + 1);
memcpy(dp[v], tmp, sizeof tmp);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n - 1; i++)
{
int u, v; cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
DFS(1, 0);
ll ans = 0;
for (int i = 0; i <= k; i++)
{
ans += dp[1][i];
ans %= MOD;
}
cout << ans;
}
|
G - Graph Coloring
Problem - G - Codeforces
codeforces.com
추가 예정
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #712 (Div1, Div. 2) (0) | 2021.04.04 |
|---|---|
| Codeforces Round #711 (Div. 2) (0) | 2021.03.30 |
| Codeforces Round #708 (Div. 2) (0) | 2021.03.18 |
| Codeforces Round #707 (Div. 1, Div. 2) (0) | 2021.03.14 |
| Codeforces Round #703 (Div. 2) (0) | 2021.02.19 |