2연속 떡상 너무 달달하고요 ㅎ


https://codeforces.com/contest/1305


A


같은 값이 존재하지 않는다. 그러면 그냥 오름차순으로 정렬해두면 그래도 같은 값이 존재하지 않게 된다. 좀 자명하지만 A에서 정렬을 써야 되는데에 충격 먹었다.


B


그냥 ')' 앞에 나오는 '('를 모두 제거해주면 된다. 그냥 '('들의 인덱스와 ')'들의 인덱스를 모두 가지고 와주자. '('들의 인덱스는 오름차순,')'는 내림차순으로 정리되어있다 했을 때 '('의 인덱스가 ')'의 인덱스보다 커질 때까지 계속 ()를 제거해주면 된다. 당연히 1번만에 가능하고, 인덱스들은 귀찮으니 일단 모은 다음 나중에 크기순으로 정렬해주자. 한쪽만 있을 수도 있고 이미 0인 경우도 잘 처리해야 됨.


C


N>M이면 a[i]=a[j](modM)인 쌍 (i,j)가 하나 이상 존재하게 된다. 그럼 abs(a[i]-a[j])가 M의 배수이고 당연히 거기에 뭐를 곱해도 M의 배수이다. 그러므로 그때 답은 0. 아닐 때는 N<=1000이므로 naive하게 답을 구하자.


D


트리에서 리프를 두 개 잡자. 그거 둘의 LCA가 그 둘 중 하나라면 당연히 그게 루트다. 그게 아니면 둘 다 루트가 아닌 건 당연하다. 그럼 그 리프는 트리에서 제거해주고 새로운 리프 두 개를 찾으면 된다. 크기 2 이상인 트리에 항상 리프 두 개가 존재함은 사실 C번에도 쓰이는 비둘기집의 원리로 증명할 수 있는데, 간선은 (N-1)개이므로 모든 정점에 대해 인접한 간선들의 합은 2N-2이다. 모든 정점에 대해 인접한 간선이 적어도 하나는 있으니 N을 빼주고, N-2를 어떻게 분배해도 인접한 간선이 하나뿐인 정점이 존재함을 알 수 있다. N이 홀수인 경우 마지막까지 오게 되면 여태까지 건드리지 않은 정점이 어딘지 확인해주자.


E


1<=k<=n인 k에 대해서 a[i]+a[j]=a[k]인 쌍 (i,j)의 개수의 최댓값을 계산해보자. a[1]과 a[k-1],a[2]와 a[k-2]식으로 쌍지었을때가 최대이다. 그러므로 한 k에 대해 그 최댓값은 floor((k-1)/2)이다. 그리고 수열이 1 2 3 4 5 6 7 8 ... n인 경우 그것을 모두 최대화할 수 있어서 최적일 수밖에 없다는 걸 알 수 있다. 길이 x인 수열에서 쌍 (i,j,k)의 최댓값을 maxv(x)라 하자. (x-1)/2+(x-2)/2+...+1/2로 구할 수 있다. 일단 m>maxv(n)이면 당연히 답이 없고, m=maxv(n)이면 답이 1~n까지의 그것이다. 어떤 x에 대해 maxv(x-1)<=m


후기


사실 계속되는 떡락에 지쳐있다가 저번 라운드에서 +92를 받고 좀 기분 좋아진 상태였다. 5점만 올리면 맥레 갱신이다! 잘해보자! 가 내 마인드였다. A번은 늘 그랬듯이 슥삭했고, B번은 10분컷해야 되는 문제가 5분 더 걸리는 약간의 꼬임이 있었지만 그럭저럭 1트에 했다. C번은 O(NM)을 금방 떠올리고 딴 풀이를 열심히 찾아서 결국 딴 풀이로 풀었다.2억에 1초는 솔직히 도박하기 좀 그렇다. 또 C번은 풀면서 뭔가 N=1,M=1로 터트릴 수 있지 않을까?라는 생각이 들었는데 N>=2인 거 못 봤었다.


D번을 보자마자 기분이 너무 좋았다. '이거 그냥 이렇게 하면 되겠는데?'라는 생각이 바로 들었고, 리프노드를 어떻게 찾지라는 생각은 N<=1000을 보고 없어졌다. 그렇게 빠르게 짜고 냈는데 Idleness limit exceeded를 띄웠다. 뭐지?뭐지?계속 찾다가 느낌표 다음에도 fflush해야 된다는 걸 깨달았다. 다른 인터랙티브 문제를 푼 코드에서는 fflush를 안 하고도 AC를 받았었는데 왜 그런지 이해가 안 간다. 솔직히 이거 아니었으면 오렌지 갔다 ㅋ


E번은 원래 기대를 잘 안 하지만 저번 코포에서도 div1C=div2E를 풀어봤고 솔브 수도 좀 있어서 들어가봤다. 침착하게 아이디어적으로 접근하니까 풀이가 나와서 냈는데 프텟2에서 틀렸다... 프텟2 예제인데 ㅋ 끝에 넣어주는 이상한 수를 잘못 넣었는데 내가 계산을 잘못한 거였다. 그리고 또 프텟10에서도 틀렸다. 이번에도 끝에 수를 잘못 넣어서 ㅋㅋㅋ 그것도 수정하고 다시 내서 AC받았는데 2틀 안 했으면 오렌지 갔다 ㅋ 실수가 왜 이렇게 많지


그래도 잘한 것도 있다. E를 풀자마자 F는 희망이 없다는 걸 문제를 보지도 않고 판단하고 룸으로 갔다. 그리고 코드 몇 개를 훑어본 결과 if(N>=M)으로 예외처리하는 코드가 통과된 걸 확인할 수 있었다. N>M이어야 한다. 2 2 1 2로 간단하게 두 명 뚝배기를 깨줬다. 핵은 사실 시스텟 터지는 코드 잡아주는 일종의 자비라고 볼 수 있는데, 안타깝게도 그 두 사람은 코드를 고치지 못했다. 8분,1분 30초 남겨서 그랬나?


그리고 다행히 시스텟은 다 맞았고, 시스텟펑이 꽤 있었지만 내 프레딕터가 2100-2017=83을 가리키는 일은 없었다.


이번 대회에서 잘한 점과 못한 점을 정리해보자.


잘한 점 : E를 풀었다. 핵을 2개 했다.

못한 점 : Idleness limit exceeded로 삽질했다. 예제도 제대로 확인 안 했다.


뭐 다음부터 안 하면 되겠지.


다음 라운드가 악명높은 코드크래프트라서 걱정된다. 프리텟이 심각하다던데 나도 그냥 nuclear war에 참전할까 싶다.


그래도 4연떨로 1899점까지 내려갔다가 3번만에 2093점까지 올라왔다. 다음 라운드에서 오렌지를 갈 수 있길 바란다.