Codeforces - CROC 2016, IndiaHacks Final

오늘 3월 19일은 대회가 두개나 있었다..

CROC 2016

새벽에 했던 대회.

출제진에 대한 걱정이 컸었다. 저번 Div1D의 심슨 어쩌구에 대한 강한 기억이 아직도 (...) 물론 난 그 때 B도 못풀었지만 말이다. (그리고 폭풍 -118)

C

C부터 풀었다. 부분 합 + 이진탐색을 쓰는 쉬운 문제.

6분 AC. http://codeforces.com/contest/645/submission/16785733

B

그리디. 일반식을 쓸까 하다가 BIT 짜는게 더 빠를거 같아서 그렇게 했다.

9분 AC. http://codeforces.com/contest/645/submission/16786132

A

당황스러웠던 문제. 쉬운 방법이 있을법도 하다 싶었지만, 그냥 백트래킹을 짰다.

14분 AC. http://codeforces.com/contest/645/submission/16786684

E

또 그리디. 수열에서 서로 부분 수열의 개수 세는 typical한 dp 알고리즘이 있다. 알고리즘을 살짝 관찰하면 매우 될법한 그리디가 하나 떠오르고 실제로 된다.

24분 AC. http://codeforces.com/contest/645/submission/16788020

D

순서를 매길 수 있다는 것은 그래프에서의 최장 경로 길이가 |V| 라는 것과 동치이다. 고로 고정된 간선 집합에 대해서 빠르게 풀 수 있고, 간선이 추가되는 형태긴 하지만 parametric search를 사용하면 O(lgV) 정도만 붙고 크게 차이가 없다.

32분 AC. http://codeforces.com/contest/645/submission/16788968

F

이렇게 32분에 5문제를 풀고 아무것도 하지 못했다. 내가 너무나도 못하고 싫어하는 정수론 문제가 등장했기 때문. 그래서 G를 열어봤더니 이번에는 쌍곡선이다 (...) 의욕도 없었고 짜증만 났다. 심지어 핵할 거리도 없어.. (우리 룸은 정말 B를 잘 풀더라..)

끝나기 전에 작정하고 생각을 했더니 뫼비우스 함수를 사용한 풀이가 떠올랐다. 몇가지 시행착오 끝에 구현을 했는데, O(약수 ^2 * Q). 당연히 pretest에서 TLE가 났고 10분 남짓한 시간에 줄이려고 했지만 전혀 방법이 떠오르지 않았다.

대회 후 kriii님의 도움을 받아서 O(약수 * Q)로 오더를 줄이고 AC를 받았다. 몇가지 precalc로 오더를 줄일 수 있었는데 상당히 신기했다.

대회 당시 TLE 코드 : http://codeforces.com/contest/645/submission/16794307

대회 후 AC 코드 : http://codeforces.com/contest/645/submission/16800600

결과

E까지 달리면서 초반에 엄청난 이득을 취했지만, FG의 벽에 막혀서 아무것도 하지 못했다. 가만히 앉아서 사람들이 F를 푸는 걸 구경했는데, 잘 풀더라.

초반빨 덕분에, 감소폭이 크지 않았다. -13으로 살짝 떨어졌다. 이 때까지는 별 생각이 없었다...

IndiaHacks Final

오후에 했던 대회.

A

하라는 대로

2분 AC

B

하면 된다. (하지만 그러지 못했다... WA +1)

7분 AC (+1)

C

문제를 처음 보고, 말리면 끝도 없을거라는 생각이 강하게 들었다. 예상외의 강적에 당황했지만 열심히 케이스를 줄이고 줄이니까 딱히 더럽지는 않더라.

근데... N <= 150000이었다. 아니 왜??? 10만 아니고 왜????? 당연하다는 듯이 10만짜리 배열을 잡은 나를 코포는 RTE로 응징했다. 나중에야 알았지만 ainta도 이 응징을 당했다 (...)

ABC 문제들에 초반에 집중을 좀 못했고, (뒤부터 시작할까에 대한 미련이 들어서..) 고로 딱히 빨리 풀지도 못했는데, 심지어 페널티도 착착 쌓여가니까 초반을 망쳤다는 생각이 강하게 들었다. 푼 직후 등수는 약 50 ~ 60등 정도였음. 최근 내 코포 경향을 보면 초반에 모든 걸 쏟아붓고 등수 떨어지는 걸 구경하는 경향이 심한데 (아침 대회가 조금 극단적인 예이다) 초반마저 망쳐버리니 희망이 없다는 생각이 들어서, C를 푼 때를 기점으로 걍 즐겜하기로 했다.

29분 AC (+1)

D

힐링문제. 하드에 있던 플로우 라이브러리를 복붙했고, 풀었다.

39분 AC

E

처음 보고 ?? 뭐지 ?? 라는 생각이 들었지만, 금방 생각해서 pretest를 맞았다. 먼저 "금지된 에지" 가 있을 때 그래프 탐색을 빠르게 하는 방법을 알아낸 후, 1번 노드의 degree를 최소 / 최대화하는 그리디를 사용했고, pretest를 pass시켰다.

하지만 systest에서 까였다.. ㅠㅠ 조금 생각해본 후 노드의 degree를 최소화하는 그리디가 말도 안된다는 것을 깨달았다. "금지된 에지"가 있을 때 그래프 탐색을 빠르게 하는 방법을 알아내고, 이를 토대로 degree의 범위를 제대로 구하는 방법으로 대회 후 AC를 맞았다. 애초에 그리디라고 생각한 내 잘못..

틀리긴 했지만, 요 근래 내가 풀었던 문제 중 가장 재미있는 문제 중 하나였다.

59분 pretest pass (+1) / WA

F

괄호 문자열이 아니라고 생각했을 때, 저 문제는 suffix array로 쉽게 풀리는 유명한 문제가 된다. 다행이도, 그 풀이를 괄호 문자열에 대해서 쉽게 일반화할 수 있다. (괄호 문자열의 특징 -> depth가 같고, 사이에 자기보다 작은 depth가 없으면 괄호 문자열이다 라는 점을 활용.)

.. 이렇게 얘기하면 풀이가 쉬워보이는데, 구현하는 건 조금 까다롭다. 예외가 많다기 보다는 바운더리 체크같은 걸 제대로 해야 해서.. 당장 N <= 500,000인데 난 nlgn suffix array도 못짜서 백준으로 달려갔다. 딴사람 코드 가져오려고 (....) 다행이도 kcmsnups 님의 코드가 아주 깔끔하게 잘 구현되어 있어서 그대로 가져다 쓸 수 있었다. (이자리를 빌어서 감사하다는 말을..) 내가 제대로 센게 맞나? 이거 이상 이거 이하 맞나? 를 계속 따졌고, 다행이도 풀수 있었다. 이걸 풀고 끝났을 때 13등.

97분 AC

결과

E를 틀렸을 때 오늘 내 레이팅은 박살났다는 걸 직감했는데 다행이도 24등에 안착해서 별 문제는 없었다. 다행이도 점수가 올랐다.

그래서 오른건 좋은데, 2599점이다. 아.......... 저번 2199점의 저주가 생각나는 대목이다. (어떻게 2201이 되긴 했지만) 까놓고 말해서 내 위에서 19등 한 북한놈만 족쳐도 IGM을 갈 거 같은데, 족칠 수 있으려나..? 일단 이 글 쓰면서 생각나서 댓글을 달긴 달았다. (http://codeforces.com/blog/entry/43860?#comment-285103)

오우 댓글 쓰고 나니까 미련이 또 남네 ㅋㅋㅋㅋㅋ IGM 가고 싶다.