올해는 삼성 DX 알고리즘 특강 과제 문제를 푸느라 바빴고, 당장 대회 다음날이 정보처리기사 실기 시험이라 대회를 위한 준비를 많이 못 했다. 엘리스 코드 챌린지 본선에 진출했으나 일정이 SCPC와 완전히 겹쳤고, 온전히 12시간을 다 쓰기 위해 참여하지 않았다. 수상자분들이 모두 코드포스 레드 이상이었다는 말을 들었다. 안 가길 잘했다.
풀이
1. 연속 1
최종 수열의 모양은 $00...00$, $00...11$, $11...00$, $11...11$, $00...111...00$ 중 하나이다.
모든 모양은 0→1→0의 상태로 표현될 수 있다. (각 구간의 수의 개수는 0개일 수 있다.)
$dp[0][i]$ : 0인 상태이고 i번째 수까지 봤을 때, 최소 비용
$dp[1][i]$ : 0→1인 상태이고 i번째 수까지 봤을 때, 최소 비용
$dp[2][i]$ : 0→1→0인 상태이고 i번째 수까지 봤을 때, 최소 비용
라고 정의하고, 각 상태에 맞는 비용을 지불하면 된다.
시간복잡도는 $O(N)$.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;ll s,e;scanf("%d%lld%lld",&n,&s,&e);
vector<int> v(n+1);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
vector<vector<ll>> dp(3,vector<ll>(n+1,2e18));
//0...1...0중에 0, 0...1, 0...1...0
dp[0][0]=0;
for(int i=0;i<n;i++){
int nx=v[i+1];
dp[0][i+1]=min(dp[0][i+1],dp[0][i]+(nx?e:0));
dp[2][i+1]=min(dp[2][i+1],dp[1][i]+(nx?e:0));
dp[2][i+1]=min(dp[2][i+1],dp[2][i]+(nx?e:0));
dp[1][i+1]=min(dp[1][i+1],dp[0][i]+(nx?0:s));
dp[1][i+1]=min(dp[1][i+1],dp[1][i]+(nx?0:s));
}
printf("%lld\n",min({dp[0][n],dp[1][n],dp[2][n]}));
fflush(stdout);
}
int main(){
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}2. 라운드 로빈
이 문제랑 비슷한 것 같다.
(1)어떤 작업이 끝나는 데 걸리는 누적 시간과 (2)끝나는 작업 번호를 기록해두면, (3)특정 시각에 어떤 작업들이 남아있는지 구할 수 있다. (코드에서는 각각 (1)$sum$, (2)$idx$, (3)$se$에 기록해두었다.)
어떤 시각 $x$가 $[sum[i] \sim sum[i+1]]$구간에 포함되어 있을 때, 해당 시각에 $se$에는 $idx[0], idx[1], \ldots idx[i]$가 삭제되고 남은 CPU들이 저장되어 있다.
이제 남은 $x-sum[i]$만큼의 작업은 CPU 개수가 고정된 상태로 할당되고, mod 연산으로 순서를 구해주면 된다.(set에서 순서에 따른 값을 찾기 위해 pbds를 사용했다.)
쿼리를 시간순으로 정렬해두면, 다음 시각으로 넘어갈 때 CPU를 초기 상태로 되돌릴 필요 없이 추가로 삭제할 것만 고려해주면 된다.
시간복잡도는 $O(NlogN + Q(logQ+logN))$.
코드
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
void solve(){
ll n,q;scanf("%lld%lld",&n,&q);
vector<ll> w(n+1);
vector<pll> v(1);
for(int i=1;i<=n;i++){
scanf("%lld",&w[i]);
v.push_back({w[i],i});
}
sort(v.begin(),v.end());
ordered_set se;
for(int i=0;i<=n;i++)se.insert(i);
vector<ll> Q;
for(int i=0;i<q;i++){
ll x;scanf("%lld",&x);
Q.push_back(x);
}
sort(Q.begin(),Q.end());
vector<ll> sum(1),idx(1);
for(ll i=1;i<v.size();i++)
sum.push_back(sum.back()+(v[i].first-v[i-1].first)*(n+1-i)),
idx.push_back(v[i].second);
ll ans=0,i=0;
for(auto x:Q){
while(i<sum.size()&&x>sum[i]){
se.erase(idx[i]);
i++;
}
ll re=x-sum[i-1],order=re%(ll)se.size();
if(!order)order=se.size();
ll add=*se.find_by_order(order-1);
ans+=add;
}
printf("%lld\n",ans);
fflush(stdout);
}
int main(){
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}3. 방범 시스템
경찰관과 사건과의 거리가 $\sqrt{(x1-x2)^2+(y1-y2)^2}$가 아닌 $|x1-x2|+|y1-y2|$이므로, x와 y의 거리를 각각 독립적으로 계산해도 된다.
확률이 최대 6자리 실수이므로, 사건이 총 $10^6$ 개라고 생각하고 해당 위치에 사건이 $p*10^6$ 개 있을 때 거리의 평균을 구해주었다.
경찰관의 x좌표 X보다 작은 사건이 E개$(x_1, x_2, \ldots x_E)$ 있다고 하면, 이들과 경찰관의 거리의 합은 $\sum\limits_{i=1}^{E}(X-x_i) = XE - \sum\limits_{i=1}^{E} x_i$가 된다. $\sum\limits_{i=1}^{E} x_i$는 세그먼트 트리 구간 합으로 구했는데, 누적 합으로도 풀 수 있다고 한다.
마찬가지로 X보다 큰 사건이 E개라면, 거리의 합은 $\sum\limits_{i=1}^{E} x_i - XE$(부호가 반대)이고, y좌표도 똑같이 해주면 된다.
문제 풀 때 update 쪽에서 사소한 구현 실수가 있었는데, 입력받는 쪽이 문제인 줄 알고 입력을 불필요하게 귀찮게 고쳤었다. 입력은 각자 편한 방법으로 받으면 될 것 같다.
좌표 제한이 커서 좌표 압축을 해주지 않으면 TLE를 받을 수 있다.
시간복잡도는 $O((n+m) * log(n+m))$(좌표 압축)
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define UNIQUE(v) sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
#define xi(x) (lower_bound(xcomp.begin(),xcomp.end(),x)-xcomp.begin())
#define yi(y) (lower_bound(ycomp.begin(),ycomp.end(),y)-ycomp.begin())
const int sz=1<<18;
ll arr[2][sz<<1];
char st[10];
void update(bool xy,int i,ll val){
i+=sz,arr[xy][i]+=val;
while(i>1)i>>=1,arr[xy][i]=arr[xy][i<<1]+arr[xy][i<<1|1];
}
ll query(bool xy,int s,int e,int node=1,int ns=0,int ne=sz-1){
if(e<ns||ne<s)return 0;
if(s<=ns&&ne<=e)return arr[xy][node];
int mid=(ns+ne)>>1;
return query(xy,s,e,node<<1,ns,mid)+query(xy,s,e,node<<1|1,mid+1,ne);
}
ll cnt[2][sz<<1];
void _update(bool xy,int i,ll val){
i+=sz,cnt[xy][i]+=val;
while(i>1)i>>=1,cnt[xy][i]=cnt[xy][i<<1]+cnt[xy][i<<1|1];
}
ll _query(bool xy,int s,int e,int node=1,int ns=0,int ne=sz-1){
if(e<ns||ne<s)return 0;
if(s<=ns&&ne<=e)return cnt[xy][node];
int mid=(ns+ne)>>1;
return _query(xy,s,e,node<<1,ns,mid)+_query(xy,s,e,node<<1|1,mid+1,ne);
}
void solve(){
memset(arr,0,sizeof(arr));
memset(cnt,0,sizeof(cnt));
int n;scanf("%d",&n);
vector<pll> v(n);
vector<ll> p(n),xcomp,ycomp;
for(auto &[x,y]:v){
scanf("%lld%lld",&x,&y);
xcomp.push_back(x),ycomp.push_back(y);
}
//입력은 6자리 실수로 고정됐기 때문에, scanf("%d.%d",&x,&y);로 받고 p[i]=x*10^6+y로 구해도 될 듯.
for(int i=0;i<n;i++){
scanf("%s",st);
int stn=strlen(st);
for(int j=0;j<8;j++){
if(st[j]=='.')continue;
ll x=j>=stn?0:st[j]-'0';
p[i]=p[i]*10+x;
}
}
int m;scanf("%d",&m);
vector<pll> q(m);
for(auto &[x,y]:q){
scanf("%lld%lld",&x,&y);
xcomp.push_back(x),ycomp.push_back(y);
}
UNIQUE(xcomp);UNIQUE(ycomp);
for(int i=0;i<n;i++){
int x=xi(v[i].first);
update(0,x,p[i]*xcomp[x]);
_update(0,x,p[i]);
int y=yi(v[i].second);
update(1,y,p[i]*ycomp[y]);
_update(1,y,p[i]);
}
for(auto [x,y]:q){
x=xi(x),y=yi(y);
ll smallx=_query(0,0,x)*xcomp[x]-query(0,0,x);
ll smally=_query(1,0,y)*ycomp[y]-query(1,0,y);
ll largex=query(0,x,(int)xcomp.size())-_query(0,x,(int)xcomp.size())*xcomp[x];
ll largey=query(1,y,(int)ycomp.size())-_query(1,y,(int)ycomp.size())*ycomp[y];
ll ans=smallx+smally+largex+largey;
printf("%lld.",ans/1000000ll);
printf("%0*lld\n",6,ans%1000000ll);
}
fflush(stdout);
}
int main(){
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}4. 수열 탈집중화
최종 수열이 어떤 상태가 되어야 하는지 알아보자.
(수열의 집중되어있지 않은 정도 $C$는 $\sum\limits_{1\leq i,j \leq n} (a_i-a_j)^2$로 정의되어 있다. 편의상 $i<j$라고 하면 이 값은 $\frac{C}{2}$이다.)
먼저 최솟값(mn), 최댓값(mx) 사이의 어떤 수를 x라고 하자.
수열 $\{mn, mx, x\}$의 $\frac{C}{2}$값을 구해보면 $(mx-mn)^2 + (mx-x)^2 + (mn-x)^2$이고, 여기서 변수인 $x$에 대한 항만 고려하면 $2(x^2 - (mx+mn)x)$이다. 이 함수는 $x=\frac{mx+mn}{2}$일 때 극솟값을 가지고, 멀어질수록 점점 커지는 이차함수이다. 따라서 $x=mx$ 또는 $x=mn$일 때 $C$가 가장 크다.
→ 최종 수열에는 최댓값과 최솟값 이외의 수는 존재하면 안 된다.
위 결과로, 최솟값의 개수를 x, 최댓값의 개수를 y라고 하면, x+y=n이다.
이때 $\frac{C}{2} = (mx-mn)^2*xy = (mx-mn)^2*x(n-x)$이므로, 마찬가지로 x에 대한 항만 고려하면 $x=\frac{n}{2}$일 때 $C$가 가장 크다.
→ 최종 수열의 상태는 최댓값과 최솟값만으로 이루어져 있으면서, 그 개수가 균등한 상태이다.
이제 연산 시행 횟수에 따라 나눠서 생각해보자. (최솟값도 아니고 최댓값도 아닌 수를 '애매한 수(mid)'라고 정의하자.)
- 연산 0회
- mn==mx인 경우
- 이미 mn과 mx의 개수가 균등한 경우
- 연산 1회
- mx의 개수가 절반 이상이고, mn의 개수가 모자란 경우
→ 구간 [l~r]을 찾아서 해당 구간을 모두 mn으로 만들고, 최종 수열의 조건을 만족하는지 확인한다.
(단, (1)이 구간은 모든 mid와 적어도 하나의 mn을 반드시 포함해야 한다. 또한, (2)연산 시행 후에도 mx가 여전히 절반 이상인지 확인해야 한다.)
만약 임의의 l값 $l_i$에 대해 (1)을 만족하는 가장 작은 r값 $r_i$를 찾았다면, $l_{i+1}$에 대해 (1)을 만족하는 $r_{i+1}$값은 항상 $r_i$보다 크거나 같다. 따라서 스위핑을 통해 $O(n)$에 모든 l, r 쌍을 검사할 수 있다.
(2)까지 만족하는 쌍을 발견하면, 해당 구간에 1번 연산을 수행하고 종료한다. - mn의 개수가 절반 이상이고, mx의 개수가 모자란 경우
→ 2)-1과 똑같은 방법으로 구하면 된다. (대신 1번 연산이 아니라 2번 연산을 해야 한다.)
- mx의 개수가 절반 이상이고, mn의 개수가 모자란 경우
- 연산 2회 이상
2회의 연산으로 항상 조건을 만족하는 수열을 만들 수 있다.
일단, mx와 mn에 해당하는 수를 아무 데서나 하나씩 고른다.(mnidx, mxidx)
- mnidx<mxidx인 경우(최솟값이 최댓값보다 왼쪽에 있는 경우)
→ 골라둔 수를 건드리지 않고 최솟값을 최대한 많이 만들려면 [1~mxidx)에 1번 연산을 하면 된다.
마찬가지로, 최댓값을 최대한 많이 만들려면 (mnidx,n]에 2번 연산을 하면 된다.
두 구간의 길이 중 하나는 반드시 $\frac{n}{2}$이상이므로, 더 긴 구간에 먼저 연산을 하고 다음 연산을 할 때 개수를 맞춰주면 된다. - mxidx<mnidx인 경우(최댓값이 최솟값보다 왼쪽에 있는 경우)
→3)-1과 똑같은 방법으로 구하면 된다.
- mnidx<mxidx인 경우(최솟값이 최댓값보다 왼쪽에 있는 경우)
시간복잡도는 $O(n)$.
코드
#include <bits/stdc++.h>
using namespace std;
#define cal(v,l,r) (v[r]-v[l-1])
int v[50002],lmn[50002],lmx[50002];
void solve(){
int n;scanf("%d",&n);
int mn=2e9,mx=-2e9;
for(int i=1;i<=n;i++){
scanf("%d",&v[i]);
mn=min(mn,v[i]),mx=max(mx,v[i]);
}
//1)-1
if(mx==mn){printf("0\n");fflush(stdout);return;}
int midl=1e9,midr=-1e9;
for(int i=1;i<=n;i++){
lmn[i]=lmn[i-1]+(v[i]==mn);
lmx[i]=lmx[i-1]+(v[i]==mx);
if(v[i]!=mx&&v[i]!=mn)midl=min(midl,i),midr=max(midr,i);
}
//1)-2
if(lmn[n]+lmx[n]==n&&lmn[n]>=n/2&&lmx[n]>=n/2){printf("0\n");fflush(stdout);return;}
//2)-1
int l=0,r=max(0,midr);
while(l<n){
l++;if(l>midl)break;
while(r<=n&&cal(lmn,l,r)<1)r++;
while(r<=n&&(r-l+1)+cal(lmn,r+1,n)+cal(lmn,1,l-1)<n/2)r++;
if(r>n)break;
int mns=(r-l+1)+cal(lmn,r+1,n)+cal(lmn,1,l-1);
if(mns>=n/2&&n-mns>=n/2){
printf("1\n");
printf("1 %d %d\n",l,r);fflush(stdout);return;
}
}
//2)-2
l=0,r=max(0,midr);
while(l<n){
l++;if(l>midl)break;
while(r<=n&&cal(lmx,l,r)<1)r++;
while(r<=n&&(r-l+1)+cal(lmx,r+1,n)+cal(lmx,1,l-1)<n/2)r++;
if(r>n)break;
int mxs=(r-l+1)+cal(lmx,r+1,n)+cal(lmx,1,l-1);
if(mxs>=n/2&&n-mxs>=n/2){
printf("1\n");
printf("2 %d %d\n",l,r);fflush(stdout);return;
}
}
printf("2\n");
int mxidx=-1,mnidx=-1;
for(int i=1;i<=n;i++){
if(v[i]==mx)mxidx=i;
if(v[i]==mn)mnidx=i;
}
if(mnidx<mxidx){//3)-1
int mnlen=mxidx-1,mxlen=n-mnlen;
if(mnlen>mxlen){//3)-1-1
printf("1 %d %d\n",1,1+mnlen-1);
printf("2 %d %d\n",n-n/2+1,n);
}
else{//3)-1-2
printf("2 %d %d\n",n-mxlen+1,n);
printf("1 %d %d\n",1,n/2);
}
}
else{//3)-2
int mxlen=mnidx-1,mnlen=n-mxlen;
if(mxlen>mnlen){//3)-2-1
printf("2 %d %d\n",1,1+mxlen-1);
printf("1 %d %d\n",n-n/2+1,n);
}
else{//3)-2-2
printf("1 %d %d\n",n-mnlen+1,n);
printf("2 %d %d\n",1,n/2);
}
}
fflush(stdout);return;
}
int main(){
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
return 0;
}5. 보물찾기 (18점 / 500점)
Bob의 모든 정점에 보물이 있는 경우만 고려한 코드이다. (위아래로 코드가 지저분해서 해당 부분만 코드를 첨부한다.)
이 경우 Bob은 정점 B를 벗어나야 하는데, Alice가 다시 말을 B로 되돌려놓으면 무한히 보물을 얻게 된다.
Alice가 패배하는 경우는, 보물이 없는 Alice 소유의 땅으로만 연결된 그래프에 해당하는 정점만 고려하면 된다. 나머지는 모두 Alice의 승리이다.
코드
for(int i=1;i<=n;i++)vis[i]=0;
queue<int> q;
for(int i=1;i<=n;i++)
if(b[i]=='T')q.push(i),vis[i]=1;
while(!q.empty()){
int cur=q.front();q.pop();
for(auto nx:graph[cur]){
if(vis[nx])continue;
vis[nx]=1,q.push(nx),b[nx]='T';
}
}
for(int i=1;i<=n;i++)
printf(b[i]=='T'?"A":"B");
printf("\n");후기
작년과 마찬가지로 아침까지는 멍하다가, 점심 먹고 나서부터 정신이 좀 들었던 것 같다. 1번 문제를 그리디로 접근하다가 시간과 페널티를 많이 날렸고, 2, 3번을 풀고 돌아와서야 제대로 된 풀이가 생각났다. 제출 횟수를 다 쓸뻔해서 초조했다.
2번에 pbds를 사용하거나 3번에 세그먼트 트리를 사용한 것이 오버킬이라고 생각하긴 하지만, 그래도 나름 다 어려운 문제라고 생각했는데 만점자가 왜 이렇게 많은지 모르겠다. 내 실력에 비해서 그럭저럭 좋은 성적을 낸 것 같은데, 커트라인이 어떻게 될지 모르겠다.
한 가지 아쉬움이 남는다면, 5번 문제를 애초에 부분점수만 노리고 풀었어야 했다. 4번까지 만점 코드를 낸 시점이 대회 종료 3시간 30분 전이었고, 이때 4번 만점자 수가 100명 아래였다. 그래서 저녁도 먹고 느긋한 마음으로 5번의 500점짜리 풀이를 고민했는데, 역시나 생각지 못한 반례들이 있었다. 결국, 대회 종료 50분 전부터 급하게 부분점수를 긁기 시작했지만 32점짜리 서브태스크의 반례가 대회 종료 10분 전에 생각나서 손쓸 수가 없었다.
...그런데 어차피 올해가 마지막이라 피드백은 별로 의미가 없다. 진인사대천명. 본선 진출 여부를 기다려보자.
와!
'CP > 대회 후기' 카테고리의 다른 글
| SCPC 2024 Final 대회 후기 (3) | 2024.09.10 |
|---|---|
| 제5회 고려대학교 MatKor Cup 후기 (4) | 2024.09.09 |
| SCPC 2024 Round 1 대회 후기 + 풀이 (0) | 2024.07.06 |
| 2024 SCSC 서울대학교 프로그래밍 경시대회 후기 (1) | 2024.06.02 |
| INU 코드페스티벌 2023 개최 과정 + 후기 (6) | 2023.12.20 |