티스토리 뷰
결과: 78점을 받으면서 37등을 했다. A번을 틀리고 시작한 것과 C번을 푸는데 너무 오래 걸린 것이 아쉽다.
풀이:
A번: Arithmetic Square: 중앙이 비어있는 3*3 배열 중앙에 수를 넣어서 가로, 세로, 대각선 방향으로 등차수열을 최대한 많이 만드는 문제이다. 중앙에 모든 수를 넣어 보면 서브태스크 1을 풀 수 있지만, 2에서는 시간초과가 난다. 2를 풀기 위해서는, map에다가 등차수열을 만들 수 있는 수와 그 때 만들어지는 등차수열의 개수를 저장한 뒤, 만들어지는 개수 중 최댓값에다가 가장자리 4개 중 등차수열을 만드는 개수를 더해주면 된다. 등차수열을 만들 수 있는 중앙 수는 총 4개이고, 중앙을 지나는 선들을 보며 찾을 수 있다. x가 반정수가 되는 경우를 처리하지 않아서 1틀 후 AC
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
int T,N, M;
cin >> T;
int xc = 0;
while(T--)
{
xc++;
int a, b, c, d, e, f, g, h;
cin >> a >> b >> c >> d >> e >> f >> g >> h;
map<int, int>x;
if((a+h)%2==0)
x[a + h]++;
if ((b + g) % 2 == 0)
x[b + g]++;
if ((c + f) % 2 == 0)
x[c + f]++;
if ((d + e) % 2 == 0)
x[d + e]++;
int an = 0;
an += (a + c) == b*2;
an += (f + h) == g * 2;
an += (a + f) == d * 2;
an += (c + h) == e * 2;
cout << "Case #"<<xc<<": "<<an+max({ x[a + h],x[b + g],x[c + f],x[d + e] }) << '\n';
}
}B번: 구간을 자를 때의 성질을 관찰해보자. L~R 구간이 하나 있을 때는, L+1~R-1 지점을 자를 때 구간 개수는 1개 증가하고, 나머지 지점에서는 변하지 않는다. 구간이 여러 개 있을 때는 각 구간을 자를 때 증가하는 구간 개수를 더해주면 된다. 이는 구간 개수가 증가하기 시작하는 지점과 원래대로 돌아가기 시작하는 지점을 저장하면 찾을 수 있다. 이러면 문제는 자를 때 증가하는 구간 개수 중에서 가장 큰 C개를 찾는 문제로 변한다. 이를 그냥 계산하면 시간 초과가 나지만, 가능한 수가 0~N까지라는 성질을 이용할 수 있다. 가능한 수들과 그 수들의 개수를 저장하는 배열을 만들고 이를 내림차순으로 탐색하며 뽑으면 O(NlogN)에 가능하다.
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define int long long
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T,N, M;
cin >> T;
int xc = 0;
while(T--)
{
xc++;
cin >> N>>M;
vector<pair<int, int>>x;
int i;
for (i = 0; i < N; i++)
{
int a, b;
cin >> a >> b;
x.push_back({ a + 1,1 });
x.push_back({ b,-1 });
}
sort(x.begin(), x.end());
vector<pair<int, int>>cus;
int c = 0;
for (i = 0; i < 2 * N; i++)
{
c += x[i].second;
if (i + 1 < 2 * N)
{
cus.push_back({ -c,x[i+1].first - x[i].first });
}
}
sort(cus.begin(), cus.end());
int ans = N;
for (i = 0; i < cus.size(); i++)
{
if (cus[i].second <= M)
{
ans -= cus[i].second * cus[i].first;
M -= cus[i].second;
}
else
{
ans -= M * cus[i].first;
break;
}
}
cout << "Case #"<<xc<<": "<<ans<<'\n';
}
}C번: 맨 처음에는 다룰 범위가 크고, 구간의 개수가 상대적으로 작은 것을 봐서 세그먼트 트리를 이용해 가장 가까운 점을 찾는 풀이를 생각했는데, 상태 전이가 복잡해지고 생각이 제대로 되지 않았다. 30분 정도 고민한 뒤에, set으로 구간을 관리하는 더 간단해 보이는 풀이를 생각해냈다. set에다가는 우선 문제 구간들을 넣은 뒤, lower bound를 이용해서 난이도와 가까운 구간 몇 개를 탐색한 뒤 가장 가까운 문제를 찾고, 그 문제를 지운 뒤 구간을 2개로 나누면 된다. 시간 복잡도는 ((N+M)logN)으로 통과된다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define int long long
set<pair<int, int>>x;
signed main()
{
int T;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
int sc = 0;
while (T--)
{
x.clear();
sc++;
int N, M;
cin >> N >> M;
int i;
for (i = 0; i < N; i++)
{
int a, b;
cin >> a >> b;
x.insert({ a,b });
}
cout << "Case #" << sc << ": ";
for (i = 0; i < M; i++)
{
int a;
cin >> a;
auto p = x.lower_bound({ a,0 });
pair<int, int>an = { 1LL << 60,0 };
if (p != x.end())
{
an = min(an, { p->first - a,p->first });
}
if (p != x.begin())
{
p--;
an = min(an, { max(0LL,a-p->second),min(a,p->second)});
}
cout << an.second << ' ';
auto p2 = x.lower_bound({ an.second+1,0 });
p2--;
int st = p2->first;
int en = p2->second;
x.erase(p2);
if (st != an.second)
x.insert({ st,an.second - 1 });
if (en != an.second)
x.insert({ an.second + 1,en });
}
cout << '\n';
}
}D번: 서브태스크 1번만 풀었다. 1번은 S=1~4를 관리하는 4개의 세그먼트 트리를 만들고 갱신될 때마다 가능한 모든 S에 대한 값 4개를 갱신해주면서 풀었다. 시간 복잡도는 A[i]N(S^2)logN으로 통과된다.
대회가 끝난 뒤 서브태스크 2 풀이를 봤는데, 내가 모르는 정수론 정리를 사용했다. 정수론도 공부해야 하는데, 어떻게 공부해야 할 지 잘 모르겠다.