NWERC 2024

5시간씩이나 시간이 비는 것이 쉽지 않은데, 어쩌다가 시간이 나서 혼자 NWERC 2024를 돌았습니다. 결과는 10+1155, 본대회 기준 9위입니다.

0:00~0:04

• A를 잡았습니다.
• 적당히 정렬을 할 줄 알면 됩니다.
• 구현했고 약간 걸렸지만 맞았습니다.

0:04~0:18

• 슥보를 보고 D를 잡았습니다.
• 대충 DP로 잘 풀 수 있을 것 같은데, 상태를 못 줄이겠습니다.
• 슥보를 보고 E번으로 넘어갔습니다.
• 분정 거듭제곱을 할 수 있으면 바로 풀 수 있는 문제였습니다.
• 구현했고 맞았습니다.

0:18~0:32

• 다시 D번으로 돌아왔습니다.
• 크기가 큰 것부터 먹으면 Superfluous한 경우를 쉽게 빼줄 수 있습니다.
• 그렇게만 하면 충분히 시간이 줄어들 것이라 생각했고 나이브를 구현했습니다. TLE를 받았습니다.
• 생각해보니까 이 아이디어에 위에서 생각한 DP를 얹으면 그대로 풀리는 문제였습니다.
• 구현했고 맞았습니다.

0:32~0:48

• 슥보를 봤고, L번이 제일 많이 풀렸길래 L을 잡았습니다.
• 적당히 모든 칸에 액자가 들어가도록 큰 것부터 그리디하게 채우고, 안되면 액자를 하나씩 빼는 그리디가 작동하는 것이 자명하게 보였습니다.
• 구현했고 맞았습니다.

0:48~1:06

• 슥보를 봤고, F랑 J가 제일 많이 풀렸길래 J를 잡고 F를 보기로 했습니다.
• 매우 단순하게 큰 것부터 달아주면 됐고, 구현했습니다.
• SJ가 존재한다는 사실을 망각하여 15분 정도 헤맸습니다.
• 그냥 제출했더니 맞았습니다.

1:06~1:23

• F를 잡았습니다.
• 그림은 거창해보이지만 사실 포레스트 간선을 하나씩 추가하면서 유파를 하면 됐습니다.
• 구현했고 맞았습니다.
• * 여기까지 골드 이하 올솔브입니다. D에서 풀이를 한 번 절었고 J에서 이상한 이유로 헤맸지만, 아무튼 문제당 20분 미만으로 잘렸습니다.

1:23~1:56

• K를 잡았습니다.
• kruidnoten이 있는 모든 매장에 대해 그 매장을 들르는 경로 길이가 존재합니다. 그 매장보다 짧은 경로를 가지는 경로가 모두 품절됐고 그 매장은 구매 가능한 경우에 대해서만 그 매장을 이용합니다.
• 경로 길이를 모두 구하는 것은 집과 학교에서 SSSP를 하면 되므로 다익을 써서 구하면 됩니다.
• 까지 생각하고 나서 ‘구매를 못하는 확률이 0보다 크면 불가능’이라는 조건을 읽었습니다. 모든 매장을 못 쓰는 확률을 생각하면 됩니다.
• 구현했고 틀렸습니다.
• 모든 정점에 0.9999짜리 매장이 붙어있으면 모든 매장을 못 쓰는 확률이 $10^{-50000}$ 스케일로 작아질 수 있습니다. 실수 오차를 막을 수 없으므로, 그런 경우는 직접 빼줘야 합니다.
• 구현했고 한 번 더 틀린 뒤 맞았습니다.

1:56~2:50

