A - Sign Flipping
Problem - A - Codeforces
codeforces.com
\(n\)이 홀수인 배열 \(a\)가 주어진다. \(n\)은 홀수이다.
배열의 원소의 부호를 원하는대로 바꿀 수 있는데, 결과가 다음을 만족해야 한다.
인접한 원소의 차이를 \(a_{i+1} - a_i\)로 정의할 때,
1. 적어도 \(\frac {n-1}{2}\)개의 인접한 원소의 차이는 양수여야 한다.
2. 적어도 \(\frac {n-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
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 a[101];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
{
if (i % 2 == 0)
{
if (a[i] < 0) a[i] = -a[i];
}
else
{
if (a[i] > 0) a[i] = -a[i];
}
cout << a[i] << ' ';
}
cout << '\n';
}
}
|
B - Neighbor Grid
Problem - B - Codeforces
codeforces.com
\(n \times m\)크기의 격자가 주어진다. 각 칸에는 음수가 아닌 정수가 쓰여져 있다.
어떤 칸에 0보다 큰 수 \(k\)가 쓰여져 있으면, 이 칸과 인접한 \(k\)칸에도 0보다 큰 수가 쓰여져 있어야 한다.
각 칸에 1을 더하는 연산을 할 수 있을 때, 격자의 모든 칸이 위 조건을 만족하게 만들 수 있는지 여부를 알아내야 한다.
각 칸이 가질 수 있는 최대값으로 격자을 채울 수 있는지 확인하면 된다.
즉, 격자의 꼭지점에 있는 칸은 2, 모서리 칸은 3, 그 외는 4가 최대값인데, 초기에 칸에 쓰여져 있는 수가 이 값보다 크다면 위 조건을 만족할 수 없다.
|
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
|
#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;
int board[301][301];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n >> m;
bool ans = true;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
{
cin >> board[i][j];
if (i == 0 || i == n - 1)
{
if (j == 0 || j == m - 1)
{
if (board[i][j] > 2) ans = false;
board[i][j] = 2;
}
else
{
if (board[i][j] > 3) ans = false;
board[i][j] = 3;
}
}
else
{
if (j == 0 || j == m - 1)
{
if (board[i][j] > 3) ans = false;
board[i][j] = 3;
}
else
{
if (board[i][j] > 4) ans = false;
board[i][j] = 4;
}
}
}
if (!ans)
{
cout << "NO\n";
continue;
}
cout << "YES\n";
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++) cout << board[i][j] << ' ';
cout << '\n';
}
}
}
|
C - Element Extermination
Problem - C - Codeforces
codeforces.com
길이 \(n\)인 배열 \(a\)가 주어진다.
초기에 이 배열은 \(n\)크기의 순열로 채워져 있다.
인접한 두 칸에 대해 \(a_i \lt a_{i+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
|
#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[300001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
if (a[0] < a[n - 1]) cout << "YES\n";
else cout << "NO\n";
}
}
|
D - Replace by MEX
Problem - D - Codeforces
codeforces.com
\(n\)길이를 가진 배열이 주어진다. 각 원소는 \(0\)이상 \(n\)이하의 정수이다.
이 배열의 원소 하나를 현재 배열의 MEX값으로 바꾸는 연산을 최대 \(2n\)번 할 수 있을 때,
배열을 비내림차순으로 만들 수 있는지 여부를 알아내야 한다.
배열의 원소 \(a_i\)에 들어가야 할 값을 \(i\)로 정해놓고, 다음 규칙에 따라 원소를 바꾸자.
1. 현재 MEX값 \(m\)이 0이 아니라면, \(a_m\)을 \(m\)으로 바꾼다.
2. 현재 MEX값이 0이라면, \(a_i \ne i\)인 칸 중 아무거나 골라 0으로 바꾼다.
그러면 한 칸에 원하는 값이 들어가는데 많아도 2번의 연산만이 필요하게 된다.
|
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
|
#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];
int cnt[1001];
int MEX()
{
for (int i = 0; i <= n; i++)
{
if (cnt[i]==0) return i;
}
}
vector <int> ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n;
ans.clear();
for (int i = 0; i <= n; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
cnt[a[i]]++;
}
for (int i = 0; i < n * 2; i++)
{
int x = MEX();
if (x == 0)
{
int res = -1;
for (int j = 1; j <= n; j++)
{
if (a[j] != j)
{
res = j;
break;
}
}
if (res == -1) break;
int tmp = a[res];
a[res] = 0;
ans.push_back(res);
cnt[tmp]--;
cnt[0]++;
continue;
}
int tmp = a[x];
a[x] = x;
ans.push_back(x);
cnt[tmp]--;
cnt[x]++;
}
cout << ans.size() << '\n';
for (int i : ans) cout << i << ' ';
cout << '\n';
}
}
|
E - Inversion SwapSort
Problem - E - Codeforces
codeforces.com
\(n\)길이의 배열 \(a\)가 주어진다.
\(1 \le u \lt v \le n\)인 \(u,v\)에 대해, \(a_u > a_v\)라면 순서 쌍 \((u,v)\)를 \(a\)의 inversion이라고 하자.
초기 \(a\)의 모든 inversion에 대해, \(a_u\)와 \(a_v\)를 swap함으로써 \(a\)를 정렬할 수 있는지 여부를 알아내야 한다.
가능하다면, swap해야 하는 순서를 출력해야 한다.
우선 좌표압축으로 \(a\)의 원소들을 \(n\)크기의 순열로 만들자.
같은 값은 \(a_i = a_j, i \lt j\)라면 \(a_i < a_j\)로 바꿔도 상태가 달라지지 않는다는 점을 이용해 적절히 변환해줄 수 있다.
맨 마지막 칸 부터 차례대로 정렬한다고 해보자. 이 칸에는 최종적으로 \(n\)이 들어가야 한다.
현재 들어가 있는 수가 \(a_n\)이라고 하면, \(a_n\)과 범위 \([a_n+1, n]\)에 해당하는 수 사이에 inversion이 존재함을 알 수 있다.
맨 마지막 칸에 \(n\)에 들어가게 하면서 \(n\)을 제외한 나머지 수들 사이의 대소관계가 변하지 않도록 할 수 있을까?
현재 \(i\)가 있는 인덱스를 \(idx_i\)라고 하자.
\((a_n, idx_{a_n+1}), (a_n, idx_{a_n+2}), \cdots , (a_n, idx_n)\)의 순서로 swap을 하면 가능함을 알 수 있다.
|
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
|
#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];
int cnt[1001];
int idx[1001];
vector <int> v;
set <pii> st;
vector <pii> ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
v.push_back(a[i]);
}
sort(v.begin(), v.end());
for (int i = 1; i <= n; i++)
{
int res = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
a[i] = res + cnt[res]++;
idx[a[i]] = i;
}
for (int i = n; i > 0; i--)
{
int cur = a[i];
for (int j = cur + 1; j <= i; j++)
{
ans.push_back({ idx[j], i });
int tmp = a[i];
swap(a[i], a[idx[j]]);
idx[tmp] = idx[j];
idx[j] = i;
}
}
cout << ans.size() << '\n';
for (pii it : ans) cout << it.first << ' ' << it.second << '\n';
}
|
F - Integer Game
Problem - F - Codeforces
codeforces.com
두 사람이 게임을 하려고 한다.
처음에 세 묶음의 돌이 있고, 각 묶음에는 \(a,b,c\)개의 돌이 있다.
초기에 각 묶음에 놓인 돌의 개수는 서로 다르다.
선공은 각 묶음에 몇개의 돌을 추가할지 정하고,
후공은 선공이 정한 개수의 돌을 한 묶음에 추가한다. 단, 이전에 골랐던 묶음과 같은 묶음을 고를 수는 없다.
후공은 돌을 추가했을 때, 어떤 두 묶음에 놓인 돌의 개수가 같다면 패배한다.
선공은 1000차례 안에 후공을 패배하지 못하게 하면 패배한다.
선공과 후공 둘 중 하나를 골라 승리해야 한다.
선공이 무조건 승리할 수 있다.
먼저 \(a,b,c\)를 크기순으로 정렬하자. (\(a\)가 가장 작고, \(c\)가 가장 크다.)
선공으로 \((c-a) + (c-b)\)개의 돌을 추가하도록 하자.
만약 후공이 가장 많은 돌이 놓인 묶음을 골랐다면, 위를 한번 더 반복한다.
그러면 후공은 \(a\)개가 놓인 묶음 또는 \(b\)개가 놓인 묶음 둘 중 하나를 고를 수 밖에 없다.
\(a\)개가 놓인 묶음을 선택했다면, 이 묶음은 \(c+c-b\)개의 돌이 놓이게 되고, 셋 중 가장 많은 돌을 가지게 된다.
이 묶음과 \(c\)개의 돌이 놓인 묶음의 돌의 개수의 차이는 \(c-b\)개이다.
\(c\)개의 돌이 놓인 묶음과 \(b\)개의 돌이 놓인 묶음의 돌의 개수의 차이 역시 \(c-b\)개이다.
따라서 \(c-b\)개의 돌을 추가하도록 하면 선공이 승리한다.
후공이 \(b\)개가 놓인 묶음을 선택했을 때도 같은 방법으로 승리할 수 있다.
|
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 main()
{
pll a[4];
for (int i = 1; i <= 3; i++)
{
cin >> a[i].first;
a[i].second = i;
}
sort(a + 1, a + 4);
cout << "First" << endl;
ll plus = 2 * a[3].first - a[1].first - a[2].first;
cout << plus << endl;
int res; cin >> res;
int ridx = 0;
for (int i = 1; i <= 3; i++)
{
if (res == a[i].second) ridx = i;
}
if (ridx == 3)
{
a[3].first += plus;
plus = 2 * a[3].first - a[1].first - a[2].first;
cout << plus << endl;
cin >> res;
for (int i = 1; i <= 3; i++)
{
if (res == a[i].second) ridx = i;
}
}
if (ridx == 1)
plus = a[3].first - a[2].first;
else
plus = a[3].first - a[1].first;
cout << plus << endl;
cin >> res;
return 0;
}
|
G - Tree Modification
Problem - G - Codeforces
codeforces.com
추가 예정
H - Set Merging
Problem - H - Codeforces
codeforces.com
추가 예정
I - Cubic Lattice
Problem - I - Codeforces
codeforces.com
추가 예정
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #656 (Div. 3) (0) | 2020.07.18 |
|---|---|
| Codeforces Round #655 (Div. 2) (0) | 2020.07.12 |
| Codeforces Round #654 (Div. 2) (0) | 2020.07.03 |
| Codeforces Round #652 (Div. 2) (0) | 2020.06.24 |
| Codeforces Round #651 (Div. 2) (0) | 2020.06.21 |
