Codeforces Global Round 15

Dashboard - Codeforces Global Round 15 - Codeforces

 

우왕..

 

코이와 날짜가 겹치긴 했지만, 글로벌 라운드를 거를 생각은 애초에 없었고 결과는 성공적이었다.

블루에 5달 넘게 서식하면서 퍼플이 멀게만 느껴졌었는데, 최근에 퍼플 퍼포를 내면서 점수가 조금씩 오르더니 기어코 오렌지 퍼포를 받으며 퍼플에 안착했다. 코이 망한 건 아쉽지만 코포로 마음이 어느 정도 달래진 것 같다.

 

TMI

대회가 시작됐는데 사이트가 먹통이 된 건지 와이파이가 느린 건지 접속이 되질 않았다. 일단 침착하게 폰으로 핫스팟을 켜고 문제를 읽었지만, 문제가 쉬웠는지 솔브 수가 무지막지하게 올라갔다. 노트북 접속이 성공했을 때는 5분 정도가 지난 시점이었고, 이미 몇천 명이 B번으로 넘어갔을 테지만 그 정도는 극복할 수 있다는 생각에 포기하지는 않았다.

 

Prob. A

정렬된 문자열과 얼마나 일치하는지 확인해주면 된다. 그런데 이를 빨리 떠올리지 못해서 5,000등 정도로 시작했다.

 

Prob. B

A를 제출했으니 어떻게든 올라가야 한다는 생각에 B는 무지성으로 풀었다. 문제 조건대로 선수들을 정렬한 뒤 첫 번째로 위치한 선수가 금메달을 딸 수 있는지만 판별해주었다. 솔직히 왜 되는지는 모르고, '틀리면 틀리라지' 이런 마인드로 제출했다. 구현도 뇌를 비우고 해서 많이 더러웠지만, 다행히 한 큐에 맞을 수 있었다. 이 제출이 틀렸으면 아마 멘탈이 크게 나갔을 것 같다.

 

Prob. C

C를 풀 때도 집 나간 지성이 아직 돌아오지 않은 상태였다. 일단 교점이 생기려면 점의 순서가 $1-3, 2-4$ 여야 한다. 이제 선택되지 않은 점들을 순서대로 두 그룹으로 나눈 다음 (ex $1, 2, 3  /  4, 5, 6$ ) 이를 앞에서부터 이어주면 ( $1-4, 2-5, 3-6$ ) 교점의 개수가 최대가 될 것이라고 추측했다. 근거는 딱히 없고, 1번 TC가 이렇게 생겨서 될 것 같았다. 교점의 개수는 무지성 4중 포문으로 구했는데, 이게 알고 보니 $O(N^{2})$ 에 돌아가서 맞을 수 있었다. C를 풀고 나니 왠지 모르게 순위가 떡상했다. 500위 안쪽이었던 걸로 기억한다.

 

Prob. D

n이 10 이하이므로 뭔가 브루트 포스를 해야 한다는 말인데... 예제를 만들기도 쉽지 않을 뿐더러 예제를 만들어도 특별한 규칙을 찾기 힘들었다. 한참 고민하다가 예제 1번에서 $a_{1}+a_{3}=a_{2}+a_{5}$ 임을 이용해 $b_{i}$ 의 개수를 줄였다는 점에서 아이디어를 얻어 모든 $a_{i}$ 에 $\pm$ 를 붙여보자는 결론을 내렸다. 가능한 집합 중 공집합이 아닌 집합의 합이 0이 된다면 construct하게 $b_{i}$ 를 구할 수 있고, 이는 naive하게 $O(N3^{N})$ bfs를 돌릴 수 있다.

 

Prob. E

그리디밖에 떠오르지 않았다. 일단 기본적으로 구간 update & max query 를 지원하는 세그를 이용했다. 1번 색부터 보면서 구간 길이순으로 정렬하고 짧은 구간부터 넣어보는 방식은 TC5에서 가차 없이 막혔고, 색에 상관없이 구간 길이순으로 정렬해서 짧은 구간부터 넣어보는 방식은 TC6에서 막혔다. 더 이상의 그리디는 생각나지 않아서 포기.

 

Prob. F

dp처럼 생긴 재밌는 문제였다. 먼저 관찰한 점은 이동 거리를 비교적 간단하게 나타낼 수 있다는 것이다. $ans=x[n]+1+\sum a[i]*(x[i]-y[i])$ 정도로 표현 가능하다. 이때 $a[i]$ 를 각각 구하기는 조금 까다로워서, dp식을 다음과 같이 세워볼 수 있다. $dp[i]=$ (열린 $i$번 포탈에 들어가 다시 $i$번 포탈에 도달할 때까지의 이동 거리) . 일단 $x[i]-y[i]$ 만큼은 무조건 이동한다. 그리고 $j$를 $y[i]\leq x[j]$ 를 만족하는 최소 정수라고 한다면 $dp[i]$에 $dp[j]+dp[j+1]+\cdots +dp[i-1]$ 이 더해진다는 것을 관찰할 수 있다. 그리고 이는 $dp[i]$ 의 누적합을 구해주면 $O(1)$ 에 구할 수 있다. 이제 $s[i]=1$ 일 때만 $dp[i]$ 를 더해주면 된다.

 

 

F의 난이도가 높지 않은데다 크게 말리지 않아서 운 좋게 퍼플을 찍을 수 있었던 것 같다. 퍼플이 된 이상 다음 목표는 오렌지인데, 오늘 같은 퍼포를 꾸준히 유지해야 오렌지가 될 수 있다는 사실에 한숨만 나온다. 코이가 끝남과 동시에 퍼플을 달성했고, 오렌지에 크게 욕심도 없으니 이젠 내신 공부에 조금 더 집중하려고 한다. 정올 준비한답시고 고생을 은근 해서 몸이 조금 피곤하다. 수고했고.. 다시 힘내자.