(koosaga) 짜증나는 dp인데 결국 어떠한 구간 s, e를 비교할 수 있는 경우의 수를 세면 된다. 각각의 구간에 대해서 [empty][a][b][c][d][...][z] 로 나누는 경우가 27승 정도인데 이건 dp안에 dp를 넣는 느낌으로 하면 된다 (물론 코드가 그렇진 않다..)
C (1:23 +1)
(alex9801) n<=5 일때 케이스를 나눠서 풀리는 문제가 있고 아닌 문제가 있는데 이 문제는 다행히 전자였고, 후자인 다른 문제는 못 풀었다. 97%의 정확도로 케이스를 처리했지만 하나를 놓쳐서 1WA를 쌓았다. 포인트는 답을 바로 구하지 말고 주어진 입력의 합에서 아낄 수 있는 정점 수를 최대화하며 카운팅하는 것. n=4에선 2의 개수, n=5에선 2와 3의 개수로 나누어 카운팅하면 된다.
(hyea) 팀원이 케이스를 나눠서 풀려고 하면 2번 이상 검증해 보라고 말해야겠다.
D (2:30 +1)
(alex9801) 사다리타기를 할때 항상 위에서 아래로 내려가므로 빠지는 사다리 선분은 위에서부터 아래로 보면 서로가 주는 영향을 모두 고려할 수 있다. 원래 생각한 풀이는 지그재그를 대각선들로 펼쳐서 각 대각선마다 숫자를 관리하는 것인데, 그냥 맨 위의 숫자가 바뀐다고 생각하는 것이 더 편하다.
(hyea) 사다리타기가 위에서 부터 바뀌기 때문에 위에서부터 쭉 보면 된다. 코딩은 시작점으로 부터 위쪽으로 쭉 가면서 찾아서 바뀌는 부분은 바꾸면 끝
F (1:05 +1)
(hyea) 예외처리를 잘 하자
(koosaga) 벡터 3개만 써도 모든 direction을 표현할 수 있다고 들어서 빠르게 하는 방법을 고민했다. 여기서 관찰이 필요한데, 12 사분면을 위 34 사분면을 아래라 하면, 위에 1개 아니면 2개의 직선만 고르면 됨. 근데 이렇게 하면 141번 TC에서 틀린다 왜냐면 4개를 써야 하는 예외가 있거든 ㅎㅎ X자 모양이 유일한 반례고 예외처리하면 맞는다.
G (4:10)
(alex9801) 뱀을 움직이는 것보다 벽을 움직이는 것이 훨씬 간단하다는 관찰이 핵심. 벽을 뱀을 타고 통과시키면서 2개 이상의 점에서 만나는 경우가 없도록 하는 방법이 있는지 확인하는 것과 동치라는 관찰을 하면 된다.
(hyea) Snake는 모든 정점에 대해 그 점만 관통할 수 있는 직선이 있다. 라는 것과 동치라는 가정을 하고 풀면 풀린다.
H (3:11 +1)
(koosaga) 그때 그때의 centroid를 다 구해두면 이후 트리 분할 정복으로 해결 가능 (설명 생략). i번 centroid는 (i-1)번째 centroid가 i번 정점쪽으로 따라간 형태가 될 건데, sparse table 만들고 서브트리에 체크된 정점 개수를 bit로 빠르게 세면 로그제곱에 따라갈 수 있음
I (unsolved)
(koosaga) 풀이를 봤는데 백트래킹으로 나열할 수 있는 무언가가 있나 보다..
J (1:22 +2)
(hyea) d차원문제는 풀었어야 했을 것 같은데 못 풀었다. 이건 내가 아무리 생각해도 d차원에 대한 감각이 퇴화했다는 증거일 것이다.
(koosaga) s <= min(ai) 이면 s^d가 답인데 삐져나오는 부분이 문제. 그래서 그 부분을 포함배제로 뺐다 넣어줬다 하면 된다. 거기부턴 냅색. 모듈러 때문에 졸라 틀렸는데 기본적인 건 좀 챙기자...
대전 이후에 팀연습을 못할 줄 알았는데 나름 기적적으로 시간 한 번 잡아서 좋다.
여담으로 더불어민규당 팀연습 기록 + 팀노트를 빠른 시일내에 GitHub으로 공개할 예정이다. 공개하면 블로그에 올릴 예정. 기대해주세요~~
