A - Matrix Game
Problem - A - Codeforces
codeforces.com
\(n \times m\) 크기의 격자가 있다.
두 사람이 이 격자에 번갈아가며 말을 놓으려고 하는데,
말을 놓을 때는 같은 행이나 열에 말이 없어야 한다. 말을 더이상 놓지 못하는 사람이 진다.
초기 격자의 상태가 주어졌을 때, 누가 이기는지 알아내야 한다.
현재 말이 놓여있지 않은 행의 개수를 \(r\), 열의 개수를 \(c\)라고 하자.
그러면 말을 \(min(r,c)\)번 놓을 수 있으므로, 이 값이 홀수면 전자가, 짝수면 후자가 승리한다.
|
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
|
#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 a[51][51];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n >> m;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
cin >> a[i][j];
int row = 0, col = 0;
for (int i = 0; i < n; i++)
{
bool flag = true;
for (int j = 0; j < m; j++) if (a[i][j]) flag = false;
if (flag) row++;
}
for (int i = 0; i < m; i++)
{
bool flag = true;
for (int j = 0; j < n; j++) if (a[j][i]) flag = false;
if (flag) col++;
}
int res = min(row, col);
if (res % 2) cout << "Ashish\n";
else cout << "Vivek\n";
}
}
|
B - Trouble Sort
Problem - B - Codeforces
codeforces.com
\(n\)개의 원소로 이루어진 배열 \(a\)가 있다.
배열의 원소 각각은 타입 \(0\)또는 \(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
|
#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[501];
int b[501];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n;
bool isExist[2] = { 0,0 };
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i], isExist[b[i]] = 1;
if (isExist[0] && isExist[1]) cout << "Yes\n";
else
{
bool ans = true;
for (int i = 1; i < n; i++)
{
if (a[i - 1] > a[i]) ans = false;
}
if (ans) cout << "Yes\n";
else cout << "No\n";
}
}
}
|
C - Rotation Matching
Problem - C - Codeforces
codeforces.com
\(n\)개의 원소를 가지는 순열 \(a\)와 \(b\)가 주어진다.
\(a\)와 \(b\)중 하나를 골라 원소를 모두 시계방향으로 회전하는 연산을 원하는만큼 할 수 있을 때,
\(1 \le i \le n\)에 대해 \(a_i = b_i\)를 만족하는 \(i\)의 개수의 최대값을 알아내야 한다.
\(1 \le x \le n\)사이의 모든 \(x\)에 대해, \(a\)에서의 인덱스 \(idx_a\)와 \(b\)에서의 인덱스 \(idx_b\)를 구해놓자.
이들 각각에 대해 \(d_x = (idx_a - idx_b) \bmod n\)를 구하면, 가장 많은 \(d_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
|
#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[200001];
int idx[200001];
int b[200001];
map <int, int> mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i], idx[a[i]] = i;
for (int i = 0; i < n; i++)
{
cin >> b[i];
int sub = i - idx[b[i]];
if (sub < 0) sub += n;
mp[sub]++;
}
int ans = 0;
for (auto it : mp) ans = max(ans, it.second);
cout << ans;
}
|
D - Solve The Maze
Problem - D - Codeforces
codeforces.com
\(n \times m\)크기의 미로가 주어진다.
이 미로의 가장 오른쪽 아래 칸으로 가면 미로를 탈출할 수 있다.
미로에는 좋은 사람과 나쁜 사람이 있다.
미로의 빈 공간에 원하는 만큼 벽을 설치해서 나쁜 사람은 미로를 탈출하지 못하고, 좋은 사람은 미로를 탈출할 수 있도록 만들 수 있는지 알아내야 한다.
나쁜 사람의 위치 상하좌우의 빈 공간에 벽을 설치해서 아예 움직이지 못하게 가두자.
그렇게 새로 만들어진 미로에 대해 좋은 사람이 미로를 탈출할 수 없거나, 나쁜 사람을 가둘 수 없으면 불가능하고, 그렇지 않다면 가능하다.
|
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
|
#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 maze[51];
int cache[51][51];
void DFS(int i, int j)
{
if (maze[i][j] == '#') return;
cache[i][j] = 1;
for (int k = 0; k < 4; k++)
{
int x = i + "1210"[k] - '1';
int y = j + "2101"[k] - '1';
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (cache[x][y]) continue;
if (maze[x][y] == '#') continue;
DFS(x, y);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> maze[i];
bool ans = true;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
{
if (maze[i][j] == 'B')
{
for (int k = 0; k < 4; k++)
{
int x = i + "1210"[k] - '1';
int y = j + "2101"[k] - '1';
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (maze[x][y] == 'G') ans = false;
if (maze[x][y] == '.') maze[x][y] = '#';
}
}
}
memset(cache, 0, sizeof cache);
DFS(n - 1, m - 1);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
{
if (maze[i][j] == 'G' && !cache[i][j]) ans = false;
}
if (ans) cout << "Yes\n";
else cout << "No\n";
}
}
|
E - Maximum Subsequence Value
Problem - E - Codeforces
codeforces.com
\(n\)길이의 배열 \(a\)가 주어진다.
이 배열에서 임의의 \(k\)길이의 부분수열을 고르자.
이 부분수열의 가치는 수열의 원소들을 이진수로 나타냈을 때, \(\max (1, k-2)\)개 이상의 원소가 \(i\)번째 비트가 1인 \(2^i\)의 합이다.
부분수열의 가치의 최대값을 알아내야 한다.
배열에서 임의의 원소 3개를 골라서 나온 부분 수열이 있다고 가정해보자.
이 원소를 모두 bitwise OR해서 나온 가치 \(x\)가 있을 때, 여기에서 원소를 어떻게 추가하더라도 가치가 더 커질 수는 없다.
가치가 커지기 위해서는 이 3개의 원소에 모두 존재하지 않는 비트가 추가되어야 하는데, 3개를 제외한 나머지 원소가 모두 해당 비트를 가지고 있다고 하더라도 \(k-3\)개이기 때문에 가치에 포함될 수 없다.
따라서 배열에서 서로 다른 3가지의 원소를 bitwise OR해서 나온 값중 최대값이 답이다.
\(n\)이 3보다 작을 때 예외도 적당히 잘 처리해주자.
|
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
|
#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;
ll a[501];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
ll ans = 0;
if (n < 3)
{
for (int i = 0; i < n; i++) ans |= a[i];
cout << ans;
return 0;
}
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) for (int k = j + 1; k < n; k++)
{
ll res = a[i] | a[j] | a[k];
ans = max(ans, res);
}
cout << ans;
}
|
F - Swaps Again
Problem - F - Codeforces
codeforces.com
\(n\)길이의 배열 \(a, b\)가 있다.
\(a\)에 다음과 같은 연산을 해서 \(b\)로 변환될 수 있는지 알아내야 한다.
: \(1 \le k \le \lfloor \frac n2 \rfloor\)인 \(k\)를 골라 배열의 앞 \(k\)개 원소와 뒤 \(k\)개 원소를 서로 바꾼다.
먼저, \(a\)와 \(b\)를 구성하고 있는 수가 아예 다르거나, 길이가 홀수인데 바뀌지 않는 정중앙 원소가 다르다면 무조건 불가능하다.
\(a\)에 위 연산을 하고 난 뒤 \(a_i\)의 바뀐 인덱스를 \(j\)라고 하자.
그러면 \(a_{n-1-i}\)은 무조건 \(a_{n-1-j}\)로 이동한다는 사실을 알 수 있다. (거울 상)
따라서 (\(1 \le i \le \lfloor \frac n2 \rfloor\))에 대해,
\(a_i\) = \(b_j\)이면서 \(a_{n-1-i} = b_{n-1-j}\)인 쌍을 모두 찾을 수 있다면 가능하고, 그렇지 않다면 불가능하다.
나이브하게 \(O(n^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
|
#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[501];
int b[501];
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];
for (int i = 0; i < n; i++) cin >> b[i];
int ta[501], tb[501];
memcpy(ta, a, sizeof a);
memcpy(tb, b, sizeof b);
sort(ta, ta + n);
sort(tb, tb + n);
bool ans = true;
for (int i = 0; i < n; i++)
{
if (ta[i] != tb[i]) ans = false;
}
if (n % 2 && a[n / 2] != b[n / 2]) ans = false;
bool cache[501] = { 0, };
for (int i = 0; i < n / 2; i++)
{
bool flag = false;
for (int j = 0; j < n; j++)
{
if (n % 2 && j == n / 2) continue;
if (cache[j]) continue;
if (a[i] == b[j] && a[n - 1 - i] == b[n - 1 - j])
{
cache[j] = cache[n - 1 - j] = 1;
flag = true;
break;
}
}
if (!flag) ans = false;
}
if (ans) cout << "Yes\n";
else cout << "No\n";
}
}
|
G - Secure Password
Problem - G - Codeforces
codeforces.com
\(n\)길이의 비밀번호 \(P\)가 있다.
비밀번호의 각 자리 \(P_i\)는 숨겨진 배열 \(A\)를 이용해 정해지는데,
\(P_i\)는 \(A_i\)를 제외한 모든 \(A\)의 원소의 값을 bitwise OR한 값이다.
\(A\)의 인덱스들을 입력으로 주면 해당하는 값들을 모두 bitwise OR한 값을 출력해주는 쿼리를 13번 사용할 수 있을 때,
원래 비밀번호를 알아내야 한다.
각 비밀번호를 13개의 쿼리만으로 구분하기 위해서는 하나의 비밀번호를 알아내기 위해 여러개의 쿼리를 이용할 필요가 있음을 알 수 있다.
\(_{13}C_6 = 1716\) 이므로 비밀번호 하나당 6개의 쿼리를 참조한다면, 서로 다른 1000가지 경우는 커버가능한 범위임을 알 수 있다.
우선 13개중 6개를 고르는 모든 경우의 수를 만들자. 비트연산을 이용하면 편리하다.
그리고 각각의 비밀번호에 한 경우를 배정하면서, 6개를 제외한 쿼리에는 해당하는 비밀번호의 인덱스가 포함되도록 하면 된다.
예를 들어, \(P_1\)에 쿼리 \(\{1,2,3,4,5,6\}\)을 배정했다고 하자.
각 쿼리의 결과 값을 \(res_i\)라고 하면, \(P_1\)은 \((res_1 | res_2 | \cdots | res_6)\)으로 구할 수 있도록 할 것이다.
그리고 \(7,8 \cdots, 13\)번째 쿼리에는 \(A_1\)이 bitwise OR에 포함되도록 하면 다른 비밀번호를 구할 때 \(A_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
|
#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 bt[1000];
vector <int> query[13];
ll res[13];
ll getVal(vector <int> v)
{
if (v.empty()) return 0;
cout << "? " << v.size();
for (int i : v) cout << ' ' << i;
cout << endl;
ll res; cin >> res;
return res;
}
int main()
{
cin >> n;
int cnt = 0;
for (int i = 0; i < (1 << 13) && cnt < n; i++)
{
int bc = 0;
for (int j = 0; j < 13; j++)
if (i & (1 << j)) bc++;
if (bc != 6) continue;
bt[cnt++] = i;
for (int j = 0; j < 13; j++)
if (!(i & (1 << j))) query[j].push_back(cnt);
}
for (int i = 0; i < 13; i++) res[i] = getVal(query[i]);
cout << "!";
for (int i = 0; i < n; i++)
{
ll ans = 0;
for (int j = 0; j < 13; j++)
if (bt[i] & (1 << j)) ans |= res[j];
cout << ' ' << ans;
}
cout << endl;
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Global Round 8 (3) | 2020.06.19 |
|---|---|
| Codeforces Round #650 (Div. 3) (0) | 2020.06.17 |
| Codeforces Round #647 (Div. 1, Div.2) - Thanks, Algo Muse! (0) | 2020.06.05 |
| Codeforces Round #646 (Div. 2) (0) | 2020.06.01 |
| Educational Codeforces Round 88 (0) | 2020.05.30 |
