12시간 동안 거의 쉬지 않고 참여한 대회는 이번이 처음이었다. 1차 예선이 24시간으로 더 길긴 했지만, 이때는 오히려 시간이 많아서 중간마다 쉬면서 유튜브도 보면서 컨디션 조절도 했었고, 새벽에 5번 문제를 만점을 받고 잠들어서 시간적 압박도 크게 없었던 것 같다. 그런데 이번에는 대회가 일찍 시작해서 약간 졸린 상태였고, 시간도 생각보다 엄청 빠르게 지나갔고, 밥 먹을 때도 대충 입에 욱여넣고 고민만 하다 보니 후반에는 머리가 멍해지기도 했던 것 같다. 끝나고 너무 힘들어서 요즘 하고 있는 구름톤 챌린지와 solved.ac 스트릭을 졸면서 채우고 기절하듯 잠들었는데, 거의 반나절을 잤다.
풀이
1. 타이젠 윷놀이
윷놀이 판의 각 위치 x마다, x에서 시작하여 $N$개의 윷을 던졌을 때 몇 점을 획득한 후 어디에 도착하게 되는지 시뮬레이션을 통해 $O(N)$에 구할 수 있다. 시작 위치로 가능한 상태가 총 22개이므로, 일일이 구해줘도 된다.
윷놀이 판에 임의의 숫자를 부여한 후, 지름길 조건에 맞게 구현해주었다(음수는 앞으로 지름길을 탈 일이 없는 경우이며, 남은 칸 수를 나타낸다.). 시작점에서 출발하는 경우(0)와 골인 직전의 경우(-100)를 구분해주었다.
이 정보를 바탕으로 $K$번의 시뮬레이션을 돌려주면 되므로, 시간복잡도는 총 $O(N+K)$이다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
map<int,pii> ma;//key 위치에서 시작해서 윷을 n번 던지면, first 바퀴를 돌고, second 위치에 도착한다.
vector<int> x;
void solve(){
int n,k;scanf("%d%d",&n,&k);
vector<int> v(n);
ma.clear();
for(int i=0;i<n;i++)scanf("%d",&v[i]);
for(auto start:x){
int cur=start,yut=0,score=0;
while(yut<n){
int tmp=cur;
cur+=v[yut++];
if(cur==5)cur=100;
else if(cur==10)cur=-6;
else if(cur==103)cur=-3;
else if(cur==0)cur=-100;
else if(tmp==-100)score++,cur=0;
else if(cur>103)cur=cur-111;
else if(cur>10&&cur<50)cur=cur-20;
else if(tmp<0&&cur>0)score++,cur=0;
}
ma[start]={score,cur};
}
int cur=0;
ll ans=0;
while(k--){
auto [score,e]=ma[cur];
ans+=score,cur=e;
}
printf("%lld\n",ans);
}
int main(int argc, char** argv){
setbuf(stdout,NULL);
for(int i=-9;i<=4;i++)x.push_back(i);
for(int i=100;i<=102;i++)x.push_back(i);
for(int i=6;i<=9;i++)x.push_back(i);
x.push_back(-100);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
}2. 괄호 문자열
먼저, 열린 괄호의 개수 x를 기준으로 번호를 부여하여 색깔을 칠해보면 아래와 같이 나타낼 수 있다.
{ { } ( ( ) ) ( { } ( ) ) } ( ) x=1, 빨강 / x=2, 보라 / x=3, 초록
연속된 괄호 문자열을 이어줄 때, 다른 색깔의 괄호는 없다고 생각해도 무방하다. 또한, 초록색 괄호의 입장에서 생각해보면, 보라색 괄호에 싸여있는 두 공간은 서로 다른 공간이므로 이어질 수 없다. 따라서 x인(보라색) 괄호가 열리거나 닫힐 때, x+1인(초록색) 괄호 집합의 개수$(=cnt[x+1])$를 0으로 만들면 된다.
또한 잘못된 괄호 문자열이 등장할 경우, 지금까지의 문자열과 이후에 등장할 문자열은 서로 이어질 수 없다. 따라서 모든 상태를 초기화한 후 처음부터 시작한다는 느낌으로 답을 구해주면 된다. 이때 길이 N에 대해 매번 초기화하면 $O(N^{2})$의 시간이 걸리는데, 현재 열린 괄호가 x개일 경우 $cnt[x+1]=cnt[x+2]=...=0$이므로 [1~x]범위만 초기화해주면 된다.
따라서 시간복잡도는 $O(N)$.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1000003];
int cnt[1000003];
vector<char> b;
map<char,char> match;
void solve(){
int n;scanf("%d%s",&n,s);
memset(cnt,0,sizeof(cnt));
b.clear();
int x=0;
ll ans=0;
for(int i=0;i<n;i++){
if(s[i]=='{'||s[i]=='(')b.push_back(s[i]),x++;
else {
if(b.empty()||match[b.back()]!=s[i]){//잘못된 괄호 문자열
b.clear();
for(int j=x+1;j>=0;j--)cnt[j]=0;
x=0;
continue;
}
b.pop_back(),x--;
cnt[x]++,ans+=cnt[x];
}
cnt[x+1]=0;
}
printf("%lld\n",ans);
}
int main(int argc, char** argv){
setbuf(stdout,NULL);
match['{']='}',match['(']=')';
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
}3. 루머
$dp[i][j]$ : 현재 i번째 사람을 보고 있고, 나의 왼쪽 이웃이 나에게 루머를 퍼트린 상태를 j(0:안퍼트림 / 1:퍼트림)라고 할 때, 루머를 믿는 사람의 최댓값
$two[i]$ : i번째 사람의 오른쪽에 있는(i를 포함) 귀가 얇지 않은 사람 중 가장 가까운 위치
$mid[i]$ : i번째 사람에게 t초 안에 루머를 퍼트릴 수 있는 가장 먼 위치(오른쪽 기준)
$ri[i]$ : i번째 사람이 t초 안에 루머를 퍼트릴 수 있는 가장 먼 위치(오른쪽 기준)
라고 정의한 후, $|S_{0}|<=M$이므로 dp테이블을 M번 갱신해주었다.
만약 이번 갱신에서 i번째 사람에게 루머를 퍼트리기로 했다고 가정해보자.
- i번째 사람이 귀가 얇은 사람인 경우$(v[i]=1)$ -> $mid[i]$위치에서 루머를 퍼트려주는 게 가장 이득이고, 이때 루머는 $ri[mid[i]]$까지 퍼지게 된다. -> $mid[i]$번째 사람이 $ri[mid[i]]-i+1$명에게 루머를 퍼트릴 수 있다.
- i번째 사람이 귀가 얇지 않은데, 나의 왼쪽 이웃이 나에게 루머를 퍼트린 경우$(v[i]=2, cover=1)$ -> 1번과 똑같이 해주면 된다.
- i번째 사람이 귀가 얇지 않으면서, 나의 왼쪽 이웃이 나에게 루머를 퍼트리지도 않은 경우$(v[i]=2, cover=0)$ -> i 위치에서 직접 루머를 퍼트려줄 수밖에 없고, 이때 루머는 $ri[i]$까지 퍼지게 된다. -> i번째 사람이 $ri[i]-i+1$명에게 루머를 퍼트릴 수 있다.
이 과정에서 루머를 믿게 된 가장 오른쪽 사람$(=ri[mid[i]] \; or \; ri[i])$의 오른쪽 이웃이 귀가 얇지 않은 사람이라면, $j=1$인 경우도 같이 갱신해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int dp[5001][2],tmp[5001][2];
int two[5001],mid[5001],ri[5001];
void solve(){
int n;scanf("%d",&n);
vector<int> v(n);
for(int i=0;i<=n;i++)dp[i][0]=0,dp[i][1]=-0x3f3f3f3f;
for(int i=0;i<n;i++)scanf("%d",&v[i]);
int m,t;scanf("%d%d",&m,&t);
two[n]=n;
for(int i=n-1;i>=0;i--){
two[i]=v[i]==2?i:two[i+1];
mid[i]=min({i+t,two[i+1],n-1});
ri[i]=min(i+t,two[i+1]-1);
}
int ans=0;
while(m--){
memset(tmp,-0x3f,sizeof(tmp));
for(int i=0;i<n;i++){
int right=ri[i],middle=mid[i],midright=ri[middle];
for(int cover=0;cover<2;cover++){
dp[i+1][0]=max(dp[i+1][0],dp[i][cover]);//안퍼트림.
if(!cover&&v[i]==2){//퍼트릴거라면 무조건 얘한테 퍼트려야함.
if(right<i+t)//right 다음 위치가 2라면,
tmp[right+1][1]=max(tmp[right+1][1],dp[i][cover]+right-i+1);//그 2는 커버됨.
tmp[right+1][0]=max(tmp[right+1][0],dp[i][cover]+right-i+1);
}
else{//퍼트릴거라면 middle한테 퍼트려야하고, 걔 기준으로 right가 midright임.
if(midright<middle+t)//right 다음 위치가 2라면,
tmp[midright+1][1]=max(tmp[midright+1][1],dp[i][cover]+midright-i+1);//그 2는 커버됨.
tmp[midright+1][0]=max(tmp[midright+1][0],dp[i][cover]+midright-i+1);
}
}
}
for(int i=0;i<=n;i++)for(int j=0;j<2;j++)dp[i][j]=tmp[i][j];
ans=max({ans,dp[n][0],dp[n][1]});
}
for(int i=0;i<=n;i++)for(int j=0;j<2;j++)ans=max(ans,dp[i][j]);
printf("%d\n",ans);
}
int main(int argc, char** argv){
setbuf(stdout,NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
}4. 막대기 연결 (180/400점)
일반적으로 쿼리를 빠른 시간에 처리해주는 세그먼트 트리나 mo's 알고리즘 위주로 고민해봤지만, 왠지 깊은 관찰이 필요할 것 같고 3번 문제를 푸는 게 더 급한 상황이라 $N^{2}$ 풀이로 180점을 긁고 넘어갔다.
$dp[l][r]$ : [l~r]의 막대기 중에서 사각형의 왼쪽 막대기를 l로 고정했을 때, 가능한 사각형 면적의 최솟값이라고 정의하면 dp 테이블을 $O(N^2)$에 채워 넣을 수 있다.
쿼리 구간 [a,b]에 대한 답은 $min(dp[a][b], dp[a+1][b], ... , dp[b-1][b])$이므로, 각 쿼리에 $O(N)$의 시간이 소요된다.
따라서 시간복잡도는 $O(N*(N+K))$이다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll dp[3001][3001];
void solve(){
int n;scanf("%d",&n);
vector<pll> v(n+1);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&v[i].first,&v[i].second);
for(int j=1;j<=n;j++)dp[i][j]=0;
}
for(int l=1;l<=n;l++){
auto [lx,lh]=v[l];
pll ans={2e18,l+1};
for(int r=l+1;r<=n;r++){
auto [rx,rh]=v[r];
ll area=(ll)(rx-lx)*(lh+rh);
ans=min(ans,{area,r});
dp[l][r]=ans.first;
}
}
int k;scanf("%d",&k);
while(k--){
int a,b;scanf("%d%d",&a,&b);
ll ans=2e18;
for(int i=a;i<b;i++)ans=min(ans,dp[i][b]);
printf("%lld\n",ans);
}
}
int main(int argc, char** argv){
setbuf(stdout,NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
}5. 스마트 아파트 건설 (60/400점)
$N<=20$을 보고 $2^{N}$ 혹은 $N*2^{N}$의 비트마스킹 풀이를 고민해봤지만, 전혀 떠오르지 않아서 브루트포스로 서브태스크만 긁었다.
아파트 건설 계획의 모든 경우의 수가 $N!$가지이고, 각각의 계획마다 조건을 만족하는지 확인하기 위해 최대 $N(N−1)/2$개의 도로를 확인해야 하므로, 시간복잡도는 $O(N!*N^{2})$이다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n,k,m;scanf("%d%d%d",&n,&k,&m);
vector<vector<int>> graph(n+1);
while(m--){
int a,b;scanf("%d%d",&a,&b);
a--,b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
if(n>8){printf("0\n");return;}
int ans=0;
vector<int> v;for(int i=1;i<=n;i++)v.push_back(i);
do{
bool ok=1;
for(int i=0;i<n;i++)
for(auto nx:graph[i])
if(v[i]+v[nx]>k)ok=0;
ans+=ok;
}while(next_permutation(v.begin(),v.end()));
printf("%d\n",ans);
}
int main(int argc, char** argv){
setbuf(stdout,NULL);
int tc;scanf("%d",&tc);
for(int i=1;i<=tc;i++){
printf("Case #%d\n",i);
solve();
}
}후기
1차 때 패널티 관리를 대충 하다가 제출 제한 10번을 다 채울 뻔한 적이 있어서, 이번에는 직접 예제도 만들면서 엄청 신중히 제출 버튼을 눌렀던 것 같다.
이번 문제들은 1차 예선처럼 '고난도 알고리즘을 얼마나 많이 알고 있는가?'라는 느낌보다는, 잘 알려진 알고리즘에 구현을 섞어서 '얼마나 내 생각을 코드로 잘 표현할 수 있는가?'를 묻는 느낌이었던 것 같다. 4, 5번 문제의 만점의 벽이 너무 높아서 못 풀었기 때문에, 이번에 소개한 풀이들은 아마 대부분의 참가자분과 크게 다르지 않았을 것으로 생각한다.
1, 2차 때 공통으로 느꼈던 점은, SCPC는 특히나 서브태스크 점수를 잘 긁는 게 중요한 대회인 것 같다. 4, 5번의 서브태스크 문제는 체감상 1번 문제보다 쉬웠는데도 배점이 꽤 높았기 때문에, 본선에서는 특정 문제의 만점에 집착하기보다는 여러 문제의 부분점수를 미리 확보해 두는 게 좋은 전략이 될 것 같다. 개인적으로는 각 서브태스크 상황에서 생각을 확장시키고 여러 가지 최적화를 거쳐서 만점에 도달하는 느낌이 아니라, 서브태스크마다 아예 다른 문제라고 느껴졌다.
그리고 본선을 가게 된다면 아마 예제를 만들어볼 시간이 없을 것이다. 서브태스크에 시도할 제출 횟수도 생각하면, 구현을 더 간결하고 명확하게 하는 연습이 필요할 것 같다.
'CP > 대회 후기' 카테고리의 다른 글
| 2023 Sogang Programming Contest 검수 후기 (0) | 2023.12.16 |
|---|---|
| 2023 ICPC Seoul Regional(지역예선) 후기 (1) | 2023.10.29 |
| SCPC 2023 본선 대회 후기 (1) | 2023.10.07 |
| SCPC 2023 1차 예선 대회 후기 + 풀이 (0) | 2023.07.30 |
| UCPC 2023 예선 준비 과정 + 대회 후기 (0) | 2023.07.02 |