티스토리 뷰
오랜만에 부계 jjang36524로 나가 5솔을 했고, 75점이 올랐다.
A번: 가장 먼저 찾을 수 있는 성질은 연산을 했을 때 abs(a-b)는 짝수라는 것이다. 1번 연산은 a-b를 변화시키지 않고, 2,3번 연산은 a-b를 2k만큼 변화시키기 때문이다. 따라서, a-b가 홀수이면 답은 -1이다. 그 외의 경우는 1번 연산 하나와 2번 혹은 3번 연산 하나만으로 가능한데, a==b인 경우는 1번 연산 하나만 필요하고, a==b==0이면 아무 연산도 필요하지 않다. 이를 구현해주면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int T;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--)
{
int a, b;
cin >> a >> b;
if (a > b)
swap(a, b);
if ((b - a) % 2)
{
cout << -1 << '\n';
}
else
{
cout << (b&&b) + (a != b) << '\n';
}
}
}B번: a를 모두 0과 1로 바꿔주고 시작하자. 0의 개수와 1의 개수의 차가 2 이상이면 불가능하다는 것을 증명할 수 있다.
0의 개수와 1의 개수가 같다면, 010101... 순서와 101010... 순서가 가능하고, 1 차이가 난다면 더 많은 것부터 시작한 뒤 개수가 같을 때처럼 넣어주는 경우 한 가지만 가능하다. 어떤 순서가 있을 때의 정답은 (abs(수열에서 i번째 0 위치-만들어야 하는 i번째 0 위치)의 합+abs(수열에서 i번째 1 위치-만들어야 하는 i번째 1 위치)의 합)/2가 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
signed main()
{
int T;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--)
{
int N;
cin >> N;
vector<int>x;
vector<int>y;
int i;
for (i = 0; i < N; i++)
{
int a;
cin >> a;
if (a % 2)
x.push_back(i);
else
y.push_back(i);
}
if (x.size() > y.size())
swap(x, y);
if (x.size() + 1 < y.size())
{
cout << -1 << '\n';
}
else
{
long long ans = 1LL<<60;
long long cur = 0;
for (i = 0; i < x.size(); i++)
{
cur += abs(x[i] - (i * 2+1));
}
for (i = 0; i < y.size(); i++)
{
cur += abs(y[i] - (i * 2));
}
ans = cur/2;
if (x.size() == y.size())
{
swap(x, y);
cur = 0;
for (i = 0; i < x.size(); i++)
{
cur += abs(x[i] - (i * 2 + 1));
}
for (i = 0; i < y.size(); i++)
{
cur += abs(y[i] - (i * 2));
}
ans = min(ans,cur/2);
}
cout << ans << '\n';
}
}
}C번: 괄호열을 (가 1, )가 -1인 수열로 바꾼 뒤 이 수열의 prefix sum을 저장해두자. 괄호 문자열은 prefix sum이 k인 곳 바로 뒤에서 시작해서 k인 곳에서 끝나는데, 중간에 prefix sum이 k보다 작아지지 않아야 한다. 이를 이용하면 문제를 풀 수 있다. 특정 높이에서 시작하는 순열의 개수를 구하려면 prefix sum을 돌아보면서 k 이하다가 k 초과로 올라가는 곳이 있으면 카운터를 1 올리고, k 초과에서 k 이하로 내려가면 카운터를 정답에 더하고, 현재 prefix sum이 k 미만이라면 카운터를 초기화해주며 구할 수 있다. 처리해줘야 할 높이는 변곡점의 prefix sum과 변곡점의 prefix sum+1뿐으로, 나머지는 바로 밑에 있는 처리해줘야 하는 높이와 정답이 같다.
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
vector<int>psum;
signed main()
{
int N;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
psum.push_back(0);
int i;
vector<int>pl{ 0,1 };
for (i = 0; i < N; i++)
{
int a;
cin >> a;
psum.push_back(psum.back() + a * (i % 2?-1 : 1));
pl.push_back(psum.back());
pl.push_back(psum.back() + 1);
}
sort(pl.begin(), pl.end());
int ans = 0;
for (i = 0; i < pl.size()-1; i++)
{
int an = 0;
int cu = 0;
int j;
for (j = 1; j < psum.size(); j++)
{
if (psum[j - 1] <= pl[i] && psum[j] > pl[i])
{
cu++;
}
if (psum[j] <= pl[i] && psum[j-1] > pl[i])
{
an += cu;
}
if (psum[j] < pl[i])
{
cu = 0;
}
}
ans += an*(pl[i+1]-pl[i]);
}
cout << ans;
}D번: 이 문제에서 가장 중요한 관찰은 i and j + i or j는 i+j라는 것이다. 이를 이용하면 a[1]+a[2], a[2]+a[3],a[3]+a[1]을 찾아서 첫 3개 원소를 구하고, 나머지는 a[1]+a[i]를 사용해서 구할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
vector<int>psum;
int res[10100];
signed main()
{
int N,K;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N>>K;
int i;
int arr[5][5];
for (i = 1; i < 3; i++)
{
int j;
for (j = i + 1; j <= 3; j++)
{
arr[i][j] = 0;
cout << "and " << i << ' ' << j << '\n';
cout.flush();
int a;
cin >> a;
arr[i][j] += a;
cout << "or " << i << ' ' << j << '\n';
cout.flush();
cin >> a;
arr[i][j] += a;
}
}
int ans = (arr[1][2] + arr[2][3] + arr[1][3]) / 2;
res[1] = ans - arr[2][3];
res[2] = ans - arr[1][3];
res[3] = ans - arr[1][2];
for (i = 4; i <= N; i++)
{
cout << "and " << i << ' ' << 1 << '\n';
cout.flush();
int a;
cin >> a;
res[i] += a;
cout << "or " << i << ' ' << 1 << '\n';
cout.flush();
cin >> a;
res[i] += a;
res[i] -= res[1];
}
sort(res + 1, res + N + 1);
cout << "finish " << res[K] << '\n';
cout.flush();
}E번:a[i]-b[i]의 prefix sum을 저장해두면 이 값을 기반으로 여러 성질을 찾을 수 있다. 우선 안 되는 경우는 l-1까지의 부분합이 r까지의 부분합과 다른 경우, l-1~r까지의 부분합의 최솟값이 r까지의 부분합과 다른 경우이다. 나머지 경우에는 l-1~r까지의 부분합의 최댓값-r까지의 부분합이 정답이고, 이는 세그먼트 트리로 구할 수 있다.
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
class stree
{
private:
int tree[1 << 18];
int N, treeN;
public:
stree()
{
memset(tree, 0, sizeof(tree));
}
int gettreeN()
{
return treeN;
}
void setNtreeN(int newN)
{
N = newN;
for (treeN = 1; treeN < N; treeN *= 2);
}
void set(vector<int>val, int op)
{
int i;
for (i = 0; i < val.size(); i++)
{
tree[i + treeN] = val[i];
}
for (i = treeN - 1; i; i--)
{
if (op)
{
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
else
{
tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}
}
}
int res(int qstart, int qend, int start, int end, int ind, int op)
{
if (start > qend || qstart > end)
return op ? (-(1LL<<60)) : 1LL << 60;
if (start >= qstart && end <= qend)
return tree[ind];
if (op)
{
return max(res(qstart, qend, start, (start + end) / 2, ind * 2, op), res(qstart, qend, (start + end) / 2 + 1, end, ind * 2 + 1, op));
}
else
{
return min(res(qstart, qend, start, (start + end) / 2, ind * 2, op), res(qstart, qend, (start + end) / 2 + 1, end, ind * 2 + 1, op));
}
}
}x,y;
int arr[100100];
signed main()
{
int N, Q;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> Q;
int i;
for (i = 0; i < N; i++)
{
cin >> arr[i];
}
x.setNtreeN(N + 1);
y.setNtreeN(N + 1);
vector<int>psum;
psum.push_back(0);
for (i = 0; i < N; i++)
{
int a;
cin >> a;
psum.push_back(psum.back() - arr[i] + a);
}
x.set(psum,1);
y.set(psum, 0);
int treeN = x.gettreeN();
while (Q--)
{
int a, b;
cin >> a >> b;
a--;
if (psum[a] != psum[b])
{
cout << -1 << '\n';
}
else
{
int ma = x.res(a, b, 0, treeN - 1, 1, 1);
int mi = y.res(a, b, 0, treeN - 1, 1, 0);
if (mi < psum[a])
cout << -1 << '\n';
else
cout << ma - psum[a] << '\n';
}
}
}