Expert 달성!
기숙사 생활을 하는 고딩이라 웬만해서는 코포 참여를 할 수가 없다.
그래서 7/29에 방학을 하고 본 첫 번째 라운드였다.
학교에서는 코포 참여를 어렵지만 PS에는 제한이 없다. 수업시간에도 알빠노를 시전하면 그만이다.
수업시간에는 수업에 집중하는 척하고 칠판을 보며 멍 때리듯 풀이를 생각하면 된다.
코포는 코포로 공부해라는 말이 있고 나도 그렇게 생각하기는 하지만,
당연히 백준 문제풀이가 코포 레이팅에 도움이 전혀 되지 않는 것은 아니다.
7월에 학교 시험이 모두 끝나고 할 게 없어서 PS만 주구장창했더니 인간관계를 잃고 실력을 얻었다.
방학하고 바로 블루를 갔으니 뭐 만족한다.
대회 후기
전체 평 : 그렇게 많은 사고를 요하는 셋은 아니었다. D와 E의 난이도 차이가 많이 나서 D까지 빠르게 풀었다면 내 기준 안정권.
https://codeforces.com/contest/1997
$A$ : 00:04 $($+$)$
[ 문제 요약 ]
문자열 $S$가 주어진다. $S$를 타이핑할 때 문자 하나당 2초가 걸리고, 연속된 문자라면 1초가 걸린다. 문자열 $S$에 문자 하나를 추가할 수 있을 때, 타이핑할 때 걸리는 시간을 최대로 걸리게 $S$에 문자 하나를 추가한 문자열을 출력해라.
[ 풀이 ]
그리디하게 연속된 문자가 있다면 그 사이에 다른 문자를 끼워넣고 없으면 아무 자리에 아무 문자나 넣어주면 된다.
[ 코드 ]
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol()
{
string s;
cin>>s;
int flag=0;
for(int i=0;i<s.length();i++)
{
if(flag==0 &&i>0 && s[i]==s[i-1])
{
if(s[i]=='a') cout<<'b';
else cout<<'a';
flag=1;
}
cout<<s[i];
}
if(flag==0)
{
if(s[s.length()-1]=='a') cout<<'b';
else cout<<'a';
}
cout<<'\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
sol();
}
}
$B$ : 00:19 $($+$)$
[ 문제 요약 ]
2행 n열의 문자열이 주어진다. 'x'는 막혀있는 블록이고, '.'은 뚫려있는 블록이다. 입력은 항상 연결된 블록 그룹의 개수가 1개 이하이다. 우리의 목적은 어떤 하나의 블록을 막아 연결된 블록 그룹의 개수가 3개가 되도록 하는 경우의 수를 구하는 것이다.
[ 풀이 ]
어떤 칸을 막아서 연결된 블록 그룹이 3개가 되도록 하려면,
어떤 칸이 1행일 때는 양 옆이 뚫린 . . .상태이며, 2행이 중간만 뚫린 x . x 상태여야 한다.
어떤 칸이 2행일 때는 반대로 양 옆이 뚫린 . . . 상태에, 1행이 중간만 뚫린 x . x 상태여야 한다.
브루트포스로 구현하면 끝.
[ 코드 ]
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s[3];
void sol()
{
int n;
cin>>n;
for(int i=0;i<=1;i++)
cin>>s[i];
int cnt=0;
for(int i=1;i<n-1;i++)
{
if(s[0][i]=='.')
{
if(s[0][i-1]=='x' && s[0][i+1]=='x' && s[1][i]=='.' && s[1][i-1]=='.' && s[1][i+1]=='.')
cnt++;
}
if(s[1][i]=='.')
{
if(s[1][i-1]=='x' && s[1][i+1]=='x' && s[0][i]=='.' && s[0][i-1]=='.' && s[0][i+1]=='.')
cnt++;
}
}
cout<<cnt<<'\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
sol();
}
}
$C$ : 00:33 $($+$)$
[ 문제 요약 ]
괄호와 '_'로 이루어진 문자열이 주어진다. 홀수 번째 문자는 '_'가, 짝수 번째 문자는 여는 괄호나 닫는 괄호가 주어진다. 우리는 '_'에 괄호를 알맞게 넣어서 점수가 최소가 되도록 하면 된다. 물론, 완성된 문자열은 완전 괄호 문자열 $($설명하기 귀찮아서 이렇게 적었는데 뭐 다들 알잘딱할거라 믿는다 ^~^$)$이어야 한다.
점수는 짝지어지는 닫는 괄호와 여는 괄호의 거리 차이의 합으로 계산된다.
[ 풀이 ]
앞에서부터 보면서 그리디하게 '_'에 닫는 괄호를 넣을 수 있다면 넣어주는 것이 항상 최소를 만듦을 알 수 있다.
닫는 괄호를 넣을 수 있는지를 판별하는 것이 관건인데, 일단 앞에서 짝지어 져야할 여는 괄호가 1개 이상 있어야 하고, 이번에 닫는 괄호를 추가했을 때, 총 닫는 괄호의 수가 $($총 문자열의 길이/2$)$보다 작거나 같아야 한다. $($RBS를 이루기 위해$)$
나머지는 다 여는 괄호를 넣어주면 된다.
이렇게 문자열을 구성한 뒤 값을 계산해주면 끝.
[ 코드 ]
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol()
{
string s;
int n;
cin>>n>>s;
int cnt=0;
for(int i=0;i<n;i++) if(s[i]==')') cnt++;
int num=0;
for(int i=0;i<n;i++)
{
if(s[i]=='(') num++;
else if(s[i]==')') num--;
else if(s[i]=='_')
{
if(num && cnt<n/2)
{
cnt++;
num--;
s[i]=')';
}
else
{
s[i]='(';
num++;
}
}
}
stack<int> st;
int res=0;
for(int i=0;i<n;i++)
{
if(s[i]=='(') st.push(i);
else res+=i-st.top(),st.pop();
}
cout<<res<<'\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
sol();
}
}
$D$ : 00:49 $($+1$)$
[ 문제 요약 ]
트리가 주어진다. 트리에서 어떤 정점 하나를 잡았을 때, 그 정점의 모든 자식들의 수를 1씩 빼고 자신의 수를 1 증가시킬 수 있다. 다음과 같은 과정을 여러 번 반복하여 루트 노드 $($1번 노드$)$의 수를 최대화해라. 물론 어떤 노드의 수가 음수가 될 수는 없다.
[ 풀이 ]
루트 노드를 최대로 만들어야 하기 때문에 생각할 것도 없이 자식 노드들을 최대한 많이 뽑아먹으면 된다.
어떤 노드가 자식 노드를 최대로 많이 뽑아먹으려면 자식 노드들의 수의 최솟값이 최대가 되어야 한다. 따라서, dfs를 돌면서 자식 노드의 수의 최솟값보다 작아지지 않을 정도로만 뽑아먹으면 된다.
이렇게 계산하여 루트 노드는 그냥 자식 노드들의 수의 최솟값을 전부 뽑아먹으면 된다.
[ 1틀 ]
루트 노드는 자식 노드들의 최솟값을 전부 빨아먹어야 하는데, 루트 노드도 자식들의 최솟값보다 작아지지 않을 정도로만 뽑아먹어서 1틀했다. 신기하게 안타깝게 예제는 통과하더라고..
[ 코드 ]
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll arr[200010],ch[200010];
vector<int> v[200010];
void dfs(int x)
{
ch[x]=1;
ll mn=(ll)1e16;
for(auto i:v[x])
{
if(ch[i]==0)
{
dfs(i);
mn=min(mn,arr[i]);
}
}
if(mn!=(ll)1e16)
{
if(x==1) arr[x]+=mn;
else if(arr[x]<mn) arr[x]=(arr[x]+mn)/2;
else arr[x]=mn;
}
}
void sol()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
for(int j=2;j<=n;j++)
{
int p;
cin>>p;
v[p].push_back(j);
}
dfs(1);
cout<<arr[1]<<'\n';
fill(ch,ch+n+1,0);
for(int i=1;i<=n;i++)
v[i].clear();
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
sol();
}
}
E 업솔빙 예정.
대회 이후
D까지 너무 빨리 풀고 블루 승급은 넉넉할 것 같아서 그냥 올림픽 보러 갔다.
E가 꽤 난도 있어 보였고, 집중할 자신이 없었기도 하다.
그리고 예상대로 블루를 찍을 수가 있었다.
덕분에 출제 조건을 만족해서 지금 준비하고 있는 대회에서 내 이름 걸고 문제를 출제할 수 있게 되었다!
이제 시작이다.
일단 8월 안에 퍼플은 찍는 것이 목표이기에 버츄얼도 치면서 열심히 공부해야겠다.
근거없는 자신감을 드러내 보자면, 오렌지까지는 이대로 가면 쭉쭉 올라갈 듯? ㅋㅋ
얘는 진짜 맞아야 정신을 차림
