SCPC 2023 1차 예선 후기
7/28 15:00 ~ 7/29 15:00
간만의 포스팅입니다. 매년 나가보는 SCPC.
이번에는 며칠 밤을 샌 채로 대회를 쳐서 대충 풀겠다고 마음먹었다가 제출횟수가 나락으로 가버렸습니다.
난이도는 5번은 안풀었지만 대강 1<2<4=5<3쯤 될 것 같아요
1. 증강현실 배달 안경
문제 요약
주어진 N, A, B에서 A*p + B*q = N에 대해 p+q를 최대화 할 때의 값은?
풀이
확장 유클리드를 사용해도 괜찮고, 작은 그룹이 더 많아야하므로 p' = N/A로 두고 투포인터 느낌으로 q'을 조금씩 늘려가면서 A*p' +B*q' == N일 때 값을 구하면 됩니다.
소스코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int M = 1e9+7, N = 1e5;
int f(int n, int p, int q){
if(p>q) swap(p,q);
for(int a = n/p, b = 0; a; --a){
for(int A = a*p; A+(b+1)*q <= n; ++b);
if(a*p+b*q == n) return a+b;
}
return -1;
}
int main(){
scanf("%*d");
for(int n, p, q, c=1; ~scanf("%d%d%d",&n,&p,&q); printf("Case #%d\n%d\n",c++,f(n,p,q)));
}2. 딸기 수확 로봇
문제 요약
1차원 좌표 평면 상에 딸기가 있고 로봇은 원점에서 시작해서 최대 D만큼 움직여 어디서는 멈출 수 있다. 로봇이 딸기가 심어진 좌표를 지나면 딸기가 수확되는데, 딸기를 최대한 수확할 때 몇 개를 얻을 수 있는가?
풀이
경우의 수는 4가지입니다.
1. 원점기준 왼쪽으로 이동
2. 원점기준 오른쪽으로 이동
3. 원점기준 왼쪽갔다가 오른쪽으로 이동
4. 원점기준 오른쪽갔다가 왼쪽으로 이동
3, 4 케이스는 투포인터로 linear하게 구할 수 있겠지만, 시간복잡도도 널널하기에 이분탐색으로 위치를 구했습니다.
소스코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(){
ll n, d;
scanf("%lld%lld",&n,&d);
vector<ll> v(n);
for(auto&t:v) scanf("%lld",&t);
sort(v.begin(), v.end());
ll z1 = lower_bound(v.begin(), v.end(), 0LL) - v.begin(); // 0
ll z2 = upper_bound(v.begin(), v.end(), 0LL) - v.begin(); // 0
ll r = z2 - z1;
for(ll i=0; i<n; ++i){
if(abs(v[i]) > d) continue;
if(v[i] < 0){
r = max(r, z2 - i);
ll j = upper_bound(v.begin(), v.end(), (d + v[i]) / 2) - v.begin();
r = max(r, j - i);
}
else if(v[i] > 0){
r = max(r, i - z1 + 1);
ll j = lower_bound(v.begin(), v.end(), (v[i] - d) / 2) - v.begin();
r = max(r, i - j + 1);
}
}
return r;
}
int main(){
int T;
scanf("%d",&T);
for(ll c=1; T--; ++c) printf("Case #%lld\n%lld\n",c,f());
}3. 장난감
문제 요약
원형 큐에서 각 위치에 Ai개의 구슬이 있고, 한 시점에서 다음 시점으로 넘어갈 때 Ai 위치에 구슬이 있다면 다음 시점에 시계방향 다음 위치에 구슬을 넘기는 과정을 반복해서 사이클이 생길 때 그 길이를 구합니다.
풀이
두 스텝으로 해결했습니다.
1. 사이클 시작 시점 상태 구하기
2. 사이클 길이 구하기
1. 사이클 시작 시점은 구슬의 0인 부분을 최대한 채워가면 알 수 있습니다.
0인 부분이 가능한 대부분 채워지면 위상이 같은 상태로 회전을 하게 됩니다.
간단하게 관찰하자면, 0인 부분은 시계방향 가장 가까운 구슬 개수가 1 초과인 위치에서 구슬을 하나 얻어와 채울 수 있습니다.
이는 스택으로 잘 구현할 수 있으니 아래 코드를 확인해주세요
2. 사이클 길이는 kmp를 사용하면 쉽게 구할 수 있으나, 대회중에 생각을 못해서 소인수분해 해가면서 나눠봤었습니다.
n의 소인수 k에 대해 i + j * n / k (j = 0, ..., k) 위치의 값들이 모두 같으면 그만큼 사이클 길이를 나눠줄 수 있으므로
n을 k로 나눈 후 또 다른 k'에 대해 확인하는걸 반복합니다.
마지막으로 남은 n 값이 사이클 길이가 됩니다.
0이 없는 상태인 경우 시간이 지나도 상태가 유지되므로 사이클 길이는 1입니다.
소스코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int M[500001];
vector<int> V;
ll f(){
int n;
scanf("%d",&n);
vector<pair<int,int>> a, b;
int q = -1, c = 0, w;
for(int i=0; i<n; ++i){
scanf("%d",&w);
if(!w){ if(q==-1) q=i; ++c; }
else if(w>1){
if(q!=-1) a.push_back({q,c}), q=-1, c=0;
int t = w - 1;
if(a.size()){
for(; a.size() && t;){
if(a.back().second <= t) t-=a.back().second, a.pop_back();
else a.back().second -= t, t=0;
}
}
if(t) b.push_back({i,t});
}
else if(q!=-1) a.push_back({q,c}), q=-1, c=0;
}
if(q!=-1) a.push_back({q,c}), q=-1;
for(c=0; c<b.size() && a.size();){
if(a.back().second <= b[c].second) b[c].second -= a.back().second, a.pop_back();
else a.back().second -= b[c].second, ++c;
}
if(!a.size()) return 1;
vector<int> v(n,1);
for(; c<b.size(); ++c) v[b[c].first] = b[c].second + 1;
for(auto&[x,y]:a) for(c=0; c<y; ++c) v[x+c] = 0;
auto g = [&](int k){for(int i=0; i<k; ++i) for(int j=1; j<V[c]; ++j) if(v[i]!=v[i+j*k]) return 0;return 1;};
for(c=0; c<V.size() && V[c] <= n && n>1;){
if(n%V[c]!=0) {++c; continue;}
if(g(n/V[c])) n/=V[c];
else ++c;
}
return n;
}
int main(){
setbuf(stdout, NULL);
//freopen("output.txt","w",stdout);
for(int i=2; i<=500000; i += i>2?2:1){
if(M[i]) continue;
V.push_back(i);
for(int j=i+i; j<=500000; j+=i) M[j]=1;
}
int T;
scanf("%d",&T);
for(ll c=1; T--; ++c) printf("Case #%lld\n%lld\n",c,f());
}4. 최적의 프로세스 수행 순서
문제 요약
진행하고자 하는 프로세스 R이 있고 효율적인 프로세스 패턴 P가 있습니다.
R을 연속적으로 잘 분해해서 각 segment가 P의 접두사가 될 수 있게 할 때, segment의 수를 최소화하는 문제입니다.
풀이
문제를 보면 KMP를 떠올릴 수 있습니다.
P 문자열에 대해 failure function f를 만들고 j로 확인할 위치를 지정한다고 할 때, 아래 점화식을 얻을 수 있습니다.
D[0] = 0
D[i + 1] = D[i - f(j) - 1] + 1
답은 D[|R|]이 됩니다.
소스코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f() {
string s1, s2;
cin >> s1 >> s2;
vector<int> v(s1.size() + 1, -1); v[0] = 0;
vector<int> f(s2.size() + 1,0); f[0] = -1;
for (int i = 0, j = -1; i < s2.size(); f[++i] = ++j) while (~j && s2[i] != s2[j]) j = f[j];
for (int i = 0, j = 0, t = 0; i < s1.size(); ++i) {
while (~j && s1[i] != s2[j]) j = f[j]; ++j;
if (v[i - j + 1] > -1)v[i + 1] = v[i - j + 1] + 1;
}
return v[s1.size()];
}
int main() {
int T;
cin >> T;
for (ll c = 1; T--; ++c) cout << "Case #" << c << '\n' << f() << endl;
}5. 타이젠
문제 요약 및 풀이
일반적인 CHT문제이므로 문제는 생략하겠습니다.
f(x = A[i]) = B[i] * x + C[i]에 대해 A는 활성 구간 사이의 휴식구간 길이, B는 Pi, C는 Wi로 생각하면 됩니다.
너무 피곤해서 자고 나니 시간이 안남아서.. 풀지 못했습니다 ㅠ