Generic Queries
문제 설명
길이가 N인 수열 A가 주어지고, Q개의 쿼리에 답을 하면 된다.
각 쿼리는 x, y(1 <= x, y <= N)으로 들어오고, Ax ~ Ay 사이(포함)의
값들을 XOR한 값들을 찾는 문제이다.해결
1부터 N까지의 의 구간합을 구해놓고, d[y] ^ d[x - 1]를 하면
(x, y) 사이의 XOR 값들을 구할 수 있다.
- XOR 성질
- A^B = Y
- Y^B = A
- Y^A = B코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000001];
int d[1000001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
d[i] = d[i - 1] ^ a[i];
}
int ans = 0;
while (q--) {
int x, y;
cin >> x >> y;
ans = ans ^ d[y] ^ d[x - 1];
}
cout << ans << '\n';
}Ezreal 여눈부터 가네 ㅈㅈ
문제 설명
그래서 0으로 시작하지 않고 1과 5로만 구성된 자리 양의 정수 중에서,
15의 배수가 몇 개인지 구하는 문제해결
15의 배수로 나누어 떨어지기 위해서는 각 자리수의 합이 3의 배수이고,
마지막 자리수가 5여야하는 성질을 가지고 있다.
따라서 이 성질을 이용해 5를 1번 사용하는 경우부터 N번 사용하는 경우까지 탐색을
진행하면서 5의 개수와 1의 개수의 합이 3의 배수인지 아닌지 확인할 한 다음,
맞다면 (N - 1)개의 자리에 대해(맨 마지막은 5 고정)
(N - 1)개 중에서 (5의 개수 - 1)개를 뽑는 경우의 수를 구하면 된다. 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
ll d[2001][2001];
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
if (n <= 1) {
cout << 0 << '\n';
return 0;
}
if (n <= 3) {
cout << 1 << '\n';
return 0;
}
for (int i = 0; i <= n; i++) {
d[i][1] = i;
d[i][i] = d[i][0] = 1;
for (int j = 2; j < i; j++) {
d[i][j] = d[i - 1][j - 1] + d[i - 1][j];
d[i][j] %= mod;
}
}
ll ans = 0;
// 5의 개수
for (int i = 1; i <= n; i++) {
int r = n - i;
if ((i * 5 + r) % 3 != 0) continue;
ans += (d[n - 1][i - 1]);
ans %= mod;
}
cout << ans << '\n';
}돌 그룹
문제 설명
3개의 그룹에 돌이 A, B, C개 들어있고, 다음과 같은 연산을 할 수 있다.
크기가 같지 않은 두 그룹을 고르고, 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다.
그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
A, B, C의 그룹에 있는 돌의 개수를 같게 만들 수 있는지 확인하는 문제해결
돌 개수가 최대 500개이다. 따라서 최대로 하더라도 한 개의 그룹에는 1500개(정확히는 잘...)
가 될 수 있다. 따라서 메모이제이션를 사용하면 쉽게 해결할 수 있다.
dp[i][j] = 현재 2개의 그룹에 돌이 i, j만큼 들어 있을 때 가능하면 1, 그렇지 않으면 0
그러면 이제, 각 연산을 수행하면서 메모이제이션을 사용하면 된다.코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[1501][1501];
int go(int x, int y, int z) {
if (x == y && x == z) {
return 1;
}
if (x > y) swap(x, y);
if (x > z) swap(x, z);
if (y > z) swap(y, z);
if (d[x][y] != -1) return d[x][y];
d[x][y] = 0;
if (x > y) {
d[x][y] = max(d[x][y], go(x - y, y + y, z));
} else if (x < y) {
d[x][y] = max(d[x][y], go(x + x, y - x, z));
}
if (x > z) {
d[x][y] = max(d[x][y], go(x - y, y, z + z));
} else if (x < z) {
d[x][y] = max(d[x][y], go(x + x, y, z - x));
}
if (y > z) {
d[x][y] = max(d[x][y], go(x, y - z, z + z));
} else if (y < z) {
d[x][y] = max(d[x][y], go(x, y + y, z - y));
}
return d[x][y];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int x, y, z;
cin >> x >> y >> z;
memset(d, -1, sizeof(d));
if ((x + y + z) % 3 || !go(x, y, z)) {
cout << 0 << '\n';
return 0;
}
cout << 1 << '\n';
}문제 설명
이차원 배열로, 각 친구들의 관계가 주어진다. 그리고 Q개의 질문이 들어오는데,
"a번 사용자, b번 사용자와 공통적으로 친구 관계인 사용자의 수" 를 구하는 문제이다. 해결
N이 최대 2000이므로, 비트마스킹으로는 안될 거 같지만, 사실 집합으로 관리하면 해결할 수 있다.
d[x][y] = x번째 사람이 (y * 20 ~ y * 20 + 20)까지의 사람들과의 관계를 비트 마스킹
그러면 각 쿼리에 대해서 a번 사용자와 b번 사용자가 공통적으로
친구 관계인 경우는 최대 100개의 그룹이 만들어 질 수 있다
시간복잡도는 O(500000 * 100)로 적당하다.코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[3000001];
int a[2001][121];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int k = 0, cnt = 0;
for (int j = 0; j < n; j++) {
if (s[j] == '1') {
a[i][cnt] += (1 << k);
}
k += 1;
if (k == 21) {
k = 0;
cnt += 1;
}
}
}
for (int i = 1; i < (1 << 21); i++) {
int cnt = 0;
for (int j = 0; j <= 20; j++) {
if (i & (1 << j)) cnt += 1;
}
d[i] = cnt;
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
x -= 1;
y -= 1;
int ans = 0;
for (int i = 0; i <= 101; i++) {
int cnt = a[x][i] & a[y][i];
ans += d[cnt];
}
cout << ans << '\n';
}
}
Load Balancing (Silver)
문제 설명
2차원 좌표에 N마리의 소가 (Ax, Ay) 위치(홀수)에 위치하고, 울타리를 (x, y)에 위치(짝수) 시켰을 때
4분면으로 나눠지게 된다. 그 때 각 4분면에 존재하는 소들의 최대값을 최소로 만드는 문제 해결
N이 1000이라서 완전탐색으로 접근해 볼 수 있다. 먼저, 소들의 좌표는 최대 백만이므로,
좌표 압축을 먼저 하고, 그 다음 가능한 모든 울타리를 만들어보고, 그 때 4분면에 존재하는
소들의 수를 구하면 된다. 소들의 수를 구하는 방법은 부분합으로 구할 수 있다.코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int>> v;
int d[5001][5001];
int a[5001][5001];
int n;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
vector<int> s;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
s.push_back(x);
s.push_back(y);
v.push_back({x, y});
}
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
for (int i = 0; i < n; i++) {
v[i].first = ((lower_bound(s.begin(), s.end(), v[i].first) - s.begin()) + 1) * 2;
v[i].second = ((lower_bound(s.begin(), s.end(), v[i].second) - s.begin()) + 1) * 2;
a[v[i].first][v[i].second] += 1;
}
for (int i = 1; i <= 4000; i++) {
for (int j = 1; j <= 4000; j++) {
d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + a[i][j];
}
}
int ans = 1e9;
for (int i = 1; i <= 4000; i += 2) {
for (int j = 1; j <= 4000; j += 2) {
int cnt = d[i][j];
cnt = max(cnt, d[4000][4000] - d[4000][j] - d[i][4000] + d[i][j]);
cnt = max(cnt, d[4000][j] - d[i][j]);
cnt = max(cnt, d[i][4000] - d[i][j]);
ans = min(ans, cnt);
}
}
cout << ans << '\n';
}연결
문제 설명
크기가 N×M인 비어있는 회로판에서 두 점 A1과 A2, 그리고 B1와 B2를 전선을 이용해서 이으려고 한다.
그 때 전선의 길이의 최솟값을 구하는 문제해결
N, M이 100이하여서 이차원 배열을 통해 각 점의 위치를 저장한다.
점 A1에서 점 A2까지의 최단 경로를 BFS를 통해 구해준다. 그리고 그 경로를 기억하고,
점 B1에서 B2로 가는 최단 경로를 구하는데, A1 - A2까지의 경로는 못가도록 한다.
또 반대로도 마찬가지로 동일하게 진행한다.코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool c[101][101];
pair<int, int> how[101][101];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m;
struct A {
int x, y;
} a[4];
int go(int x, int y, int tx, int ty) {
memset(c, false, sizeof(c));
queue<pair<A, int>> q;
q.push({{a[x].x, a[x].y}, 0});
c[a[x].x][a[x].y] = true;
how[a[x].x][a[x].y] = {-1, -1};
while (!q.empty()) {
A tmp = q.front().first;
int dist = q.front().second;
if (tmp.x == a[y].x && tmp.y == a[y].y) {
return dist;
}
q.pop();
for (int i = 0; i < 4; i++) {
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
if (nx < 0 || ny < 0 || nx > n || ny > m || how[nx][ny].first != 0 || c[nx][ny]) continue;
if (nx == a[tx].x && ny == a[tx].y) continue;
if (nx == a[ty].x && ny == a[ty].y) continue;
c[nx][ny] = true;
how[nx][ny] = {tmp.x, tmp.y};
q.push({{nx, ny}, dist + 1});
}
}
return -1;
}
int go2(int xx, int yy, int nxx, int nyy) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
how[i][j] = {0, 0};
}
}
int cnt = go(xx, yy, nxx, nyy);
if (cnt == -1) return -1;
vector<pair<int, int>> v;
int x = a[yy].x;
int y = a[yy].y;
while (x != -1) {
v.push_back({x, y});
int nx = how[x][y].first;
int ny = how[x][y].second;
x = nx;
y = ny;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
how[i][j] = {0, 0};
}
}
for (int i = 0; i < v.size(); i++) {
how[v[i].first][v[i].second] = {1, 1};
}
int cnt2 = go(nxx, nyy, xx, yy);
if (cnt2 == -1) return -1;
return cnt + cnt2;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < 4; i++) {
cin >> a[i].x >> a[i].y;
}
int ans = -1;
int cnt = go2(0, 1, 2, 3);
if (cnt != -1) ans = cnt;
cnt = go2(2, 3, 0, 1);
if (cnt != -1) {
if (ans == -1)
ans = cnt;
else
ans = min(ans, cnt);
}
if (ans == -1) {
cout << "IMPOSSIBLE" << '\n';
} else
cout << ans << '\n';
}Kaisar - 생존
문제 설명
트리가 주어지고 모든 정점의 LCA를 구한 다음, 정렬한 다음 홀수번째 합과 짝수번째의 합을
구하는 문제해결
단계적으로 해결해야 한다.
1. 자신을 포함하여 자식의 개수 (위상정렬)
2. 루트에서부터 시작하여 자식들을 탐색하면서 자식들 중에서 2개를 선택했을 경우, 그 때 루트가
LCA가 되는 경우는 그 두개의 곱이다.
그러면 이제 자식이 대충 50000이라 하면, 하나하나 해주면 시간이 굉장히 오래걸린다.
하지만 구간합을 이용하면 O(N)만에 해결할 수 있다.
자식들을 일렬로 놓았을 때, 자식 [1,2,3,4,5]라고 가정하자. 그러면 아래와 같은 식이 성립한다.
1 * 2 + 1 * 3 + 1 * 4 + 1 * 5 == 1 * (2 + 3 + 4 + 5)
그러면 이제, 각 정점이 LCA가 되는 개수를 구했고, 마지막으로 홀수번째의 값들의 합 또는
짝수번째 값들의 합을 더하면 된다.
홀수번째 값들의 합은 홀수번째일 경우, (개수 + 1) / 2
짝수번째일 경우, (개수) / 2 를 더해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[200001], a[200001], ind[200001];
ll ans[200001];
vector<int> v[200001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
int root = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 0) root = i;
v[a[i]].push_back(i);
ind[a[i]] += 1;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (ind[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int x = q.front();
q.pop();
d[x] += 1;
d[a[x]] += d[x];
ind[a[x]] -= 1;
if (ind[a[x]] == 0) {
q.push(a[x]);
}
}
q.push(root);
while (!q.empty()) {
int x = q.front();
q.pop();
ans[x] += (ll)(d[x] - (ll)1);
if (v[x].empty()) {
ans[x] *= (ll)2;
ans[x] += (ll)1;
continue;
}
ll sum = 0, cnt = 0;
for (int i = 0; i < v[x].size(); i++) {
sum += (ll)d[v[x][i]];
q.push(v[x][i]);
}
for (int i = 0; i < v[x].size(); i++) {
cnt += d[v[x][i]];
ans[x] += (ll)d[v[x][i]] * (sum - cnt);
}
ans[x] *= (ll)2;
ans[x] += (ll)1;
}
ll sum = 0, cnt = 0;
bool f = false;
for (int i = 1; i <= n; i++) {
sum += (ll)i * ans[i];
if (!f) {
cnt += (ll)i * (ll)((ans[i] + (ll)1) / (ll)2);
} else {
cnt += (ll)i * (ll)(ans[i] / (ll)2);
}
f = !f;
}
cout << sum - cnt << ' ' << cnt << '\n';
}
Wow