• 슥보에 의하면 H와 M을 잡아야 했습니다.
• H의 지문이 매우 긴 것을 보고 M을 잡았다가, 기하인 것을 보고 10분 정도 뒤에 H로 도망왔습니다.
• 사실 맨 아랫부분만 읽으면 문제를 알 수 있었습니다.
• 순열사이클분할에서 아무 사이클이나 하나 잡을 수 있으면 문제를 풀 수 있었습니다. 보다 정확히, 사이클의 크기와 사이클에 포함된 점 하나를 알아야 합니다.
• baby step giant step의 아이디어를 생각하면, 사이클 위에 있는 점에서 1걸음씩 루트번 루트걸음씩 루트번 움직이면 사이클의 크기를 알 수 있습니다.
• 어떤 점에서 출발해서든 N걸음을 가면 사이클 위에 있게 됩니다.
• 따라서, 1번 점에서 N걸음을 간 뒤 그 점에서 baby step 450번 giant step 450번을 하면 무조건 사이클을 하나 구할 수 있습니다. 그럼 문제를 풀 수 있습니다.
• C의 범위가 명시되어 있지 않은 것때문에 한 번 틀리고, 출력 순서를 이상하게 하고 제출해서 두 번 더 틀렸습니다. 앞으로 icpc 인터랙티브는 테스터를 잘 돌려야겠습니다.
• 아무튼 맞았습니다.

2:50~3:34

• C를 잠깐 봤습니다.
• 몇 가지 그림을 그려봤을 때 직사각형이 생겼는데, 그렇지 않은 그림도 있었습니다.
• M으로 돌아왔습니다.
• 고양이 위치가 정해져 있을 때로 15분 정도 고민했고, 어려움은 둘째치고 부질없다는 것을 깨달았습니다.
• 가능한 모든 삼각형의 넓이의 합을 구하면 됐고, 그래서 벡터 외적을 생각했습니다.
• 식정리를 조금만 하면 풀렸습니다.

3:34~4:04

• 슬슬 C가 좀 풀렸길래 C로 갔습니다.
• 뭔가 almost-linear한 세 점이 풀이에 영항을 주지 않을까 싶었습니다.
• 이걸 위해서 컨헐 할때 upper/lower hull 구할때처럼 제일 왼쪽 점을 가져오는 생각을 했습니다.
• 이때, 제일 왼쪽 점은 그 다음 왼쪽 점이 있는 곳까지는 오른쪽으로 밀어줘도 괜찮습니다. 이걸 모든 방향에 대해 다 할 수 있습니다.
• 이게 끝나면 직사각형 하나 혹은 직사각형과 내부의 한 점이 남습니다. 케웍하면 풀립니다.
• 구현하고 맞았습니다.

4:04~4:30

• B를 잡았고, 11001100 사이클이 있는 순간 무한하다는 것을 알아낸 것 외에 별다른 성과를 내지 못했습니다.
• G는 그냥 너무 어려웠고, I도 이상한 수학 같아서 안 잡았습니다.
• 30분 정도 남기고 포기하고 풀이를 깠습니다.

후기

• 혼자서 5시간짜리 셋을 5시간동안 돈 것이 꽤나 오랜만입니다. 생각보다 피곤하기도 하고, 골플구현기계가 된 것 같아서 힘듭니다.
  • 어려운 문제까지 가는데 더 오래 걸려서 머가리를 덜 굴려도 되긴 합니다.
• 저보다 유의미하게 빠른 속도로 골플을 밀어줄 다른 구현기계를 얻어오지 못할 확률이 크므로 제가 골플기계가 되어야 합니다. 그래서 첫 번째 ICPC 목표는 골플 빨리 잡기가 될 것 같습니다.
• 그걸 상정했을 때, 이번 셋은 골드는 충분히 빨리 밀었고 플레에서는 좀 절었다는 느낌입니다.
  • 제가 아무 골랜디나 15~20분에 자를 수 있는 실력인지 잘 모르겠는데, 오늘은 그게 잘 됐습니다. 여러모로 좋습니다.
  • H는 사실상 아이디어를 다 알고 있었음에도 구현에서 말려서 두 번인가 틀렸습니다. 그 외에도 여러 번 틀린 것들이 꽤나 있습니다.
  • 어쨌든 패널티를 많이 안 쌓는 것이 중요한데, 정올을 하다 와서 패널티 관리에 익숙하지 않다는 느낌입니다.
  • 그래서 요즘 들어 ‘최대한 풀이 구체화하고 구현 짧게 하기’를 하고자 생각만 하고 있는데, 실천이 잘 안 되네요.
  • 아무튼 그래서 플레 하나에 평균 40분, 최대 55분 정도가 걸렸습니다. 갈 길이 꽤나 먼 것 같습니다.
• 어쨌든 혼자 했는데도 4시간 동안 플레를 다 밀었기 때문에(혼자 돌아서 플레를 완전히 민 것은 아마 처음입니다) 만족합니다.