[Codeforces] Round #462 (Div. 1 + Div. 2)

http://codeforces.com/contest/934

A, B번 모두 hack이 굉장히 잘 일어날 수 있는 문제여서 이를 잘 이용했습니다. 다만, 이전에는 hack을 해본적이 많이 없어서 몰랐는데, hack 버튼을 누르고 로딩화면이 무한히 뜨는 일이 자주 발생했습니다. 이 때 새로고침을 계속 하면 금세 뜨는데 그걸 몰라 같은 Room에 속한 사람에게 hack을 많이 뺏겼습니다. 시작하고 10분만에 A에서 hack이 많이 발생할 수 있겠다는걸 깨닫고 B를 풀기도 전에 hack을 시작했는데, 그것 때문에 시간도 많이 낭비했습니다. 또 C번 문제를 잘못 생각해 7분 남기고 해결에 성공한 것도 조금 아쉽습니다.

결론적으로 A, B, C를 풀고 hack을 6번 성공했습니다.(hack을 5번 정도는 더 할 수 있었는데 아쉽네요.)

A - A Compatible Pair

만약 수들이 전부 양수라면 정렬 후 a[n-2]*b[n-1]을 출력하면 되는 매우 간단한 문제였겠지만 그렇지 않아 맨 처음에는 음수/0/양수를 따로 분류해서 풀어야하나 하다가, n이 작길래 그냥 있는 상황 그대로 brute force를 했습니다.

https://github.com/blisstoner/Codeforces/blob/master/Round%20462%20Div.2/A.cpp

B - A Prosperous Lot

B를 풀기 전, 이 당시 다른 사람의 A를 hack하려고 무한정 대기하다가 시간을 많이 날려먹었습니다. 입력받은 k가 36보다 크면 -1을 출력하고, 36이하이면 그냥 k/2개의 8을 찍고 k가 홀수면 추가로 0, 4, 6, 9 중에 아무거나 하나를 출력하면 됩니다. A번보다 더 쉬워보입니다.

https://github.com/blisstoner/Codeforces/blob/master/Round%20462%20Div.2/B.cpp

C - A Twisty Movement

D1[i]를 p[1~i]까지에서 1의 갯수, D2[i]를 p[i~k]까지에서 2의 갯수, D3[i][j]를 p[i~j]에서 non-inceasing subsequence의 최대 길이라고 한다면, D1[i-1]+D3[i][j]+D2[j+1]이 i-j 구간을 뒤집었을 때의 longest non-decreasing subsequence의 길이입니다. D3[i][j]는 p[i-j]까지의 2의 갯수와 D3[i][j-1]로부터 상수시간안에 계산할 수 있으므로 O(N^2)에 해결 가능합니다. O(N)에 가능하다고 editorial에 올라와있는데 잘 이해를 못했습니다. 참고로 처음에 제가 문제를 잘못 이해해서, 1이 연속해서 등장하는 부분과 2가 연속해서 등장하는 부분을 묶어버렸는데(코드상의 seg) 그 부분은 결과적으로 필요없는 부분이 됐네요.

https://github.com/blisstoner/Codeforces/blob/master/Round%20462%20Div.2/C.cpp

C를 엄청 늦게 풀었지만 hack을 6번 성공한 덕에 215등을 기록할 수 있었습니다. D번 문제가 그닥 어려운건 아니었다는데 문제를 읽을 시간조차 확보하지 못했던건 아쉽네요. 어쨌든 지금 이 정도의 상태만 유지할 수 있어도 일단 퍼플을 찍을 수 있긴 할 것 같습니다.