A - Puzzle Pieces
Problem - A - Codeforces
codeforces.com
퍼즐 조각 하나가 주어진다.
이 퍼즐 조각을 \(n\)행 \(m\)열로 늘어 놓을 때, 맞닿는 면이 서로 완벽히 맞도록 할 수 있는지 알아내야 한다.
먼저 행이나 열이 1개라면, 무조건 가능함이 자명하다.
그렇지 않다면, 행과 열이 각각 2개인 경우를 제외하고는 만드는 것이 불가능하다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#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 a, b; cin >> a >> b;
if (a > b) swap(a, b);
if (a == 1 || a == 2 && b == 2) cout << "YES\n";
else cout << "NO\n";
}
}
|
B - Card Constructions
Problem - B - Codeforces
codeforces.com
\(n\)개의 카드가 있다.
이 카드를 이용해 문제에 주어진 피라미드를 만드려고 한다.
피라미드를 만들 때에는 현재 가진 카드로 만들 수 있는 가장 높은 피라미드를 만들어야 하고,
남은 카드를 이용해 피라미드를 만드는 것을 반복한다.
만들어지는 피라미드의 개수를 구해야 한다.
피라미드를 만들 수 있는 카드 수를 미리 구해 놓자.
직접 계산해 보면 \(10^9\)이하의 카드로 만들 수 있는 피라미드의 가지수는 \(25819\)가지라는 사실을 알 수 있다.
그 후 가장 많은 카드를 사용하는 피라미드부터 시작해 현재 남아 있는 카드를 이용해 만드는 것이 가능한지 확인하면 된다.
남은 카드의 수가 굉장히 빨리 줄어들기 때문에 충분히 시간안에 돌아가게 된다.
|
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
|
#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; }
vector <ll> card;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ll d = 2;
ll sum = 0;
while (sum <= 1e9)
{
sum += d;
card.push_back(sum);
d += 3;
}
reverse(card.begin(), card.end());
int t; cin >> t;
while (t--)
{
ll n; cin >> n;
int ans = 0;
for (ll tmp : card)
{
while (n >= tmp)
{
n -= tmp;
ans++;
}
}
cout << ans << '\n';
}
}
|
A - Hilbert's Hotel
Problem - A - Codeforces
codeforces.com
무한히 많은 수의 방을 가진 힐베르트 호텔이 있다.
이 호텔은 모든 정수에 1:1 대응하는 호텔 방이 하나씩 존재한다.
이 호텔에는 현재 모든 방에 1명의 손님이 투숙하고 있다.
\(n\)개의 수가 주어지는데,
모든 정수 \(k\)에 대하여, \(k\)번 방에 있는 손님을 \(k+a_{k \bmod n}\)번 방으로 옮기려고 한다.
모든 손님이 방을 옮기고 난 후에도 모든 방에 1명의 손님이 있게 되는지 알아내야 한다.
\(0 \le i \le n-1\)에 대하여, \(f(i) = (i+a_i) \bmod k\)를 계산하자.
서로 다른 \(f(i)\)의 수가 \(k\)개라면 모든 정수는 다른 정수에 1: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;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll n;
ll a[200001];
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];
set <ll> st;
for (ll i = 0; i < n; i++)
{
ll res = ((i + a[i]) % n + n) % n;
st.insert(res);
}
if (st.size() == n) cout << "YES\n";
else cout << "NO\n";
}
}
|
B - Monopole Magnets
Problem - B - Codeforces
codeforces.com
N극 또는 S극 하나만으로 이루어진 자석이 있다.
\(n \times m\)크기의 격자가 있고, 이 격자에 자석을 적당히 놓으려고 한다.
같은 격자에 여러개의 자석을 놓을 수도 있다.
자석을 놓았다면, 다음과 같은 연산을 할 수 있다.
1. N극 자석 하나와 S극 자석 하나를 고른다.
2. 두 자석이 같은 위치에 있거나, 같은 행 또는 같은 열에 있지 않다면 무시한다.
3. 그렇지 않다면, N극 자석을 S극 자석이 있는 방향으로 1칸 이동한다.
모든 격자는 검은색 또는 흰색으로 칠해져 있는데, 아래의 조건을 만족하도록 자석을 놓아야 한다.
1. 모든 열과 행에 적어도 하나의 S극 자석이 존재해야 한다.
2. 격자가 검은색으로 칠해져 있다면, 몇 번의 연산 후에 N극 자석이 이 칸에 도달하는것이 가능해야 한다.
3. 격자가 흰색으로 칠해져 있다면, 어떻게 연산하더라도 N극 자석이 이 칸이 도달하는것이 불가능해야 한다.
위 조건을 만족하도록 자석을 놓는 것이 가능한지 알아내야 한다.
가능하다면, 놓을 수 있는 N극 자석의 수의 최소값을 출력해야 한다.
관찰을 잘 해보자.
같은 행 또는 열에 대해서, 검은색으로 칠해진 두 칸이 그 행 또는 열 내에서 검은 칸만을 이용해 이동할 수 없다면, 조건에 만족하도록 자석을 놓는 것이 불가능함을 알 수 있다.
각 행이나 열에 S극이 적어도 하나씩은 존재해야 하는데, 그러면 N극이 흰색 칸으로 이동할 수 있게 되기 때문이다.
또 빈 행이나 빈 열이 있을 경우, 빈 열이나 빈 행 역시 존재해야 한다.
그렇지 않으면 그 빈 행이나 열에 S극을 놓았을 때, N극이 흰색 칸으로 이동할 수 있게 된다.
여기까지 조건을 만족한다면, 모든 검은색 칸에 S극 자석을 놓으면 된다.
필요한 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
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
|
#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, m;
string board[1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool cache[1001][1001];
void DFS(int x, int y)
{
cache[x][y] = 1;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == '.') continue;
if (cache[nx][ny]) continue;
DFS(nx, ny);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> board[i];
bool emp_row = 0, emp_col = 0;
for (int i = 0; i < n; i++)
{
int l = 0, r = m - 1;
while (l < m && board[i][l] == '.') l++;
while (r >= 0 && board[i][r] == '.') r--;
if (l == m) emp_row = 1;
for (int j = l; j <= r; j++)
{
if (board[i][j] == '.')
{
cout << -1;
return 0;
}
}
}
for (int j = 0; j < m; j++)
{
int l = 0, r = n - 1;
while (l < n && board[l][j] == '.') l++;
while (r >= 0 && board[r][j] == '.') r--;
if (l == n) emp_col = 1;
for (int i = l; i <= r; i++)
{
if (board[i][j] == '.')
{
cout << -1;
return 0;
}
}
}
if (emp_row != emp_col)
{
cout << -1;
return 0;
}
int ans = 0;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
{
if (board[i][j] == '.') continue;
if (!cache[i][j])
{
ans++;
DFS(i, j);
}
}
cout << ans;
}
|
C - Quantifier Question
Problem - C - Codeforces
codeforces.com
\(m\)개의 부등식이 주어지고, 이 부등식들이 모두 논리 AND로 연결된 명제 함수가 주어진다.
이 함수 앞에 한정 명제를 주어진 순서대로 붙여서, 식을 참으로 만들려고 한다.
이 때, 사용할 수 있는 전칭 기호의 개수의 최댓값과 실해를 출력해야 한다.
어떻게 해도 식을 참으로 만들 수 없다면, -1을 출력해야 한다.
\(x_a < x_b\)라는 식이 있을 때, 이 식을 정점 \(a\)에서 \(b\)까지의 단방향 간선이 존재하는 그래프로 변환할 수 있다.
이 그래프에 사이클이 존재한다면, 모순이 되어 식은 무조건 거짓이 된다.
그렇지 않다면 이 그래프는 DAG가 되고, 각 원소의 상대적 크기는 그래프의 위상정렬을 하나 만듦으로써 정해질 수 있다.
이제 각 \(x_i\)에 대해 사용할 수 있는 한정 명제를 구해보자.
\(j \lt i\)인 \(x_i, x_j\)에 대해, \(x_i\)와 \(x_j\)를 직접적으로 비교할 수 있다면, \(x_i\)에는 전칭 기호가 붙을 수 없다.
따라서 \(1 \le i \le n\)에 대해 크기를 직접 비교할 수 있는 다른 \(x_j\)가 존재한다면 (\(j \le i\)), 무조건 한정 기호가 붙어야 한다.
그렇지 않다면, 전칭 기호를 붙이면 된다.
위를 만족하는 \(j\)의 존재 여부는 그래프가 DAG이기 때문에, 순방향 그래프와 간선을 모두 뒤집은 역방향 그래프 두 가지 경우에 대해 각각 간단한 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
|
#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, m;
vector <int> graph[200001];
vector <int> rev_graph[200001];
const int INF = 987654321;
bool hasCycle = 0;
int cache[200001];
void DFS(int v)
{
cache[v] = 1;
for (auto nv : graph[v])
{
if (cache[nv] == 1)
hasCycle = 1;
if (cache[nv] == 0)
DFS(nv);
}
cache[v] = 2;
}
int dp1[200001];
int dp2[200001];
int solve(int v, vector <int>* graph, int* dp)
{
int& ret = dp[v];
if (ret != -1) return ret;
ret = v;
for (auto nv : graph[v])
{
ret = min(ret, solve(nv, graph, dp));
}
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v; cin >> u >> v;
graph[u].push_back(v);
rev_graph[v].push_back(u);
}
for (int i = 1; i <= n; i++)
{
if (cache[i] == 0) DFS(i);
}
if (hasCycle)
{
cout << -1;
return 0;
}
int ans = 0;
string str;
memset(dp1, -1, sizeof dp1);
memset(dp2, -1, sizeof dp2);
for (int i = 1; i <= n; i++)
{
if (solve(i, graph, dp1) == i && solve(i, rev_graph, dp2) == i)
{
ans++;
str += 'A';
}
else str += 'E';
}
cout << ans << '\n';
cout << str;
}
|
D - Résumé Review
Problem - D - Codeforces
codeforces.com
\(n\)개의 수로 이루어진 수열 \(a\)가 주어진다.
\(1 \le i \le n\)에 대해서, \(0 \le b_i \le a_i\)를 만족하고, \(\sum b_i = k\)를 만족하는 새로운 수열 \(b\)를 만드려고 한다.
이 때 이 수열 \(b\)에 대한 함수값 \(f(b)\)는 다음과 같다.
$$f(b) = \sum_{i=1}^n b_i(a_i - b_i^2)$$
\(f(b)\)를 최대화 하는 수열 \(b\)를 구해야 한다.
우선 \(\sum b_i = k\)라는 조건은 무시하자.
임의의 \(b_i\)를 1 증가시켜 \(x\)로 만들었다고 할 때, \(f(b)\)의 변화량 \(d_{i,x}\)는 다음과 같다.
$$d_{i, x} = x(a_i - x^2) - (x-1)(a_i-(x-1)^2) = a_i-3x^2+3x-1$$
이 값은 \(x \ge 1\)에서 항상 감소한다.
따라서 \(1 \le i \le n\)에 대해 그리디하게 \(d_{i, b_i+1}\)가 가장 큰 값을 택했을 때의 \(i\)를 \(j\)라고 했을 때, \(b_j\)를 1 증가시키는 것을 \(k\)번 반복함으로써, 답을 구할 수 있게 된다.
하지만 \(k\)가 최대 \(10^{14}\)기 때문에 이 방식 그대로 하면 시간초과가 나게 도니다.
\(d_{i, x}\)는 \(i\)가 증가함에 따라 항상 감소하기 때문에 \(j\)를 한번 고를 때마다 다음 \(d_{j, b_j+1}\)의 값은 항상 감소하게 된다.
따라서 이분탐색을 이용해 \(d_{i, x}\)의 최대값을 구할 수 있게 된다.
이 때 고정된 값 \(y\)에 대해 \(d_{i, x} \ge y\)를 만족하는 \(i\)의 최소값을 구해야 하는데, 함수가 단조 감소하므로 역시 이분탐색을 사용해 \(O(\log a_i)\)에 해결하거나, 이차방정식의 해를 직접 구함으로써 \(O(1)\)에 해결할 수 있다.
따라서 총 시간복잡도는 전자일 때 \(O(n\log d \log a)\), 후자일 때 \(O(n\log d)\)이다.
(\(d : d_{i, x}\) 의 최대값, \(a : a_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
|
#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 = 4e18;
ll n, k;
ll a[100001];
ll ans[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
ll l = -INF, r = INF;
ll sum = 0;
while (l + 1 < r)
{
ll m = (l + r) / 2;
sum = 0;
for (int i = 0; i < n; i++)
{
ll tl = 0, tr = a[i] + 1;
while (tl + 1 < tr)
{
ll tm = (tl + tr) / 2;
ll res = a[i] - 3 * tm * tm + 3 * tm + 1;
if (res >= m) tl = tm;
else tr = tm;
}
sum += tl;
}
if (sum > k) l = m;
else r = m;
}
sum = 0;
for (int i = 0; i < n; i++)
{
ll tl = 0, tr = a[i] + 1;
while (tl + 1 < tr)
{
ll tm = (tl + tr) / 2;
ll res = a[i] - 3 * tm * tm + 3 * tm + 1;
if (res >= r) tl = tm;
else tr = tm;
}
ans[i] = tl;
sum += tl;
}
priority_queue <pll> pq;
for (int i = 0; i < n; i++)
{
if (ans[i] == a[i]) continue;
ll res = a[i] - 3 * (ans[i] + 1) * (ans[i] + 1) + 3 * (ans[i] + 1) + 1;
pq.push({ res, i });
}
for (int i = 0; i < k - sum; i++)
{
pll tmp = pq.top(); pq.pop();
int idx = tmp.second;
ans[idx]++;
if (ans[idx] != a[idx])
{
ll res = a[idx] - 3 * (ans[idx] + 1) * (ans[idx] + 1) + 3 * (ans[idx] + 1) + 1;
pq.push({ res, idx });
}
}
for (int i = 0; i < n; i++) cout << ans[i] << ' ';
}
|
cs |
E - Train Tracks
Problem - E - Codeforces
codeforces.com
추가 예정
F - Piet's Palette
Problem - F - Codeforces
codeforces.com
추가 예정
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #641 (Div. 1, Div. 2) (0) | 2020.05.13 |
|---|---|
| Codeforces Round #640 (Div. 4) (1) | 2020.05.10 |
| Codeforces Round #638 (Div. 2) (0) | 2020.05.04 |
| Educational Codeforces Round 86 (0) | 2020.04.27 |
| Codeforces Round #637 (Div. 1, Div. 2) (0) | 2020.04.24 |
