Longest Path to WF 팀연습 기록
2021/09/07 NWERC 2017
I : 증명을 하지 않은 그리디 + 냅색 디피를 제출했다가 틀렸고, 오타를 낸걸 고치느라 2번정도 더 틀렸다. edenooo님이 Exchange Arguement만을 쓴 뒤 그리디하게 답을 찾는 코드를 제출했다가 틀리셨고, 전에 제출했던 코드 안의 냅색 DP와 섞으니깐 맞았다. 패널티 망한 가장 큰 이유..
D : 그냥 쉬운 문제였지만, long long을 안써서 1 WA에 디버깅 약 10분을 낭비했다.
F : 보자마자 지루하지 않은 수열 문제가 떠올렸고, $O(NlogN)$ 풀이를 떠올리는데 시간이 걸리긴 했지만 풀이 그대로 한번에 맞았다.
Upsolved
J : 남은 문제들 중 그나마 사람들이 푼 문제여서 F번을 푼 2시간 40분 이후로 계속 잡았는데 끝날 때까지 아무것도 관찰하지 못했다. 풀이에 도움이 되지 않은 추측만 하면서 오히려 방해가 된거 같다. edenooo님 혼자서 브루트포스 코드를 가지고 관찰을 해서 맞는 풀이가 나왔지만, 제한시간 안에 풀지 못했다. 업솔빙은 했지만 왜 되는건지 모르겠다. 이게 다이아의 애드혹?
H : 식을 보니깐 $a^2$를 최대화 하도록 한 곳에 최대한 몰아주거나 $7*min(a,b,c)$를 최대화 하도록 골고루 나눠주는 두 방식이 가능성이 있어보였고, 그대로 짰더니 맞았다.
K : 강한 적을 최대한 나중에 만나도록 만든 다음에 답을 구하면 된다. 답을 구하는 과정에서 뇌절을 미친듯이 했다. 대회때 내가 잡았으면 패널티가 터졌을 가능성이 99%였다.
2021/09/08 NWERC 2018
I : 시작하자 마자 솔브가 나와서 차분히 읽어보니 쉬운 그리디 문제. 빠르게 AC
K : 문제를 읽었더니 얼마 전에 엄청 고통받으면서 푼 브론즈 문제였다는 걸 기억해냈지만 풀이가 떠오르지 않았고, 시작부터 차근차근히 풀어서 20분이나 걸렸다. 예전엔 한시간 이상 걸렸던 걸로 기억하는데 발전한건가?
J : 문제를 잘못읽고 1WA했지만 그렇게 크게 벗어나진 않았음을 깨닫고 풀이를 크게 바꾸지 않고 풀어냈다. 오타가 나서 1WA를 추가로 했었다.
J번을 풀었을 당시가 2시간 30분째였는데, 그 이후로 아무것도 팀에 도움이 되지 못했다.
Upsolved
E : 이런 문제를 잡았어야 했는데 풀이가 나올 당시 J번을 푸느라 바빴고, 다른 문제를 막 풀어서 시간이 비어있던 edenooo님이 풀었다. 조금의 함정이 있긴 했지만 예제로 알려줘서 큰 문제가 되지 않았다. 문제를 해결할 때 가장 어려운 점은 파싱+구현. edenooo님의 풀이가 예상외로 빠르게 통과한다는 이야기를 듣고 대충 짰더니 1 TLE. 그 뒤에 시간복잡도를 신경쓰며 짰더니 코너케이스를 하나 놓쳐서 1WA를 적립한 뒤에 맞았다.
H : 그냥 쉬운 그리디 문제. 영어 해석하는게 풀이 나오는 시간보다 오래 걸렸다.
2021/09/10 CERC 2015
C : L번을 풀만한 문제로 착각해서 풀이를 열심히 찾던 중에 쉬운 문제들을 모두 팀원 두분이서 해결했다. 남은 문제들 모두 골고루 적게 풀린 상태였고, 당시에 아무도 읽지 않았다는 C번을 읽었는데, 풀이가 나올거 같아서 잡았다. 스위핑을 떠올린 이후로는 풀이를 막힘없이 해냈던거 같았다. 2시간 30분쯤에 코드를 완성했지만 틀렸는데, 코딩 큐가 밀려있어서 약 1시간동안 열심히 손으로 반례를 찾아보았으나 찾아내지 못하고 스트레스를 짜서 찾아냈다. 풀이에는 결함이 없었는데, 코드 안에서 순서만 바꿔주니깐 맞는 거였다. 그래서 4시간 29분에 AC.
Aeren님이 4문제, edenooo님이 4문제, 그리고 내가 1문제를 풀어서 9솔이 되었다.
Upsolved
A : 문제를 열어보자마자 끄고 싶었다. 정말 풀기 싫었지만 결국엔 풀었다. 재미없는 구현문제
D : % m == 0인 곳을 칸막이로 둔다고 생각한다면 넣을지 뺄지를 자유롭게 결정할 수 있다. 그러므로 $2^{칸막이의 개수}$가 정답이다.
K : 팀 연습때 들었던 edenooo님의 풀이를 그대로 구현해서 맞았다. indegree가 0인 애들은 반드시 subset에 넣어야 하고 subset내의 정점이 가르킨 정점은 제외한다. 그렇게 indegree가 0인 정점이 없을 때 까지 계속 정점을 지우다 보면 사이클이 남게 되는데, 짝수 길이의 사이클이기 때문에 남아있는 정점들 중에 한쪽에 있는 애들만 subset에 넣어주면 된다.
B : 팀 연습때 Aeren님이 $N \sqrt N$ 풀이가 나왔다고 해서 흥미가 떨어졌었는데, 다른 사람들의 코드 길이가 짧아서 궁금해서 풀이를 까봤다. $N/1 + N/2 + N/3 + … + N/N = O(N \log N)$ 이라는 점을 이용해서 $l$부터 $r$까지 이분탐색으로 답을 각각 구하면 $O(N \log^2 N)$으로 문제가 해결된다.
2021/09/13 Tsukuba 2017
I : policy-2의 경우 가장 많이 겹치는 순간을 찾으면 되고, policy-1의 경우 각 구간과 겹치는 구간의 개수 중 max 값에 1을 더한 값을 구하면 된다.
J : 입력 조건이 문제를 푸는데 필요한 단서였다. 입력 조건에 의해 각 문자가 복사될 수 있는 leftmost는 왼쪽으로 이동하기만 하면 되고, 쿼리로 들어온 위치 또한 leftmost를 구해 1번 힌트로 들어온 적이 있는지 확인하면 된다.
2021/09/14 NEERC 2016
H : 겹치는 구간은 합쳐주는 게 최적이므로 스위핑을 하면서 합쳐준다. <= 또는 >= 만 있는 입력이 들어오면 각각 L을 -32768로, R을 32767로 하면 구간으로 표현할 수 있다.
M : 들어오는 정점마다 가장 가까운 위치에 있는 먹이를 먹으러 가면 되는데, 만약 전에 사용했던 간선을 역으로 간다면 사용한 거리가 +1이 아니라 -1로 처리해야 한다.
Upsolved
D : edenooo님의 풀이를 들었는데, 어짜피 코딩 큐가 나한테 돌아오지 않을 예정이었어서 그냥 연습시간에 짰다. 우선 e[i]를 모두 더한 뒤에 s[i]를 s[i]-e[i]로 바꾼다면 S만 선택해서 답을 구하는 문제가 된다. 그 뒤에 MCMF으로 풀리도록 모델링을 잘 해주면 된다.
2021/09/15 NEERC 2012
점점 순위가 낮아지고 있는 거 같다..
H : 초반에 솔브가 꽤 나왔는데 Aeren님과 edenooo님이 각각 A와 G를 푸느라 내가 잡았다. 금방 풀이가 떠올라서 풀었는데 롱롱이슈 때문에 한번 틀렸다. 근데 백준에 보니깐 예전에 풀었던 문제였다. 그래서 쉽게 풀었나?
**E **: 마찬가지로 솔브가 많은 문제를 잡게 되었다. 1의 자리를 채울 수 있는 박스들 중 최대 값을 가져오는 것을 반복해서 1의 자리의 수를 모두 채우면 10의자리, 10의 자리를 채운뒤에 100의 자리, … $10^{18}$자리 까지 채우는 것을 반복하여 모두 채우는 데에 필요한 박스들의 수를 채우면 된다.
J : 풀리지 않은 문제들 중에 그나마 풀만해 보여서 edenooo님과 같이 잡았다. $3 \leq a, b, c$이 가장 중요한 제한으로, $c = 0, 1 \leq a$인 경우에 항상 풀 수 있는 방법이 있어서 케이스를 열심히 나눠봤다. $c \bmod 3$의 3가지 경우를 처리하면서 a가 1이상인 경우가 되도록 만들 수 있어서 문제를 해결했다.
Aeren님이 구현이 힘든 F를 푸시고, edenooo님이 파싱은 어렵지만 풀이가 나온 D, 내가 대회 종료 15분 전에 풀이를 찾은 L을 각각 맡았는데, F는 맞왜틀, D는 구현 시간 부족, L는 코딩 큐가 오지도 않아 그대로 사망했다. 근데 F가 파일입출력에서 바로 fclose를 하지 않고 exit()를 쓰면 출력이 나오지 않는다는 게 틀린 원인이었어서 맞은걸로 쳐도 되지 않을까 한다.
중간에 D 파싱이 어렵지 않은 걸로 착각해서 내가 15분쯤 사용했는데 그대로 망해서 edenooo님이 코드를 갈아 엎고 새로 짜셨다.
Upsolved
L : 풀이는 맞았지만 구현 방법에서 틀려서 한참을 해메다가 데이터를 뜯어보고 맞았다. 왼쪽 위에서 오른쪽 아래로 가는 경로가 있다는 것은 왼쪽 아래에서 오른쪽 위로 #을 타고 가는 경로(대각선 포함)이 없다는 것이므로 왼쪽 아래와 오른쪽 위를 이어주는 정사각형을 찾으면 된다. dp를 이용해 해당 지점에서 뻗을 수 있는 가장 큰 정사각형의 크기를 찾을 수 있고, 이 길이는 이분탐색이 가능하기 때문에 섞어주면 $O(N^2 \log N)$으로 문제가 풀린다.
D : edenooo님의 풀이 방향을 들어서 쉽게 풀 수 있을거라 생각했지만, 이곳 저곳의 typo와 빈칸은 처리하지 않는 것, 그리고 I를 잘못 처리해서 a*Ib = aab 가 성립하게 된게 문제여서 데이터를 뜯어보면서 고쳤다. 연습 중간에 엎기 전 코드를 조금 많이 생각해서인지 생각보다 파싱에 고통받지는 않았다.