티스토리를 처음 시작했는데 후기라도 올려보자 싶어서 인생 처음으로 한 코드포스 후기를 올려봄
A - Hotelier
걍 대충 짜라고 만든 문제. 쉽다.
#include
char ch[100005];
int stt[10];
int main()
{
int n,i,j;
scanf("%d\n%s", &n,ch);
for(i=0;i<n;i++)
{
if(ch[i]=='L')
{
for(j=0;j<10;j++)
if(stt[j]==0)
break;
stt[j]=1;
}
else if(ch[i]=='R')
{
for(j=9;j>=0;j--)
if(stt[j]==0)
break;
stt[j]=1;
}
else
stt[ch[i]-'0']=0;
}
for(i=0;i<10;i++)
printf("%d", stt[i]);
return 0;
}
B - Block Advecture
현 위치에서 최대한 많이 블록을 얻고 현재 있는 곳이 다음 칸보다 k이상 낮을 때만 블록을 놓으면 되는 문제. 그리디.
그렇게 해서 되면 YES, 안되면 NO를 출력하면 된다.
#include
int arr[105];
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n,m,k;
scanf("%d%d%d", &n,&m,&k);
int i;
for(i=1;i<=n;i++)
scanf("%d", &arr[i]);
for(i=1;i<n;i++)
{
if(arr[i]+k<arr[i+1])
{
m-=(arr[i+1]-k-arr[i]);
if(m<0) break;
}
else if(arr[i+1]-k<=0)
m+=arr[i];
else
m+=(arr[i]-(arr[i+1]-k));
}
if(i<n) printf("NO\n");
else printf("YES\n");
}
return 0;
}
C - Round Corridor
안쪽과 바깥쪽 벽이 만나는 곳은 n,m의 최대공약수의 배수 칸에서만 만난다. n,m 최대공약수 구하고 쿼리 들어오면 적당히 나눠줘서 두 구역 사이에 벽이 있는지 없는지 따져주면 된다.
#include
#define ll long long
ll n,m,q;
ll gcd(ll a,ll b)
{
if(a%b==0) return b;
return gcd(b,a%b);
}
ll sect(int inout,ll a)
{
if(inout==1)
return (a-1)/n;
else
return (a-1)/m;
}
int main()
{
scanf("%lld%lld%lld", &n,&m,&q);
ll g=gcd(n,m);
n/=g;
m/=g;
for(int i=0;i<q;i++)
{
ll a,b,c,d;
scanf("%lld%lld%lld%lld", &a,&b,&c,&d);
ll fst=sect(a,b);
ll scd=sect(c,d);
if(fst==scd) printf("YES\n");
else printf("NO\n");
}
return 0;
}
D - White Lines
설명하기 귀찮은데...
#include
char ch[2005][2005];
int krow[2005][2005];
int kcol[2005][2005];
int rowb[2005];
int colb[2005];
int wrow[2005][2005];
int wcol[2005][2005];
int main()
{
int n,k,i,j;
scanf("%d%d", &n,&k);
for(i=1;i<=n;i++)
scanf("\n%s", ch[i]+1);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
int a=(ch[i][j]=='B');
rowb[i]+=a;
colb[j]+=a;
}
}
for(i=1;i<=n;i++)
{
kcol[i][n]=(ch[i][n]=='B');
for(j=n-1;(n-j)<k;j--)
kcol[i][j]=kcol[i][j+1]+(ch[i][j]=='B');
for(;j>0;j--)
kcol[i][j]=kcol[i][j+1]+(ch[i][j]=='B')-(ch[i][j+k]=='B');
}
for(i=1;i<=n;i++)
{
krow[n][i]=(ch[n][i]=='B');
for(j=n-1;(n-j)<k;j--)
krow[j][i]=krow[j+1][i]+(ch[j][i]=='B');
for(;j>0;j--)
krow[j][i]=krow[j+1][i]+(ch[j][i]=='B')-(ch[j+k][i]=='B');
}
for(i=1;i<=n-k+1;i++)
{
for(j=1;j<=k;j++)
wcol[i][1]+=(krow[i][j]==colb[j] && colb[j]!=0);
for(;j<=n;j++)
wcol[i][j-k+1]=wcol[i][j-k]-(krow[i][j-k]==colb[j-k] && colb[j-k]!=0)+(krow[i][j]==colb[j] && colb[j]!=0);
}
for(j=1;j<=n-k+1;j++)
{
for(i=1;i<=k;i++)
wrow[1][j]+=(kcol[i][j]==rowb[i] && rowb[i]!=0);
for(;i<=n;i++)
wrow[i-k+1][j]=wrow[i-k][j]-(kcol[i-k][j]==rowb[i-k] && rowb[i-k]!=0)+(kcol[i][j]==rowb[i] && rowb[i]!=0);
}
int ans=0;
for(i=1;i<=n-k+1;i++)
for(j=1;j<=n-k+1;j++)
{
//printf("%d %d %d %d %d %d %d %d\n", i,j,krow[i][j],kcol[i][j],colb[j],rowb[i],wrow[i][j],wcol[i][j]);
if(ans<wrow[i][j]+wcol[i][j])
{
ans=wrow[i][j]+wcol[i][j];
}
}
for(i=1;i<=n;i++)
ans+=(colb[i]==0)+(rowb[i]==0);
printf("%d\n", ans);
return 0;
}
E - Compress Words
KMP쓰는 문제. 풀었는데 아쉽게도 정답 코드를 제출하지 못했다.
#include
#include
int arr[1000006];
char ch[1000005];
char ha[1000005];
int main()
{
int n,i;
scanf("%d\n%s", &n,ch);
int len=strlen(ch);
for(i=1;i<n;i++)
{
int j;
scanf(" %s", ha);
int l=strlen(ha);
int lft=0;
arr[0]=-1;
for(j=1;j<l;j++)
{
while(lft!=-1 && ha[j]!=ha[lft])
lft=arr[lft];
arr[j]=lft;
lft++;
}
j=n-l-1;
if(j<0) j=0;
lft=0;
for(;j<len;j++)
{
while(lft!=-1 && ch[j]!=ha[lft])
lft=arr[lft];
lft++;
}
j=lft;
for(;lft<l;lft++)
ch[len-j+lft]=ha[lft];
len+=l-j;
}
ch[len]=0;
printf("%s\n", ch);
return 0;
}
근데 이 코드 문제있음
3
ooi ioo oioo에서
원래는 ooioo가 나와야 되는데
ooioooioo가 나옴.
F - 문제 읽지도 못하고 끝남
*위 코드들에서 주석 처리해놓은 printf는 대회 중 디버깅 용으로 넣은 것. 딱히 중요하진 않다.
한국인이 연 대회라 그런지 시간대도 적절하고 이름도 친숙해서 좋았던 것 같다.
아닌가? 생각해보면 아무개, 길동은 그닥 친숙한 이름은 아니다. 정정.
E를 풀 수 있는데 시간이 없었던 것이 조금 아쉽긴 한데 처음 보는 시험 치고는 좋은 결과인 것 같다.