2022 한국 정보 올림피아드 1,2차 후기

실력이 부족해서 후기라 할 것도 없었다.

PS는 작년 1월달 부터 하기 시작했다.

 

1차

1차를 보는데 필기가 엄청 어려워서

원래 180점 정도를 예상했지만,(거짓말,최대공약수)문제를 틀리고,

확률과 통계 관련 문제를 틀려서 100점 초반대가 나왔다.

실기는 2번 문제는 손도 못 댔고, 1번 피하자 문제를 푸는데,

일단 다 바꿔보는 브루트 포스로 50점을 긁었고,

누적합을 사용해 O(n)만에 풀려고 했고, 로직은 맞았다.

하지만 int 자료형을 넘는 경우가 있어 그것도 모르고 있다가.

동상을 받게 되었다.

 

2차

1번

먼저 1번 문제의 서브테스크 1번을 풀려고 했다.

근데 계속해서 0점이 나와 당황해 3번 4번 문제의

1번 서브테스크만 긁고 다시 돌아왔는데, 

갑자기 등차수열에서 원소가 정수란것을 이용해서

O(n^2) 로 풀어서 100점이 나왔다.

 

3번

구형의 주차타워가 주어지고,

왼쪽으로 돌리기, 오른쪽으로 돌리기,

차 빼기(타워에 차보다 큰 숫자가 없어야하며,구에서 맨 밑에 존재해야함)

연산이 주어질때 모든 차를 빼기 위한 최소의 연산 횟수를

구하는 문제였다. 어려워서 1번 케이스인 옆 차가 번호가 큰

케이스만 공략했다.

 

4번

K명의 사람이 주어지고, 각각의 레벨이 주어질때

최소의 레벨을 가진 사람에게 레벨업을 할때,

총 레벨업 횟수가 주어질때 각 사람의 레벨업 진행도를 

구하는 문제였다.

1번 케이스만 긁었는데, 이 경우에는 그냥 정렬후

시뮬레이션으로 O(KM log N)만에 하였고,

2번 같은 경우는 누적합을 사용하면 O(K log M)만에 되는데,

Li<=Lj을 가진 사람이 있을 거라고 착각 해서 못 긁었다.

하지만 이 경우에는 계수 달린 누적합을 쓰면 될 거였다.

2번

2번 문제를 보는데, 2번 문제를 간단히 설명하자면,

트리가 주어지고,쿼리가 주어지는데,

쿼리 집합의 원소들 중 2개를 a,b라 칭하면

a에서 부터 b로 가는데 쿼리 내 집합들만 지나서 이동가능하면

결합력이 1이라 할때 그 쿼리의 결합력을 구하는 것이다.

 

1번 테스크가 n이 정점이 3개 일때 인데,

이때 쿼리의 집합의 크기는 1~3이라 생각하고,

1,2,3 크기를 나누어 풀려했지만 무슨 이유에선지 0점만 나오고,

2번 테스크가 O(n^3)으로 될거같아 bfs 코드를 짰는데, 에러가 났고,

2시간을 허비했다.

 

결과

차라리 4번 문제를 더 긁어보았으면 좋았을 거 같다.

그 결과 112점(동상)이 되었다.