A - Exercising Walk
Problem - A - Codeforces
codeforces.com
고양이 한 마리가 좌표 \((x,y)\)에 위치해 있다.
이 고양이를 \(a\)번 왼쪽, \(b\)번 오른쪽, \(c\)번 아래쪽, \(d\)번 위쪽으로 순서 상관없이 이동시키려고 하는데,
\([x_1,x_2] \times [y_1,y_2]\) 범위 안에서 움직이는게 가능한지 알아내야 한다.
\(x_1 = x_2\)인데 \(a\)이나 \(b\)가 \(0\)이 아니라면, 또는 \(y_1 = y_2\)인데 \(c\)나 \(d\)가 \(0\)이 아니라면 불가능하다.
그렇지 않다면 \(x\)축 방향으로의 이동에 대해 생각했을 때, 한 칸의 여유를 이용해 \(min(a, b) \times 2\)번 움직일 수 있다. $$abab.....ab$$
그러므로 왼쪽으로 \(a-min(a,b)\)번 움직일 공간이 있는지, 오른쪽으로 \(b-min(a,b)\)번 움직일 공간이 있는지 여부만 확인 하면 된다.
\(y\)축에 대해서도 같다.
|
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
|
#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 a, b, c, d; cin >> a >> b >> c >> d;
ll x, y, x1, y1, x2, y2;
cin >> x >> y >> x1 >> y1 >> x2 >> y2;
bool ans = true;
if (x == x1 && x == x2 && (a || b)) ans = false;
if (y == y1 && y == y2 && (c || d)) ans = false;
if (x - x1 < a - b) ans = false;
if (x2 - x < b - a) ans = false;
if (y - y1 < c - d) ans = false;
if (y2 - y < d - c) ans = false;
if (ans) cout << "YES\n";
else cout << "NO\n";
}
}
|
B - Composite Coloring
Problem - B - Codeforces
codeforces.com
\(n\)개의 합성수로 이루어진 수열 \(a\)가 있다. (\(4 \le a_i \le 1000\))
이 수열을 \(m \le 11\)개의 색으로 칠하려 하는데, 다음과 같은 조건을 만족해야 한다.
1. \(1\)부터 \(m\)까지 모든 색이 적어도 한번씩은 나와야 한다.
2. 모든 원소는 적어도 한가지 색으로 칠해져야 한다.
3. 같은 색으로 칠해진 원소 \(a_i\), \(a_j\)에 대하여, \(gcd(a_i,a_j) \gt 1\)이어야 한다.
이 때 가능한 수열을 하나 출력하면 된다.
\(\sqrt {1000}\) 이하의 소수의 개수는 총 11개이다.
$$2,3,5,7,11,13,17,19,23,29,31$$
\(a_i\)는 합성수이므로, 이 11개의 소수중 하나로 나눠떨어지기 때문에
각 a_i를 p번째 소수로 나눴을 때 나눠떨어지면, p번째 색으로 칠하면 된다.
그 후 조건 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
|
#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;
int a[1001];
bool cache[1001];
int ans[1001];
int p[11] = { 2,3,5,7,11,13,17,19,23,29,31 };
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 >> a[i], cache[i] = 0;
vector <int> res[11];
for (int k = 0; k < 11; k++)
{
for (int i = 0; i < n; i++)
{
if (cache[i]) continue;
if (a[i] % p[k] == 0)
{
cache[i] = 1;
res[k].push_back(i);
}
}
}
int cnt = 0;
for (int i = 0; i < 11; i++) if (!res[i].empty()) cnt++;
cout << cnt << '\n';
cnt = 0;
for (int i = 0; i < 11; i++)
{
if (res[i].empty()) continue;
for (auto it : res[i]) ans[it] = cnt + 1;
cnt++;
}
for (int i = 0; i < n; i++) cout << ans[i] << ' ';
cout << '\n';
}
}
|
C - K-Complete Word
Problem - C - Codeforces
codeforces.com
길이 \(n\)의 단어 \(s\)를 다음과 같은 조건을 만족할때 \(k\)-complete라고 하자.
1. \(s\)는 팰린드롬이다.
2. \(s\)의 주기가 \(k\)이다.
길이 \(n\)의 단어 \(s\)가 주어졌을 때, 이 단어를 \(k\)-complete하게 만들기 위해 바꿔야 하는 철자의 최소 개수를 구해야 한다.
위의 조건을 만족하려면 한 주기를 이루는 \(k\)길이의 단어가 팰린드롬이어야 한다는 사실을 알 수 있다.
따라서 단어 \(s\)에서 철자들이 모두 같아야 하는 위치들도 알 수 있는데,
이때 (철자들이 모두 같아야 하는 위치의 수 - 그 위치에서 가장 많이 등장하는 철자의 수)의 합이 답이 된다.
|
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 n, k;
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;
int ans = 0;
for (int i = 0; i < k / 2; i++)
{
map <int, int> mp;
for (int j = 0; j < n / k; j++)
{
mp[s[j * k + i]]++;
mp[s[(j + 1) * k - 1 - i]]++;
}
int mx = 0;
ans += (n / k * 2) - mx;
}
if (k % 2)
{
map <int, int> mp;
for (int j = 0; j < n / k; j++)
{
mp[s[j * k + k / 2]]++;
}
int mx = 0;
ans += (n / k) - mx;
}
cout << ans << '\n';
}
}
|
D - Walk on Matrix
Problem - D - Codeforces
codeforces.com
\(n \times m\) 크기의 행렬 \(A\)가 주어진다.
플레이어는 처음에 \(A_{1,1}\)에 서있고, 오른쪽 또는 아래로만 이동해 \(A_{n,m}\)까지 이동하려고 한다.
플레이어의 점수는 그 사이에 이동한 모든 \(A_{i,j}\) 값들을 bitwise AND한 값이다.
이를 해결하기 위한 틀린 알고리즘이 주어지고, \(n, m, k\)가 주어졌을 때, 이 알고리즘을 이용해 나오는 값과 실제 정답의 차이가 \(k\)가 되는 행렬 하나를 출력하면 된다.
\(2^{17}\)이 \(10^5\)보다 크다는 사실을 이용하면, 잘못된 알고리즘을 이용했을 때 0을 출력하도록 적절히 행렬을 만들 수 있다.
Tutorial에 올라온 방법
$$ \begin{pmatrix} 2^{17}+k & 2^{17} & 0 \\ k & 2^{17}+k & k \\ \end{pmatrix} $$
본인 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#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 k; cin >> k;
cout << "3 3\n";
cout << "262143 262143 262143\n";
cout << "131072 " << k << " 131072\n";
cout << "262143 262143 131071\n";
}
|
E - Height All the Same
Problem - E - Codeforces
codeforces.com
\(n \times m\) 격자가 있고, 칸 \(i,j\)에 \(a_{i,j}\)개의 정육면체가 쌓여져 있다고 하자.
플레이어는 다음과 같은 연산을 할 수 있다.
1. 두 인접한 셀에 정육면체를 하나씩 쌓는다.
2. 한 셀에 정육면체 2개를 쌓는다.
이런 연산을 무제한으로 해서 모든 셀의 높이를 같게 만드려고 하는데, 모든 경우에 이것이 가능한 것은 아니다.
\(n, m, L, R\)를 주어질 때, \(L \le a_{i,j} \le R\)를 만족하며 모든 셀을 같은 높이로 만들 수 있는 초기 격자의 상태의 개수를 \(998,244,353\)으로 나눈 나머지를 구해야 한다.
관찰을 잘 해보면 다음과 같은 사실을 알 수 있다.
1. \(n \times m\)가 홀수인 경우는 모든 경우에서 가능하다.
2. \(n \times m\)가 짝수라면, \(a_{i,j}\)가 짝수인 셀의 개수가 짝수인 경우에만 가능하다.
1번의 경우에는 간단하니 2번의 경우를 계산해보자.
\(L\)과 \(R\) 사이 홀수의 개수를 \(cnt_{odd}\), 짝수의 개수를 \(cnt_{even}\) 이라고 하면,
$$\sum_{i=0}^{nm/2}{cnt_{odd}}^{2i}{cnt_{even}}^{nm-2i} \cdot {_{nm}C_{2i}}$$
가 답이 될것이다.
여기에서
$$(a+b)^n + (a-b)^n = 2 \sum_{i=0}^{n/2}a^{2i}b^{n-2i} \cdot {_nC_{2i}}$$
라는 사실을 이용하면 \(O(log(nm))\)의 시간에 답을 구할 수 있다.
|
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 MOD = 998244353;
const ll mpow(ll a, ll n) // a^n
{
if (n == 0) return 1;
ll t = mpow(a, n / 2);
t = t * t % MOD;
if (n % 2) t = t * a % MOD;
return t;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ll n, m, l, r; cin >> n >> m >> l >> r;
n *= m;
ll odd = (r - l) / 2 + 1;
ll even = (r - l) / 2 + 1;
if ((r - l) % 2 == 0)
{
if (l % 2) even--;
else odd--;
}
ll ans;
if (n % 2) ans = mpow(r - l + 1, n);
else
{
ll res1 = mpow(odd + even, n);
ll res2 = mpow(odd - even, n);
ans = (res1 + res2) % MOD * mpow(2, MOD - 2) % MOD;
}
cout << ans;
}
|
F - Independent Set
Problem - F - Codeforces
codeforces.com
그래프 \(G = (V,E)\)에 대해 어떤 그래프 \(G^\prime = (V^\prime,E^\prime)\)가 \(E^\prime \subset E\)를 만족하고, 모든 정점이 적어도 하나의 간선에 부속되어 있다고 하면, 이 그래프를 edge-induced subgraph라고 하자.
트리 \(G = (V,E)\)가 주어졌을 때, 공집합이 아닌 모든 edge-induced subgraph에 대해 각 subgraph의 독립집합의 개수의 합을 \(998,244,353\)으로 나눈 나머지를 구해야 한다.
단순히 트리 하나가 주어졌을 때 독립집합의 개수를 구하는 것은 다음과 같은 간단한 DP로 구할 수 있다.
\(DP(v, 0) : \) 정점 \(v\)를 루트로 하는 서브트리에 대해 \(v\)가 집합에 포함되어 있지 않을 때, 독립집합의 총 개수
\(DP(v, 1) : \) 정점 \(v\)를 루트로 하는 서브트리에 대해 \(v\)가 집합에 포함되어 있을 때, 독립집합의 총 개수
\(DP(v,0) = \prod_{u=child(v)} DP(u,0)+DP(u,1)\)
\(DP(v,1) = \prod_{u=child(v)} DP(u,0)\)
이 식을 조금 더 응용해서,
정점 \(v\)에서 자식 \(u\)까지의 간선을 잇는지 끊는지 여부까지 더하면 정점 \(v\)를 루트로 하는 서브트리의 edge-induced subgraph의 독립집합의 수도 만들 수 있다.
\(DP(v,0) = \prod_{u=child(v)} 2DP(u,0)+2DP(u,1)\)
\(DP(v,1) = \prod_{u=child(v)} 2DP(u,0)+DP(u,1)\)
이 때, 예외가 한가지 생기게 되는데, 정점 v가 모든 child와 끊어져 있다면 edge-induced subgraph가 아니게 된다. 이 부분을 따로 처리해주기 위해 다음을 정의하자.
\(DP(v, 2) : \) 정점 \(v\)를 루트로 하는 서브트리의 edge-induced subgraph에 대해 \(v\)가 모든 자식과 연결되어 있지 않을 때, 독립집합의 총 개수
그럼 다음과 같은 식을 만들 수 있다.
\(DP(v,0) = \prod_{u=child(v)} 2DP(u,0)+2DP(u,1)-DP(u,2)\)
\(DP(v,1) = \prod_{u=child(v)} 2DP(u,0)+DP(u,1)-DP(u,2)\)
\(DP(v,2) = \prod_{u=child(v)} DP(u,0)+DP(u,1)-DP(u,2)\)
루트를 1번 정점이라고 하면, 답은 \(DP(1,0) + DP(1,1) - DP(1,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
|
#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 int MOD = 998244353;
int n;
vector <int> graph[300001];
ll dp[300001][3];
void solve(int v, int p)
{
dp[v][0] = dp[v][1] = dp[v][2] = 1;
for (auto nv : graph[v])
{
if (nv == p) continue;
solve(nv, v);
ll res = 0;
res = dp[nv][0] * 2 % MOD;
res += dp[nv][1] * 2 % MOD; res %= MOD;
res += MOD - dp[nv][2]; res %= MOD;
dp[v][0] *= res; dp[v][0] %= MOD;
res = dp[nv][0] * 2 % MOD;
res += dp[nv][1]; res %= MOD;
res += MOD - dp[nv][2]; res %= MOD;
dp[v][1] *= res; dp[v][1] %= MOD;
res = dp[nv][0];
res += dp[nv][1]; res %= MOD;
res += MOD - dp[nv][2]; res %= MOD;
dp[v][2] *= res; dp[v][2] %= MOD;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int u, v; cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
solve(1, 0);
cout << (dp[1][0] + dp[1][1] + MOD - dp[1][2] - 1) % MOD;
}
|
G - No Monotone Triples
Problem - G - Codeforces
codeforces.com
추가 예정
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #633 (Div. 1, Div. 2) (0) | 2020.04.13 |
|---|---|
| Educational Codeforces Round 85 (0) | 2020.04.12 |
| Codeforces Round #632 (Div. 2) (2) | 2020.04.09 |
| Codeforces Round #631 (Div. 1, Div. 2) (0) | 2020.04.07 |
| Codeforces Round #629 (Div. 3) (0) | 2020.03.30 |