2021 SCPC 2차 예선 풀이
들어가며
1차 예선을 통과한 만큼 오랜만에 본선에 진출하여 기념품을 받고자 약속도 날을 피해서 잡았다. 주말이지만 아침에 알람까지 맞춰놓고 일어났다. 전날에 일찍 자고자 했지만 노느라 실패해서 상당히 피곤한 상태이기는 했다. 핸드폰으로 문제를 일단 먼저 쭉 읽었는데 꽤 재밌어 보였다. 5번은 Output Only였고 4번은 뭔가 Aho-Corasick 같은 느낌으로 될 것도 같았다.
1. 원 안의 점
축에 있는 점들만 중복으로 안 세도록 잘 처리해주고, 원점만 더해주면 된다. 나는 제1사분면 기준 X축 양수 방향에 있는 점을 셌다. \(O(R)\)
처음에 "Case #x" 부분 안 찍어서 1번 틀렸다.
SCPC2021R2Q1.cpp
#include<iostream>
using namespace std;
#include<math.h>
int t;
long long n,out;
int main()
{
int i;
long long x,y2,y;
cin>>t;
for(i=1;i<=t;++i)
{
cin>>n;
out=0;
for(x=1;x<n;++x)
{
y2=n*n-x*x;
y=sqrt(y2);
if(y*y==y2)y--;
out=out+y+1;
}
cout<<"Case #"<<i<<endl<<out*4+1<<endl;
}
return 0;
}3. 산탄총
본 풀이에 앞서, 실수를 좀 많이 했고, 디버깅도 쉽지 않아서 일단 작은 데이터에 대해 Brute Force로 무조건 정확한 답을 찾는 코드를 하나 짰다. 부분점수를 받는 것으로 검증해야 하는데 여기서조차도 자꾸 실수해서 한 3번 제출 횟수를 날렸다.
SCPC2021R2Q3_bf.cpp
#include<iostream>
using namespace std;
int t,n,m;
long long a[610][610],out;
inline long long getA(int r,int c)
{
if(r>=1&&r<=n&&c>=1&&c<=n)return a[r][c];
return 0;
}
inline int absi(int a)
{
if(a>0)return a;
return -a;
}
int main()
{
int i,j,k,r,c,d;
long long now;
cin>>t;
for(i=1;i<=t;++i)
{
cin>>n>>m;
for(j=1;j<=n;++j)for(k=1;k<=n;++k)cin>>a[j][k];
if(n>50)
{
cout<<"Case #"<<i<<endl<<"-1"<<endl;
continue;
}
out=0;
for(j=1-(m-1);j<=n+(m-1);++j)
{
for(k=1-(m-1);k<=n+(m-1);++k)
{
now=0;
for(r=j-(m-1);r<=j+(m-1);++r)
{
for(c=k-(m-1);c<=k+(m-1);++c)
{
d=absi(r-j)+absi(c-k);
if(d>=m)continue;
now=now+(m-d)*getA(r,c);
}
}
if(now>out)out=now;
}
}
cout<<"Case #"<<i<<endl<<out<<endl;
}
return 0;
}이제 이 코드를 바탕으로 정해 코드를 검증하기 위한 Data Maker를 만들었다. 작은 N에 대해 틀리는 경우가 나오면 이때 만들어진 데이터를 가지고 디버깅을 해볼 수 있다.
system으로 부르는 실행 파일 중 wcmp.exe를 컴파일하기 위해서는 wcmp.cpp와 testlib.h가 필요하다. 옛날에는 토큰 비교하는 것도 다 직접 짰었는데 polygon 쓰면서 배워온 testlib 쓰니까 편하다.
SCPC2021R2Q3_dm.cpp
#include<iostream>
using namespace std;
#include<stdio.h>
int t=3,n,m;
FILE*fout;
int main()
{
int i,j,k;
srand(970525);
system("g++ -O2 SCPC2021R2Q3.cpp -o SCPC2021R2Q3.exe");
system("g++ -O2 SCPC2021R2Q3_bf.cpp -o SCPC2021R2Q3_bf.exe");
while(1)
{
fout=fopen("input.txt","w");
fprintf(fout,"%d\n",t);
for(i=1;i<=t;++i)
{
n=rand()%3+1;
m=rand()%n+1;
fprintf(fout,"%d %d\n",n,m);
for(j=1;j<=n;++j)for(k=1;k<=n;++k)fprintf(fout,"%d%s",rand()%201-100,k<n?" ":"\n");
}
fclose(fout);
system("SCPC2021R2Q3.exe <input.txt >output.txt");
system("SCPC2021R2Q3_bf.exe <input.txt >output_bf.txt");
if(system("wcmp.exe input.txt output.txt output_bf.txt"))break;
}
}// TODO
SCPC2021R2Q3.cpp
#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
int t,n,m,n2,n3,n5,n2m;
long long a[610][610],s[1810][3010],h[1810][1810],v[1810][1810],out;
inline long long getS(int r,int c)
{
r=r-n;
c=c+n;
if(r>=1&&r<=n3&&c>=1&&c<=n5)return s[r][c];
return 0;
}
int main()
{
int i,j,k,x,y;
scanf("%d",&t);
for(i=1;i<=t;++i)
{
scanf("%d%d",&n,&m);
for(j=1;j<=n;++j)for(k=1;k<=n;++k)scanf("%lld",&a[j][k]);
n2=n*2;
n3=n*3;
n5=n*5;
n2m=n2+m;
for(j=1;j<=n3;++j)
{
for(k=1;k<=n5;++k)
{
if(j<=n&&k>n2&&k<=n3)s[j][k]=a[j][k-n2];
else s[j][k]=0;
s[j][k]=s[j][k]+s[j-1][k-1]+s[j-1][k+1];
if(j>=2)s[j][k]=s[j][k]-s[j-2][k];
}
}
memset(h,0,sizeof(h));
for(j=n+1;j<=n3;++j)
{
for(k=1;k<=m;++k)h[j][1]=h[j][1]+(2-(k==m))*(getS(j,1-k)+getS(j,1+k));
for(k=2;k<=n3;++k)h[j][k]=h[j][k-1]+getS(j,k+m-1)+getS(j,k+m)-getS(j,k-m-1)-getS(j,k-m)+2*getS(j,k-1)-2*getS(j,k);
}
for(k=1;k<=n3;++k)for(j=1;j<=n3;++j)v[j][k]=v[j-1][k]+getS(j+m-1,k)+getS(j+m,k)-getS(j-m-1,k)-getS(j-m,k)+2*getS(j-1,k)-2*getS(j,k);
out=0;
for(j=n+1-(m-1);j<n2m;++j)
{
x=n+1-(m-1);
y=n2m-1;
if(j<=n)
{
x=x+(n+1-j);
y=y-(n+1-j);
}
if(j>n2)
{
x=x+(j-n2);
y=y-(j-n2);
}
for(k=x;k<=y;++k)if(-h[j-1][k]+v[j-1][k]>=out)out=-h[j-1][k]+v[j-1][k];
}
printf("Case #%d\n%lld\n",i,out);
}
return 0;
}2. 직8각형
처음에는 각 꼭짓점을 어떻게 정하나 싶었다. \(8!\)을 다 해볼까 했는데 그래도 어떻게 최적화할지 잘 안 떠올랐다. 긴 세로 직사각형과 긴 가로 직사각형 두 파트로 잘라서 생각해보고, 거기서 또 위쪽/아래쪽, 왼쪽/오른쪽을 나눠서 생각해보니 그림이 좀 그려졌다. 그 후 중심 좌표에 따른 Convex Function에서 최저점을 찾으면 될 것으로 생각했다. 3번을 짜고 나니 좀 힘이 빠져있는 상태였고 당장 떠오르는 구현 방법도 너무 귀찮았기에, 피곤해서 좀 잤다.
// TODO
SCPC2021R2Q2.cpp
#include<iostream>
using namespace std;
#include<algorithm>
int t,n,out,p[10],bcnt[110],hc[10]={0,0,0,1,2,3,3,1,2},vc[10]={0,0,1,2,2,0,1,-1,-1},h[10],v[10];
pair<int,int> a[10],b[10][10];
inline int absi(int a)
{
if(a>0)return a;
return -a;
}
int main()
{
int i,j,k,pos,now;
cin>>t;
for(i=1;i<=t;++i)
{
cin>>n;
for(j=1;j<=8;++j)
{
cin>>a[j].first>>a[j].second;
p[j]=(j+1)/2;
}
out=1999999999;
do
{
for(j=1;j<=4;++j)bcnt[j]=0;
for(j=1;j<=8;++j)b[p[j]][++bcnt[p[j]]]=a[j];
if(b[1][1].second>b[1][2].second)swap(b[1][1],b[1][2]);
if(b[2][1].first>b[2][2].first)swap(b[2][1],b[2][2]);
if(b[3][1].second>b[3][2].second)swap(b[3][1],b[3][2]);
if(b[4][1].first>b[4][2].first)swap(b[4][1],b[4][2]);
pos=0;
for(j=1;j<=4;++j)
{
for(k=1;k<=2;++k)
{
pos++;
h[pos]=b[j][k].first-hc[pos]*n;
v[pos]=b[j][k].second-vc[pos]*n;
}
}
sort(&h[1],&h[9]);
sort(&v[1],&v[9]);
now=0;
pos=0;
for(j=1;j<=4;++j)for(k=1;k<=2;++k)now=now+absi(h[4]+hc[(j-1)*2+k]*n-b[j][k].first)+absi(v[4]+vc[(j-1)*2+k]*n-b[j][k].second);
if(now<out)out=now;
}while(next_permutation(&p[1],&p[9]));
cout<<"Case #"<<i<<endl<<out<<endl;
}
return 0;
}결과
600/1000, 2560x1080 화면에서 찍었다. 옛날 글을 찾아보면 노트북 1366x768 화면에서 찍은 것도 보이는데 많이 달라졌다.
대회 시간 자체는 길었지만, 중간에 낮잠도 자고 올림픽 야구도 보니 4번을 긁거나 5번을 제대로 생각할 여유가 딱히 없었다. 특히 3번의 제출 횟수가 좀 많아서 순위 결정 기준에 따라 삐끗할 수도 있을 것 같은데 제발 본선 가면 좋겠다. 아직 죽지 않았다고 증명하고 싶다.
1차 예선과 2차 예선 코드를 다시 살펴보니, 그동안 Java로 다른 사람도 읽기 쉽게 하는 개발을 좀 했는데도 오랜만에 PS 코딩 스타일이 그대로 나타났다. 아직은 읽을만하다.
2021-08-13 추가
탈락했다. 들리는 이야기로는 600점보다는 높은 점수가 커트였다고 하던데, 시간 배분 등의 문제로 나머지를 긁지 않은 잘못이 컸다.
본선 인원수도 찾아보니 100명 초반대인 것 같아서 이미 3번의 만점자가 120명을 넘은 상황에서 너무 안일했다.
풀이 작성에 좀 시간이 걸리다 보니 미뤄두고 있었는데 심지어 떨어지기까지 해서 원동력을 조금 잃었다.
다른 대회라도 언젠가 좋은 결과를 다시 한번 내보고 싶다.