이 글은 Oler의 대회 후기이며, 추후 상세한 수정이 있을 예정입니다.
참고: 특별한 사정으로 인해 시험 당일에 후기를 작성하지 못해 아쉬움이 큽니다.
업데이트 (2023-11-20): 합격선이 발표되었는데, 간신히 일반전형 1차 합격선에 들었습니다.
시험 전날
"마지막 밤이니 템플릿이나 외우자"
템플릿 몇 개를 외웠다... (시험장에서 하나도 사용하지 못함)
"정신을 위해 일찍 자야지, 안 돼, 밤새워야 해, NBA 워리어스 뉴스나 봐야지..."
10:00에는 불 끄고 자야겠다.
시험 당일
오전
정상적으로 기상했고, 기분은 좋았다. 간단하게 동태를 올려 "행운을 빈다"고 했다.
아침 식사로 국수 한 그릇과 만두 여덟 개, 우유 한 병을 마시고 smzx 시험장으로 향했다. 바람이 많이 부는 느낌이었다.
시험장에 도착하니 이미 고수 myz가 기다리고 있었다. 올해 문제 난이도에 대해 가볍게 대화를 나누었다.
이어서 ljs, xzk, zsw, hk, lsy, yyh 등 다른 고수들이 차례로 도착했다.
고수들과 인사를 나눈 뒤 시험실로 들어갔다.
C++ 기초 리그 (普及组)
8:27 폴더 압축을 풀고 바로 문제를 보았다.
8:30 시험이 공식적으로 시작되었다. 문제 풀이 순서는 T1-T2-T4-T3였다.
T1 apple
문제 풀이 시간: 8:30-9:00
소요 시간: 약 30분
쉬운 문제이니 무조건 풀어야 했다. 첫눈에 보기에는 규칙을 찾는 문제 같았다. 20분 동안 규칙을 찾지 못해 시간을 확인하고, 일단 무식한 방법으로 풀어보기로 했다. 코드를 작성해보니 바로 통과되었고, 복잡도는 O(log_3 n)이었다. 큰 예제도 통과되어 빠르게 넘어갔다.
기대 점수: +100점
실제 점수: +100점
T2 road
문제 풀이 시간: 9:00-9:40
소요 시간: 약 40분
문제를 보니 DP나 탐욕법 같았다. 데이터 범위를 보니 1e5라 DP 상태 정의가 떠오르지 않아 잠시 DP는 접어두고 탐욕법을 생각했다.
간단하게 생각한 탐욕법은, 이동하면서 최솟값을 취하고 그 기여도를 계산하여 더하는 방식이었다. 10분 만에 코드를 작성했다.
이때 재미있는 일이 발생했다. 문제 순서대로 큰 데이터를 취하는데, 문제 이름을 제대로 보지 않고 버스(bus) 데이터의 큰 것을 잘못 가져왔다. 30분 동안 원인을 찾지 못하다가 잘못된 데이터를 사용했다는 것을 깨달았다. 원래 데이터를 가져오니 쉽게 통과되었고, 시간 복잡도는 O(n^2)이었다. 시간이 많지 않아 빠르게 넘어갔다.
기대 점수: +100점
실제 점수: +100점
T3 uqe
문제 풀이 시간: 10:30-11:57
소요 시간: 약 90분
큰 시뮬레이션 문제라 마지막에 풀기로 했다. 이때 1시간 30분이 남아있었다. 차분하게 문제를 풀었고, 완성 후 10분이 남았다. 예제를 테스트했는데 몇 개가 틀렸다. 문제를 발견했을 때는 11:54였고, 11:57에 답안 제출이 마감되어 3분밖에 남지 않았다. 당황하여 절반만 수정하고 미완성된 코드를 제출했다.
기대 점수: +50점
실제 점수: +10점
T4 bus
문제 풀이 시간: 9:40-10:30
소요 시간: 약 60분
시험 전에 마지막 문제는 DP 문제일 것이라고 예상했지만, 최단 경로 문제가 나왔다. 첫 번째 생각은 특성을 파악하고 Dijkstra 알고리즘으로 최단 경로를 찾는 것이었다. 약간의 특성을 발견했는데, 이동 경로의 길이가 k의 배수여야 한다는 것이었다. 하지만 계층 그래프를 생각하지 못하고 BFS로 무식하게 풀어 T3로 넘어갔다.
기대 점수: +10점
실제 점수: 0점
시험장을 나서니 머릿속이 하얘졌다. 많은 고수들이 3문제를 풀었다고 들었다. myz와 xzk는 모두 풀었다 (예상대로였다).
나는 고작 두 문제만 풀었고, 3번 문제의 결과는 불확실했다 (자신감이 떨어졌다).
점심
smzx 식당에서 간단히 점심을 먹었고, 여러 고수들과 토론하면서 시험 중에 텍스트 파일을 새로 만들고 NOI Linux를 실행하는 것을 잊었다는 것을 깨달았다. (애도!)
멘탈이 무너졌지만, 이전 대회 경험 덕분에 크게 개의치 않고 편안하게 잠들었다.
오후
1:40에 깨어났고, 몽롱한 상태로 위층으로 올라갔다. 아직 시험장에 들어갈 수 없었다. 잠시 정신을 차리고 고수들에게 인사하며 운을 빌었다.
2:05 시험장에 입장했고, 좌석에 앉아 신들께 기도했다. 나에게 돌아온 것은...
C++ 고급 리그 (提高组)
오전에 시험을 망쳤다. 올해의 노력이 이 마지막 경기에 달려 있었다. 배수진을 쳤다...
2:30 고급 시험이 시작되었다.
문제 풀이 순서는 T1-T2-T3-T4로, 비교적 여유로운 순서였다.
T1 lock
문제 풀이 시간: 2:30-3:00
소요 시간: 약 30분
첫 문제는 너무 쉽지 않을 것이라고 생각했지만, 역시 첫 문제였기에 신중하게 풀어야 했다. 바로 연습장에 특성을 찾기 시작했다. 데이터 범위를 보니 n ≤ 8이었고, 비밀번호 자물쇠는 5자리였다. 모든 경우의 수를 탐색해도 될 것 같았다. 코드를 작성해보니 모든 예제를 통과했다. 기초 리그 T1보다 쉬운 것 아닌가? (물론 문제를 너무 복잡하게 생각해서 시간을 낭비했다.)
기대 점수: +100점
실제 점수: +100점
작은 삽화 I
T3 문제의 예제 설명에 오류가 있었다. 수정되었다... (아쉽게도 나는 별로 신경 쓰지 않았다.)
T2 game
문제 풀이 시간: 3:00-3:20
소요 시간: 약 20분
문제를 보자마자 zsq가 자주 내는 "구간 DP" 문제와 비슷하다고 생각했다. 데이터 범위를 보니 n ≤ 2 × 10^5라 구간 DP로는 최대 35점 정도밖에 얻지 못할 것 같았다. 다른 방법을 찾아보기로 했다.
갑자기 시험 며칠 전 고수들이 구간 문제에 대해 정리한 것을 본 것이 생각났다. fi를 시작 또는 끝으로 정의하는 상태를 설정하고, 문제에 적용해보니 last_i를 사용하여 현재 문자가 앞에 마지막으로 나타난 위치를 기록하고 스택으로 관리하면 될 것 같았다. 이 정도 생각했으면 조금 더 노력하면 정답을 찾을 수 있었을 텐데, 그때는 머리가 멍해져서 최적화를 생각하지 못했다 (실패했다). 결국 O(n^2)으로 50점 정도만 얻기로 하고, 코드는 간단하게 10분 만에 해결했다. 이 문제는 더 이상 신경 쓰지 않고 넘어갔다.
기대 점수: +50점
실제 점수: +50점
T3 struct
문제 풀이 시간: 3:20-4:55
소요 시간: 약 100분
나에게는 어려운 대형 시뮬레이션 문제였다. 시간이 충분했기에 최대한 높은 점수를 얻고 싶었다. 처음에는 정답을 바로 풀려고 시도했지만, 40분 후에 막혔다. 특수 조건 ABCD를 보니, 내가 작성한 프로그램을 수정하면 모두 해결할 수 있을 것 같았다. 그래서 방향을 바꾸어 특수 조건에 집중하기로 했다. 약 45분 동안 수정한 결과, 공식적으로 특수 조건에 대한 데이터가 제공되지 않아 직접 데이터를 만들었고, 10분 만에 모두 통과되었다. 자신감이 넘쳤다... 하지만 큰 문제를 간과했다. 시험 중에 문제가 수정되었고, 시험장에서 시험 시작 직후 수정 사항이 공지되었지만, 그때 나는 T1을 풀고 있었고, 이후에는 별로 신경 쓰지 않고 주의 깊게 문제를 읽지 않았다. 예제 설명대로 코드를 작성하여 결국 0점을 받았다. (너무 슬펐다...)
기대 점수: +80점
실제 점수: 0점
작은 삽화 II
시간: 4:55-5:05
소요 시간: 약 10분
5시까지 시간이 좀 남아 있었다. 오전 경험과 점심 시간에 고수들에게 조언을 들은 덕분에 NOI Linux를 실행하고 정보 관련 텍스트 파일을 작성했다. 마음이 좀 놓였다.
NOI Linux에서 앞의 세 문제 프로그램은 문법 오류가 없었다. 그래서 T4로 넘어갔다.
T4 tree
문제 풀이 시간: 5:05-6:20
소요 시간: 약 80분
올해 가장 많이 공부한 것이 그래프 이론이었다. 그래프 문제라니! (하지만 나는 풀지 못했다...) 처음에는 이 문제에 대한 약간의 희망을 가졌지만, 곧 현실을 깨달았다. 이 문제는 현재 내 실력으로는 풀 수 없다는 것을. 그래서 특수 조건만 보기로 했다. 특수 조건의 그래프는 그리기가 쉬웠고, 식을 유도하거나 그래프를 한 번 탐색하여 일부 점수를 얻을 수 있을 것이라고 생각했다. 하지만 너무 쉽게 생각했고, 특수 조건도 유도하기 어려웠다. 결국 1시간 20분 동안 아무것도 하지 못했다. 마지막에는 무식한 방법과 두 개의 틀린 특수 조건 해법만 제출했다. (기초 리그 마지막 두 문제와 상황이 비슷했다...)
기대 점수: [0, 10]점
실제 점수: 0점
마지막 문제를 풀 때 컨디션이 좋지 않았던 것 같다. 그렇지 않았다면 부분 점수라도 얻었을 것이다.
작은 삽화 III
이제야 검토할 시간을 충분히 확보했다. 검토 후 자리에 앉아 예상 점수와 올해 합격선을 계산해 보았다.
6:27 시험 종료, 답안 제출 마감.
하루의 시험이 마침내 끝났다. 가벼운 마음으로 시험장을 나왔을 때는 이미 어두워져 있었다. 작년과 같은 느낌이었다...
myz와 ljs 두 신은 거의 3시간 만에 두 번째 문제를 풀고 두 문제를 맞혔다. 정말 존경스럽다.
저녁
밖에 나가서 맛있는 저녁을 먹었고, 3시간 동안 쇼핑몰을 돌아다니다가 새 신발을 샀다. (기분이 좋았다...)
집에 돌아오니 학교 정보 그룹 채팅방이 활발했다. 그래서 예상 점수를 계산해 보았다...
시험 후 요약
기초 리그 (J)
예상 점수: 100 + 100 + 50 + 10 = 260점
실제 점수: 100 + 100 + 10 + 0 = 210점
2등 안에 들지 못했다 (5점 차이!!! 망했다...)
업데이트: 간신히 1등 안에 들었다...
먼저, 시험 중의 정신 상태에 약간 문제가 있었다. 아침에는 뇌가 덜 깨어 있었던 것 같다. 상태가 좋지 않았다.
첫 번째 문제의 사고 방향이 잘못되었다. 두 번째 문제에서는 큰 데이터를 잘못 가져와 시간을 낭비했다. 이런 실수는 하지 말았어야 했다.
세 번째 문제는 시험 후 30분 동안 수정해도 원래 코드를 완성하지 못했다. hk의 설명을 듣고 나서야 시험 중에 너무 복잡하게 생각했고, 단순화하지 않고 바로 해결하려고 했다는 것을 알게 되었다. 결국 코드를 재구성해야 했다. (두 번째 문제에서 시간을 덜 썼더라도 원래 코드를 완성하지 못했을 것이다. 반성해야 한다.)
네 번째 문제에서 시험 중에 -1을 출력했으면 5점을 얻을 수 있었다. 그랬다면 1등 안에 들었을 텐데... (아쉽다)
본론으로 돌아가서, 네 번째 문제는 이론적으로 시험 중에 풀었어야 했다. 시험은 끝났지만 원인을 분석해야 한다. 첫째, Dijkstra 알고리즘은 생각했지만, k의 배수 문제에서 (k mod %)를 먼저 생각해야 한다는 것을 잊었다. (시험 전에 배수 문제에서 정리했던 것을 시험 중에 잊었다...) 간단히 말하면, 계층 그래프였다... 아아아!!!
고급 리그 (S)
예상 점수: 100 + 50 + 80 + [0, 10] = 230점
실제 점수: 100 + 50 + 0 + 0 = 150점
아슬아슬하게 1등 안에 들었다... (드디어 녹색 체크를 벗어날 수 있겠다)
주황색 1개, 파란색 3개, 이론상 아크
첫 번째 문제는 주황색 난이도였고 30분 만에 풀었다. (고급 리그 난이도에 대한 작은 추측 덕분이다) 괜찮았다. 더 이상 말할 필요가 없다...
두 번째 문제는 할 말이 많다. 이 문제는 매칭 스택과 해싱으로 풀 수 있었다. 하지만 여름 방학 때 이 주제를 딱 다뤘었다 (매칭 스택은 다루지 않았지만). 깊은 감명을 받았기에 아쉬웠다...
두 번째 문제에서 다른 정답을 생각해냈는데, 최적화하면 통과할 수 있었다. 시험 전에 비슷한 유형의 문제를 풀었기 때문에 알 수 있었다. 유명 고수의 해설을 보고 정리한 내용이었다. 하지만 최적화 방법을 떠올리지 못해, 안전하게 50점짜리 부분만 얻었다. 시험 후 zsw의 분석을 통해 어떻게 최적화하는지 알게 되었다... (myz, ljs 두 고수는 최적화하지 않은 방법으로 문제를 풀었다고 들었다.)
강조!! 세 번째 문제는 대형 시뮬레이션에 너무 몰두한 나머지, 수정 사항을 확인하는 것을 잊었다!!!
결과는 예상대로였다. 80점에서 0점으로 떨어졌다. 이걸 교훈 삼아 스스로에게 경고해야겠다... 이 문제에 대해서는 더 이상 말하고 싶지 않다 (대형 시뮬레이션)...
네 번째 문제는 또 아쉬웠다. 어떤 이유인지 모르겠지만, 시험 중에 작성한 less는 원래 최대 힙이어야 하는데, 프로그램은 항상 최소 힙 결과를 출력했다. 내 프로그램 문제라고 생각했다... 25점에서 0점으로 떨어졌다. (또, 또, xzk는 우선순위 큐를 제대로 사용했지만 5점밖에 얻지 못해 1등을 놓쳤다고 들었다. 안타깝다... 그리고 고수 ljs는 비슷한 아이디어를 가지고 있었지만, 시험 중에 실수로 코드가 잘못되어 1점도 얻지 못했다고 한다.)
총괄 요약
요약하자면, 시험 중에 나는 계속 바보 같았다. 절대 스스로를 용서할 수 없다!!!
또한 시험 정신 상태와 문제 풀이 전략이 매우 중요했다. 결국 평소 연습 습관이 부족했기 때문이었다. 습관부터 바로잡아야 한다...
가장 중요한 점은 실력이 부족하다는 것이다. 배운 것을 제대로 활용하지 못한다. 더 열심히 해야 한다...
번외
시험 프로그램 복원
이 부분은 건너뛸 수 있다. 뒤에 내가 작성한 문제 해설이 있다.
참고: 시험 압축 파일에서 가져왔으며, 수정 흔적이 없다...
기초 리그 J - 210점
T1 apple - 100점
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t,ans,res=-1;
signed main() {
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
scanf("%lld",&n);
int x=n;
while(t!=n) {
int tem=(x-1)/3+1;
if(x%3==1&&res==-1)
res=ans+1;
t+=tem,x-=tem,ans++;
}
printf("%lld %lld\n",ans,res);
return 0;
}
T2 road - 100점
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,d,v[N],a[N];
signed main() {
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
scanf("%lld%lld",&n,&d);
for(int i=1;i<n;i++)
scanf("%lld",&v[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
int ans=0,minx=a[1],p=v[1],t=0;
for(int i=2;i<n;i++) {
if(a[i]<minx) {;
ans+=minx*((p-t-1)/d+1);
int tem2=t;
t=((p-t-1)/d+1)*d+tem2-p;
minx=a[i];
p=0;
}
p+=v[i];
}
ans+=minx*((p-t-1)/d+1);
printf("%lld\n",ans);
return 0;
}
T3 uqe - 10점
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int t,m,a,b,c;
int pri[N];
map<int,int> mp;
signed main() {
freopen("uqe.in","r",stdin);
freopen("uqe.out","w",stdout);
scanf("%lld%lld",&t,&m);
for(int i=1;i<=m;i++)
pri[i]=i*i,mp[i*i]=i;
for(int i=1;i<=t;i++) {
scanf("%lld%lld%lld",&a,&b,&c);
int tem=b*b-4*a*c;
if(tem<0) printf("NO\n");
else {
int x1=(-b+sqrt(tem));
int x2=(-b-sqrt(tem));
// cout<<x1<<" "<<x2<<"\n";
if(x1>x2) {
int t=sqrt(tem);
if(t*t==tem) {
// cout<<-b+t<<"\n";
int p=-b+t,q=2*a;
int pp=p,qq=q;
if(p<0) p=-p;
if(q<0) q=-q;
int gc=__gcd(p,q);
p/=gc,q/=gc;
if(pp<0) p=-p;
if(qq<0) q=-q;
if(p==0) printf("0\n");
else if(q==1) printf("%lld\n",p);
else printf("%lld/%lld\n",p,q);
} else {
int p=-b,q=tem,x=0;
int pp=p,qq=q;
if(p<0) p=-p;
if(q<0) q=-q;
int gc=__gcd(p,a);
p/=gc;
gc=__gcd(q,a);
q/=gc;
if(pp<0) p=-p;
if(qq<0) q=-q;
for(int j=2;j<=sqrt(tem);j++)
if(tem%(j*j)==0)
x=j;
if(p==0) {
if(x==0) printf("sqrt(%lld)/2\n",q);
else {
if(x%2==0) printf("%lld*sqrt(%lld)\n",x/2,tem/x/x);
else {
if(x==1) printf("sqrt(%lld)/2\n",tem/x/x);
else printf("%lld*sqrt(%lld)/2\n",x,tem/x/x);
}
}
} else {
if(p%2==0) {
if(x==0) printf("%lld+sqrt(%lld)/2\n",p/2,q);
else {
if(x%2==0) printf("%lld+%lld*sqrt(%lld)\n",p/2,x/2,tem/x/x);
else {
if(x==1) printf("%lld+sqrt(%lld)/2\n",p/2,tem/x/x);
else printf("%lld+%lld*sqrt(%lld)/2\n",p/2,x,tem/x/x);
}
}
} else {
if(x==0) printf("%lld/2+sqrt(%lld)/2\n",p,q);
else {
if(x%2==0) printf("%lld+%lld*sqrt(%lld)/2\n",p,x/2,tem/x/x);
else {
if(x==1) printf("%lld/2+sqrt(%lld)/2\n",p,tem/x/x);
else printf("%lld/2+%lld*sqrt(%lld)/2\n",p,x,tem/x/x);
}
}
}
}
// printf("%lld/2+sqrt(%lld)/2\n",p);
}
} else {
int t=sqrt(tem);
if(t*t==tem) {
int p=-b-t,q=2*a;
int pp=p,qq=q;
if(p<0) p=-p;
if(q<0) q=-q;
int gc=__gcd(p,q);
p/=gc,q/=gc;
if(pp<0) p=-p;
if(qq<0) q=-q;
if(p==0) printf("0\n");
else if(q==1) printf("%lld\n",p);
else printf("%lld/%lld\n",p,q);
} else {
int p=-b,q=tem,x=0;
int pp=p,qq=q;
if(p<0) p=-p;
if(q<0) q=-q;
int gc=__gcd(p,a);
p/=gc;
gc=__gcd(q,a);
q/=gc;
if(pp<0) p=-p;
if(qq<0) q=-q;
for(int j=2;j<=sqrt(tem);j++)
if(tem%(j*j)==0)
x=j;
if(p==0) {
if(x==0) printf("sqrt(%lld)/2\n",q);
else {
if(x%2==0) printf("-%lld*sqrt(%lld)\n",x/2,tem/x/x);
else {
if(x==1) printf("-sqrt(%lld)/2\n",tem/x/x);
else printf("-%lld*sqrt(%lld)/2\n",x,tem/x/x);
}
}
} if(p%2==0) {
if(x==0) printf("%lld-sqrt(%lld)/2\n",p/2,q);
else {
if(x%2==0) printf("%lld-%lld*sqrt(%lld)\n",p/2,x/2,tem/x/x);
else {
if(x==1) printf("%lld-sqrt(%lld)/2\n",p/2,tem/x/x);
else printf("%lld-%lld*sqrt(%lld)/2\n",p/2,x,tem/x/x);
}
}
} else {
if(x==0) printf("%lld/2-sqrt(%lld)/2\n",p,q);
else {
if(x%2==0) printf("%lld-%lld*sqrt(%lld)/2\n",p,x/2,tem/x/x);
else {
if(x==1) printf("%lld/2-sqrt(%lld)/2\n",p,tem/x/x);
else printf("%lld/2-%lld*sqrt(%lld)/2\n",p,x,tem/x/x);
}
}
}
}
}
}
}
return 0;
}
/*
9 1000
1 -1 0
-1 -1 -1
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1
*/
T4 bus - 0점
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int oo=0x3f3f3f3f;
const int N=1e5+10;
int n,m,k,x,y,z;
struct Node {
int to,nxt,st;
Node() {
to=nxt=st=0;
}
Node(int a,int b,int c) {
to=a;
nxt=b;
st=c;
}
} adj[N<<1];
int head[N],idx;
bool flag;
queue<int> a,b,c;
inline void add(int x,int y,int z) {
adj[++idx]=Node(y,head[x],z);
head[x]=idx;
}
void bfs(int s) {
a.push(s);
b.push(0);
c.push(0);
while(!a.empty()) {
int px=a.front(); a.pop();
int py=b.front(); b.pop();
int pz=c.front(); c.pop();
// cout<<px<<" "<<pz<<"\n";
if(px==n) {
if(pz%k==0) {
// cout<<py<<"\n";
printf("%lld\n",py+pz);
flag=1;
return ;
}
}
for(int i=head[px];i;i=adj[i].nxt) {
int v=adj[i].to,be=adj[i].st;
// if(pz+1>=be) {
// cout<<px<<" "<<v<<" "<<pz+1<<"\n";
// if(be==3) cout<<be-pz+1<<"\n";
a.push(v);
b.push(max(py,be-pz+1));
c.push(pz+1);
// }
}
}
}
signed main() {
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&k);
cout<<n<<" "<<m<<"\n";
for(int i=1;i<=m;i++) {
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
}
bfs(1);
if(!flag) printf("-1\n");
return 0;
}
/*
5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1
*/
고급 리그 S - 150점
T1 lock - 100점
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[11],ans;
int s[11][6];
void dfs(int cnt) {
if(cnt>5) {
for(int i=1;i<=n;i++) {
int p=0;
for(int j=1;j<=5;j++) {
if(s[i][j]!=a[j]) {
if(p==1) {
if(s[i][j-1]!=a[j-1]) {
if((s[i][j-1]-a[j-1]+10)%10!=(s[i][j]-a[j]+10)%10)
return ;
} else return ;
}
p++;
if(p>2) return ;
}
}
if(p==0) return ;
}
ans++;
return ;
}
for(int i=0;i<=9;i++) {
a[cnt]=i;
dfs(cnt+1);
}
}
signed main() {
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) {
s[i][0]=-1;
for(int j=1;j<=5;j++)
cin>>s[i][j];
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
T2 game - 50점
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int oo=0x3f3f3f3f;
const int N=1e5+10;
int n,f[N],last[30];
int stk[N],top,ans;
string s;
signed main() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
getline(cin,s);
int len=s.size();
for(int i=0;i<len;i++) {
if(s[i]>='0'&&s[i]<='9')
n=n*10+(s[i]-'0');
}
getline(cin,s);
len=s.size();
for(int i=0;i<=26;i++)
last[i]=oo;
for(int i=0;i<n;i++) {
if(last[s[i]-'a']!=oo) {
string w="";
top=0;
for(int j=last[s[i]-'a'];j<=n;j++) {
w+=s[j];
if(top&&s[j]==stk[top])
top--;
else stk[++top]=s[j];
if(top==0&&w!="")
ans++;
}
}
last[s[i]-'a']=i;
}
printf("%lld\n",ans);
return 0;
}
T3 struct - 0점
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1001;
int n,op,k,pos=1;
int maxv[N];
string s,t,a;
map<string,int> mp;
//map<string,int> mp3;
map<string,int> mp2;
map<int,string> mp4;
vector<string> vec[N];
int Vnum;
signed main() {
freopen("struct.in","r",stdin);
freopen("struct.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) {
cin>>op;
if(op==1) {
cin>>s>>k;
int maxx=0;
++Vnum;
vec[Vnum].push_back(s);
for(int j=1;j<=k;j++) {
cin>>t>>a;
if(t=="byte") {
maxx=max(1ll,maxx);
vec[Vnum].push_back(a);
} else {
if(t=="short") {
maxx=max(2ll,maxx);
vec[Vnum].push_back(a);
} else {
if(t=="int") {
maxx=max(4ll,maxx);
vec[Vnum].push_back(a);
} else {
if(t=="long") {
maxx=max(8ll,maxx);
vec[Vnum].push_back(a);
} else {
maxx=max(maxv[mp[t]],maxx);
vec[Vnum].push_back(a);
}
}
}
}
}
mp[s]=Vnum;
maxv[Vnum]=maxx;
}
if(op==2) {
cin>>t>>s;
if(t=="byte") {
mp2[s]=pos;
mp4[pos]=s;
pos++;
} else {
if(t=="short"){
mp2[s]=pos;
for(int j=pos;j<=pos+1;j++)
mp4[j]=s;
pos+=2;
} else {
if(t=="int") {
mp2[s]=pos;
for(int j=pos;j<=pos+3;j++)
mp4[j]=s;
pos+=4;
} else {
if(t=="long") {
mp2[s]=pos;
for(int j=pos;j<=pos+7;j++)
mp4[j]=s;
pos+=8;
} else {
int p=mp[t];
int len=vec[p].size();
int maxx=maxv[p];
for(int j=1;j<len;j++) {
mp2[s+'.'+vec[p][j]]=pos;
for(int ll=pos;ll<=pos+maxx-1;ll++)
mp4[ll]=s+'.'+ vec[p][j];
pos+=maxx;
}
}
}
}
}
}
if(op==3) {
cin>>s;
printf("%lld\n",mp2[s]-1);
}
if(op==4) {
cin>>k;
if(mp4[k+1]=="") printf("ERR\n");
else cout<<mp4[k+1]<<"\n";
}
}
return 0;
}
T4 tree - 0점
#include<bits/stdc++.h>
#define int long long
#define M(x,y) make_pair(x,y)
using namespace std;
typedef pair<int,int> pll;
const int N=1e5+10;
int n,x,y,a[N],b[N],c[N];
struct Node {
int to,nxt;
Node() {
to=nxt=0;
}
Node(int a,int b) {
to=a;
nxt=b;
}
} adj[N];
struct Tree {
int val,id;
} t[N];
int head[N],idx;
int dep[N],maxx[N];
int ans,w=0;
priority_queue<pll,vector<pll>,less<pll> > heap;
inline void add(int x,int y) {
adj[++idx]=Node(y,head[x]);
head[x]=idx;
}
void dfs(int u,int fa) {
dep[u]=dep[fa]+1;
for(int i=head[u];i;i=adj[i].nxt) {
int v=adj[i].to;
dfs(v,u);
}
}
void dfs2(int u,int fa) {
maxx[u]=t[u].val;
for(int i=head[u];i;i=adj[i].nxt) {
int v=adj[i].to;
dfs2(v,u);
maxx[u]=max(maxx[u],maxx[v]);
}
}
void dfs3() {
heap.push(M(t[1].val,1));
while(!heap.empty()) {
pll k=heap.top();
heap.pop();
int u=k.second;
int distance=k.first;
for(int i=head[u];i;i=adj[i].nxt) {
int v=adj[i].to;
w++;
ans=max(ans,t[v].val-dep[u]+w-1);
// cout<<w<<" "<<v<<" "<<t[v].val-dep[u]+w-1<<"\n";
heap.push(M(t[v].val,v));
}
}
}
signed main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
int cnt=0;
bool flag=1;
for(int i=1;i<n;i++) {
scanf("%lld%lld",&x,&y);
if(y-x!=1) flag=0;
if(x==1) cnt++;
add(x,y);
}
if(flag) {
// cout<<n<<"\n";
int day=0,maxx=0;
for(int i=1;i<=n;i++) {
day++;
if(c[i]>0) {
int s=b[i]+c[i];
int m=a[i];
int g=c[i];
int ret=0;
if(g!=0) ret=(m-s-1)/g+1;
else ret=(m-s-1)+1;
if(ret*g<a[i]) ret++;
maxx=max(day+ret,maxx);
} else {
int ret=0,pp=0;
for(int j=1;;j++) {
ret+=max(1ll,b[i]+j*c[i]);
if(ret>=a[i]) {
pp=j;
break;
}
}
maxx=max(day+pp,maxx);
}
}
printf("%lld\n",maxx);
} else {
if(cnt==n-1) {
for(int i=2;i<=n;i++) {
if(c[i]>=0) {
t[i].val=111;
t[i].id=i;
} else ;
}
} else {
// cout<<111111<<"\n";
dfs(1,0);
for(int i=1;i<=n;i++) {
t[i].val=dep[i]+(a[i]-1)/b[i]+1;
t[i].id=i;
// cout<<t[i].val<<" ";
}
// cout<<"\n";
dfs2(1,0);
dfs3();
printf("%lld\n",ans);
}
}
return 0;
}
/*
4
5 1 0
8 2 0
3 1 0
11 2 0
1 2
1 3
3 4
*/
문제 해설
통과하지 못한 문제 위주로 설명하겠습니다.
기초 리그 J
T3
잡담: 시뮬레이션 문제였고, 시험 중에 풀지 못했지만 시험 후에 hk의 도움으로 완성했습니다.
본론: 2차 방정식 $ax^2 + bx + c = 0$ ($a \neq 0$)의 해는 다음과 같이 구할 수 있습니다 (문제에도 나와 있습니다).
위 식을 다음과 같이 변형할 수 있습니다:
편의상 $a$를 양수로 가정합니다 ($a = |a|$).
문제에서는 두 실근 중 최댓값을 요구하므로, $+$를 사용하면 근이 최대가 됩니다. 따라서 다음 식을 풀면 됩니다:
이제 문제는 위 식을 어떻게 계산하는지로 바뀌었습니다. 분류하여 논의해야 하지만, 자세한 내용은 생략하겠습니다. 주로 출력 형식에 따라 두 가지 경우로 나눌 수 있습니다. $a$ 또는 $a+b$ 형태입니다 (여기서 $a, b$는 모두 실수).
후자의 경우, 유리수와 무리수를 각각 처리해야 합니다. 여기서 gcd와 같은 연산이 필요합니다.
$\sqrt \Delta$를 처리하는 방법을 중점적으로 설명하겠습니다. 먼저 $\Delta$가 완전 제곱수인지 확인합니다. 완전 제곱수이면 바로 제곱근을 구합니다. 그렇지 않으면 가장 간단한 이차 무리식 형태로 만들어야 합니다. 중학교 2학년이면 누구나 할 수 있습니다. 간단히 말해, $\Delta$를 단순화한 결과는 유리수 $y$와 무리수 $w$, 그리고 분모 $x$로 나눌 수 있습니다. $a+b\sqrt{c}/d$ 형태로 출력하면 됩니다.
자세한 내용은 코드를 참조하십시오...
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int t,m,a,b,c,y,w;
signed main() {
// freopen("uqe.in","r",stdin);
// freopen("uqe.out","w",stdout);
scanf("%lld%lld",&t,&m);
for(int i=1;i<=t;i++) {
scanf("%lld%lld%lld",&a,&b,&c);
if(a<0) a=-a,b=-b,c=-c;
int tem=b*b-4*a*c;
int x=a*2,gc,cnt;
bool flag=1;
if(tem<0)
printf("NO\n");
else {
if(tem==0) {
if(b==0) printf("0\n");
else {
b=-b;
gc=__gcd(x,b);
x/=gc,b/=gc;
if(abs(x)==1) printf("%lld\n",x*b);
else {
if(x<0) x=-x,b=-b;
printf("%lld/%lld\n",b,x);
}
}
} else {
int t=sqrt(tem);
if(t*t==tem) {
b=-b+t;
gc=__gcd(x,b);
x/=gc,b/=gc;
if(abs(x)==1) printf("%lld\n",x*b);
else {
if(x<0) x=-x,b=-b;
printf("%lld/%lld\n",b,x);
}
} else {
if(b!=0) {
flag=0;
b=-b;
gc=__gcd(x,b);
x/=gc,b/=gc;
if(abs(x)==1) printf("%lld",x*b);
else {
if(x<0) x=-x,b=-b;
printf("%lld/%lld",b,x);
}
}
t=sqrt(tem),cnt=0;
y=w=1;
for(int i=2;i<=t;i++) {
while(tem%i==0) {
cnt++;
if(cnt==2)
y*=i,cnt=0;
tem/=i;
}
if(cnt==1) w*=i,cnt=0;
}
if(tem>1) w*=tem;
x=a*2;
gc=__gcd(y,x);
y/=gc,x/=gc;
y=abs(y),x=abs(x);
if(!flag) printf("+");
if(y!=1) printf("%lld*",y);
printf("sqrt(%lld)",w);
if(x!=1) printf("/%lld",x);
printf("\n");
}
}
}
}
return 0;
}
고급 리그 S
T2
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
int n,a[N][31],ans;
int last[N],f[N];
string s;
signed main() {
scanf("%lld",&n);
getchar();
getline(cin,s);
s=' '+s;
for(int i=1;i<=n;i++) {
last[i]=i;
int tem=a[last[i-1]][s[i]-'a'];
if(tem) {
last[i]=last[tem-1];
f[i]=f[tem-1]+1;
}
a[last[i]][s[i]-'a']=i;
ans+=f[i];
}
printf("%lld\n",ans);
return 0;
}