UCPC 2022 본선 후기?

패널티 기계가 되었다. 만족할 만한 결과를 내지 못했다..

 

스코어보드는 아직 못 보는듯..?

 

우리 팀은 4솔(+10)로 43등정도를 했다. 오프라인 대회가 처음이라 그런지, 이런 어수선한 분위기에 적응이 되지 않았다. 게다가 잘 시간인 6시 쯤에 일어나니 더 피곤했다. 구차한 핑계는 넘기고.. 문제를 많이 못 푼 만큼, 풀이도 매우 간단히 적겠다.

 

H (solved by me, +1)

뒤가 큰 것부터 먹고, 그 다음 앞이 큰 것을 먹으면 된다.

 

J (solved by greedev, +3)

답은 1 또는 2이다. 1인 경우는 쉽고, 아닌 경우에는 l r 각각 존재 여부를 찾아주면 된다.

 

K (solved by greedev, +3)

구현이 매우 빡세다. 지는 횟수와 이기는 횟수를 잘 보면 된다. 구현을 대신해줘서 많이 고마울 따름이다. 그리고 세트에 값 100만개를 넣는 짓 덕에 특별상도 받았다 ㅋㅋ...

 

L (solved by greedev, +3)

문제를 안 봐서 뭔지 모른다

 

 

이후는 풀이 구상은 어느 정도 했으나 못 푼 문제들이다.

 

A

안쪽에서부터 채워나가기, i번째에서는 무조건 k~i의 연속된 구간의 색들과 붙는다는 것을 찾았으나, 누적 합을 만들 생각을 못 해서 죽음의 N^3풀이만 가지고 있게 되었다.

 

F

그리디가 통하지 않는다는 것은 찾았고, dp[n][k]를 어떻게 잘 최적화해야 했다. 세그 트리를 사용하면 되지만, 떠올리지 못했다.

 

I

'비행기 타고 가요'에 쓰이는 테크닉을 사용하면 된다. hodudragon이 간선이라는 아이디어를 내었고, 이것으로 구간 간선 테크닉?을 greedev이 내게 알려주었다. 이를 토대로 scc끼리 묶고 이를 위상 정렬(이미 되어있긴 함)하는 것까지 찾았다. 근데 20분 밖에 남지 않아서 구현 시간이 부족했다.

greedev이 한 달 전 쯤에, 알아두면 좋다고 한 건데 귀찮아서 미뤘던 게 문제로 보이니까 묘했다.

 

 

 

 대회 초반에 너무 말렸다. 우리 팀 모두 오프라인 팀대회가 처음이었던 것이 저조한 퍼포먼스의 요인 같다.

 

I번은 업솔빙을 꼭 해야겠다..