A - Magical Sticks
Problem - A - Codeforces
codeforces.com
각 \(1\)부터 \(n\)까지의 길이를 가지는 막대가 하나씩 있다.
이 막대를 2개씩 붙여 새로운 막대를 만들 수도 있을 때, 같은 길이를 가지는 막대들의 최대 개수를 구해야 한다.
길이 \(1\)과 \(n-1\)인 막대, \(2\)와 \(n-2\)인 막대... 를 각각 붙여 \(n\) 길이의 막대를 만드는 것이 최선임을 알 수 있다.
따라서 답은 \(\lceil \frac n2 \rceil\)이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#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;
cout << (n - 1) / 2 + 1 << '\n';
}
}
|
B - Magical Calendar
Problem - B - Codeforces
codeforces.com
달력이 있고, 이 달력에 연속된 \(n\)일을 표시하려고 한다.
이 달력의 한 주에 해당되는 날의 수를 \(1\)이상 \(r\)이하 범위에서 정할 수 있을 때, 표시한 날로 만들어지는 서로 다른 도형의 개수를 구해야 한다.
도형은 모서리로 서로 모두 이어져 있어야 하며, 평행이동 했을 때 같으면 같은 도형이다.
한 주가 \(i \lt n\)일이라면 가능한 도형의 수가 \(i\)가지이고,.
한 주가 \(n\)일보다 크거나 같다면 가능한 도형의 수는 모두 합해 1가지 뿐이라는 사실을 알 수 있다.
1부터 \(x\)까지의 합은 \(O(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
|
#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, r; cin >> n >> r;
ll tmp = min(n - 1, r);
ll ans = tmp * (tmp + 1) / 2;
if (r >= n) ans++;
cout << ans << '\n';
}
}
|
C - A Cookie for You
Problem - C - Codeforces
codeforces.com
\(a\)개의 바닐라맛 쿠키와 \(b\)개의 초콜릿만 쿠키가 있다.
\(n\)명의 1타입 사람과 \(m\)명의 2타입 사람이 있는데,
1타입 사람은 두 쿠키 중 많은 개수의 쿠키를 하나 먹고,
2타입 사람은 두 쿠키 중 적은 개수의 쿠키를 하나 먹는다.
\(a,b,n,m\)이 주어졌을 때, 모든 사람이 쿠키를 먹을 수 있는지 여부를 알아내야 한다.
무조건 2타입 사람들이 먼저 쿠키를 먹게 하는 것이 유리함을 알 수 있다.
\(\min (a,b)\)가 \(m\)보다 크거나 같고, \(a+b \ge n+m\)이면 가능하고, 아니면 불가능하다.
|
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--)
{
ll a, b, n, m;
cin >> a >> b >> n >> m;
if (min(a, b) >= m && a + b >= n + m) cout << "Yes\n";
else cout << "No\n";
}
}
|
D - Grid-00100
Problem - D - Codeforces
codeforces.com
\(n \times n\)크기의 격자가 있다.
이 격자는 초기에 모두 0으로 채워져 있고, \(k\)개의 1을 덧쓰려고 한다.
\((\text{1이 가장 많은 행에 쓰여진 1의 수} - \text{1이 가장 적은 행에 쓰여진 1의 수})^2\)
+ \((\text{1이 가장 많은 열에 쓰여진 1의 수} - \text{1이 가장 적은 열에 쓰여진 1의 수})^2\)
를 최소화 하려고 할 때, 그 때의 값과 격자의 상태를 출력해야 한다.
현재 격자에 1을 하나 추가한다고 할 때, 1이 가장 적은 행과 열이 교차하는 곳에 1을 써넣는 것이 가장 이득임을 알 수 있다.
대각선 방향으로 \(k\)개의 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
|
#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 ans[301][301];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n, k; cin >> n >> k;
memset(ans, 0, sizeof ans);
int x = 0, y = 0;
while (k)
{
ans[x][y] = 1;
k--;
x = (x + 1) % n;
y = (y + 1) % n;
if (ans[x][y]) y++;
}
vector <int> r, c;
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = 0; j < n; j++) sum += ans[i][j];
r.push_back(sum);
}
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = 0; j < n; j++) sum += ans[j][i];
c.push_back(sum);
}
int t1 = *max_element(r.begin(), r.end()) - *min_element(r.begin(), r.end());
int t2 = *max_element(c.begin(), c.end()) - *min_element(c.begin(), c.end());
int res = t1 * t1 + t2 * t2;
cout << res << '\n';
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << ans[i][j];
cout << '\n';
}
}
}
|
E - Asterism (Hard Version)
Problem - E2 - Codeforces
codeforces.com
다음과 같은 게임을 하려고 한다.
1. 초기에 \(x\)개의 사탕을 들고 시작한다.
2. 적과 사탕 개수를 비교해서, 더 많은 사탕을 가진 쪽이 이긴다.
3. 이겼다면 1개의 사탕을 추가로 받는다.
\(n\)명의 모든 적과 대결해 승리했다면, 게임에서 이겼다고 한다.
적이 가지고 있는 사탕의 개수를 나타내는 배열 \(a\)가 있다.
이 배열의 인덱스를 이용한 순열로 각 차례마다 적이 몇개의 사탕을 가지고 있을지 결정할 수 있다.
예를 들어, \(a = \{2,4,3\}\)이고 순열이 \(\{2,3,1\}\)이라면, 적은 나오는 순서대로 \(a_2 = 4, a_3 = 3, a_1 = 2\)개의 사탕을 가진채로 등장한다.
각 \(x\)에 대해, 게임에서 이길 수 있는 순열의 개수를 \(f(x)\)라고 하자.
주어지는 소수 \(p\)에 대해, \(f(x)\)가 \(p\)로 나누어 떨어지지 않는 \(x\)를 모두 알아내야 한다.
먼저 게임을 이기기 위한 \(x\)의 하한과 상한을 계산하자.
\(a\)를 정렬한 다음, \(a_i - i\)의 최대값이 하한, \(a_i\)의 최대값이 상한임을 알 수 있다.
\(x\)가 정해졌을 때, \(f(x)\)를 계산해보자.
맨 처음에 올 수 있는 수의 개수는 \(n - (\text{a에서 x보다 큰 수의 개수})\),
그 다음에 올 수 있는 수의 개수는 \(n-1 - (\text{a에서 x+1보다 큰 수의 개수})\)... 이다.
\(x\)보다 큰 수에는 \(x+1\)보다 큰 수가 포함되기 때문에,
이와 같이 계산해서 나온 수들을 모두 곱함으로써 순열의 개수를 구할 수 있게 된다.
E1은 이를 \(O(n^2)\) 완전탐색으로 구해 풀 수 있다.
\(x\)의 값에 따라, \(f(x)\)가 어떻게 변화하는지 살펴보자.
\(p\)가 소수이고, 또 \(n\)보다 작거나 같기 때문에 \(f(x)\)가 \(p\)로 나눠 떨어지면, \(f(y)\)도 \(p\)로 떨어질 수 밖에 없음을 관찰로써 알 수 있다.
따라서 조건을 만족하는 \(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
|
#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, p;
ll a[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> p;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
ll st = 0;
ll ed = a[n - 1];
for (int i = 0; i < n; i++)
{
ll res = a[i] - i;
st = max(st, res);
}
int l = st - 1, r = ed + 1;
while (l + 1 < r)
{
int t = (l + r) / 2;
bool flag = true;
for (int i = 0; i < n; i++)
{
int res = (a + n) - upper_bound(a, a + n, t + i);
if ((n - i - res) % p == 0) flag = false;
}
if (flag) l = t;
else r = t;
}
cout << l - st + 1 << '\n';
for (int i = st; i <= l; i++) cout << i << ' ';
}
|
F - Raging Thunder
Problem - F - Codeforces
codeforces.com
왼쪽과 오른쪽으로 가는 컨베이어 벨트가 있다.
공을 컨베이어 벨트에 놓았을 때 컨베이어 벨트의 방향대로 이동하는데, 이동한 위치가 맨 끝이거나 두 컨베이어 벨트의 움직이는 방향이 서로 만나는 방향이라면, 그 위치에 있는 바구니에 공이 들어가게 된다.
초기 컨베이어 벨트의 상태가 주어지고, 쿼리가 주어진다.
각 쿼리에서는 \(l, r\)이 주어지는데, \([l,r]\) 범위에 있는 컨베이어 벨트의 방향을 뒤집고, 이 범위에 공을 하나씩 놓았을 때 가장 많은 공이 모이는 바구니에 들어있는 공의 개수를 출력해야 한다.
문제를 분할해서 생각해보자.
연속된 두 범위 \([l,m], [m+1,r]\)이 있을 때, 두 범위 각각의 상태를 이용해
범위 \([l,r]\)의 상태를 계산할 수 있다.
본인은 각 상태를 다음과 같은 8개의 변수를 이용했다. (이게 가장 쉬운 방법은 아닐것 같다)
맨 왼쪽에 있는 벨트가 왼쪽 방향인지 여부, 맨 왼쪽부터 시작해 같은 방향인 벨트의 길이, 그 다음부터 시작해 같은 방향인 벨트의 길이
맨 오른쪽에 있는 벨트가 오른쪽 방향인지 여부, 맨 오른쪽부터 시작해 같은 방향인 벨트의 길이, 그 다음부터 시작해 같은 방향인 벨트의 길이,
문제에서 원하는 답, 벨트의 방향이 뒤집어졌을 때의 답
이를 세그먼트 트리의 형태로 저장하면, 연속된 범위의 컨베이어 벨트를 뒤집었을 때도 Lazy Propagation을 이용해 \(O(\log 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
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
|
#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 N = 500001;
struct Node
{
bool isll;
int l1, l2;
bool isrr;
int r1, r2;
int mx1, mx2;
int sz;
bool notZero;
};
Node Zero;
Node merge(Node n1, Node n2)
{
if (!n1.notZero) return n2;
if (!n2.notZero) return n1;
Node res;
res.isll = n1.isll;
if (n1.l1 == n1.sz)
{
if (n1.isll == n2.isll)
{
res.l1 = n1.l1 + n2.l1;
res.l2 = n2.l2;
}
else
{
res.l1 = n1.l1;
res.l2 = n2.l1;
}
}
else if (n1.l1 + n1.l2 == n1.sz && n1.isll != n2.isll)
{
res.l1 = n1.l1;
res.l2 = n1.l2 + n2.l1;
}
else
{
res.l1 = n1.l1;
res.l2 = n1.l2;
}
res.isrr = n2.isrr;
if (n2.r1 == n2.sz)
{
if (n2.isrr == n1.isrr)
{
res.r1 = n2.r1 + n1.r1;
res.r2 = n1.r2;
}
else
{
res.r1 = n2.r1;
res.r2 = n1.r1;
}
}
else if (n2.r1 + n2.r2 == n2.sz && n2.isrr != n1.isrr)
{
res.r1 = n2.r1;
res.r2 = n2.r2 + n1.r1;
}
else
{
res.r1 = n2.r1;
res.r2 = n2.r2;
}
res.mx1 = max(n1.mx1, n2.mx1);
// res.mx1 = max(res.mx1, max(res.l1, res.r1));
if (n1.isrr)
{
int tmp = n1.r1;
if (n2.isll) tmp += n2.l1;
else tmp += n2.l1 + n2.l2;
res.mx1 = max(res.mx1, tmp);
}
else
{
int tmp = n1.r1 + n1.r2;
if (n2.isll) tmp += n2.l1;
res.mx1 = max(res.mx1, tmp);
}
res.mx2 = max(n1.mx2, n2.mx2);
// res.mx2 = max(res.mx2, max(res.l1, res.r1));
if (!n1.isrr)
{
int tmp = n1.r1;
if (!n2.isll) tmp += n2.l1;
else tmp += n2.l1 + n2.l2;
res.mx2 = max(res.mx2, tmp);
}
else
{
int tmp = n1.r1 + n1.r2;
if (!n2.isll) tmp += n2.l1;
res.mx2 = max(res.mx2, tmp);
}
res.sz = n1.sz + n2.sz;
res.notZero = 1;
return res;
}
Node segTree[N * 4];
// 0 : left, 1 : right
void update(int ptr, int l, int r, int i, int val)
{
if (i < l || r < i) return;
if (l == r)
{
Node cur;
cur.l1 = 1, cur.l2 = 0;
cur.r1 = 1, cur.r2 = 0;
if (val == 0)
cur.isll = 1, cur.isrr = 0;
else
cur.isll = 0, cur.isrr = 1;
cur.mx1 = 1;
cur.mx2 = 1;
cur.sz = 1;
cur.notZero = 1;
segTree[ptr] = cur;
return;
}
update(ptr * 2, l, (l + r) / 2, i, val);
update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, val);
segTree[ptr] = merge(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
bool lazy[N * 4];
void setLazy(int ptr, int l, int r)
{
lazy[ptr] = 0;
segTree[ptr].isll = !segTree[ptr].isll;
segTree[ptr].isrr = !segTree[ptr].isrr;
swap(segTree[ptr].mx1, segTree[ptr].mx2);
if (l != r)
{
lazy[ptr * 2] = !lazy[ptr * 2];
lazy[ptr * 2 + 1] = !lazy[ptr * 2 + 1];
}
}
Node flip(int ptr, int l, int r, int i, int j)
{
if (lazy[ptr]) setLazy(ptr, l, r);
if (j < l || r < i) return Zero;
if (i <= l && r <= j)
{
segTree[ptr].isll = !segTree[ptr].isll;
segTree[ptr].isrr = !segTree[ptr].isrr;
swap(segTree[ptr].mx1, segTree[ptr].mx2);
if (l != r)
{
lazy[ptr * 2] = !lazy[ptr * 2];
lazy[ptr * 2 + 1] = !lazy[ptr * 2 + 1];
}
return segTree[ptr];
}
Node n1 = flip(ptr * 2, l, (l + r) / 2, i, j);
Node n2 = flip(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j);
segTree[ptr] = merge(segTree[ptr * 2], segTree[ptr * 2 + 1]);
return merge(n1, n2);
}
int n, q;
string s;
void print()
{
for (int i = 1; i <= n; i++)
{
flip(1, 1, n, i, i);
Node res = flip(1, 1, n, i, i);
if (res.isll) cout << "<";
else cout << ">";
}
cout << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
cin >> s;
for (int i = 0; i < n; i++)
{
update(1, 1, n, i + 1, s[i] == '<' ? 0 : 1);
}
while (q--)
{
int l, r; cin >> l >> r;
Node res = flip(1, 1, n, l, r);
cout << res.mx1 << '\n';
//print();
}
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #655 (Div. 2) (0) | 2020.07.12 |
|---|---|
| Codeforces Global Round 9 (0) | 2020.07.05 |
| Codeforces Round #652 (Div. 2) (0) | 2020.06.24 |
| Codeforces Round #651 (Div. 2) (0) | 2020.06.21 |
| Codeforces Global Round 8 (3) | 2020.06.19 |
