NWERC 2022

5시간씩이나 비는 것이 쉽지 않다고 했지만, 생각보다 수요일 저녁 시간대가 잘 빈다는 것을 알아냈습니다. 앞으로는 시험기간을 제외하면 이 시간에는 ICPC 셋을 돌 것 같습니다.

평소에는 노트북전용열람실을 애용하다가 멀티미디어실에 와봤습니다. 생각보다 PS하기 매우 좋은 장소입니다! 앞으로 셋을 돌 때는 여기로 와서 해야겠습니다. 문제를 프린트하기도 여기가 좋고요…

0:00~0:12

• A번과 B번을 읽고, B에서 식을 정리하다가,
• 슥보를 봤더니 I에 제출 3개가 들어가있는 걸 봤고,
• I를 봤더니 gcd만 쓰면 되는 문제로 보였습니다.
• 짰고, 틀렸고, 뒷면에 반례가 예제로 주어져있다는 것을 알게 되었습니다.
• 짰고, 맞았습니다.

0:12~0:23

• B번과 C번의 솔브수가 비슷한 속도로 늘어나고 있었습니다.
• B는 느낌이 잘 안 와서, C를 먼저 봤습니다.
• 이분탐색을 하면 적절히 풀 수 있을 것 같아 보였습니다. 문제는 답을 float로 내야 했습니다.
• 이런저런 생각을 해봤지만 아무리 생각해도 이분탐색을 하는 게 맞아 보였습니다.
• 절대오차보다 작은 오차까지 계산하는 이분탐색을 짰고 냈더니 바로 맞았습니다. 넘어갔습니다.

0:23~0:40

• B의 식을 정리하러 갔다가, 역시 식정리로 푸는 건 아니겠구나 싶었습니다.
• 슥보에 D가 풀리는 게 보여서 슬쩍 봤는데, 격자에서 거리 구하는 DP로 바로 짤 수 있는 문제였습니다.
• 바로 짰고 바로 맞았습니다.

0:40~0:46

• D를 하면서 생각해보니까 B도 계산하려 하지 말고 삼분탐색으로 그냥 짜도 될 것 같았습니다.
• 이유라 함은, 그래프가 아래로 볼록하게 나오는 것이 자명해 보였기 때문입니다.
• 짜봤고, 역시나 실수 범위 탐색이므로 2000번 정도 탐색하도록 짰고, 맞았습니다.

0:46~1:13

• 다음으로 풀 수 있는게 뭐가 있을지 슥보를 봤더니, 그나마 E가 잡히고 있길래 E로 갔습니다.
• 대충 어떤 정점으로의 최단거리의 합이 주어지는 값이도록 하는 그래프를 구성하면 되는 문제였습니다.
• 이런저런 생각을 해봤더니, 일단 루트에서 어떠한 strand를 쭉 뽑아낸 다음 그걸 확장시킨 트리 비슷한 걸 만들면 다 다룰 수 있는 것으로 보였습니다.
• 그걸 갖다 짜봤는데 틀렸습니다.
• 입력되는 분수를 갖다가 매우 큰 값을 곱해주는 것이 대체로 유리합니다. 논증하지 않고 몇 가지를 시도했고 그중 하나가 사실상 때려맞아서 넘어갔습니다.

1:13~1:29

• H랑 J가 조금씩 풀리고 있었고, 그중에서 J가 조금 더 풀렸길래 J를 먼저 봤습니다.
• 구간을 그리디하게 잘 관리하는 걸 생각하면 LIS를 구하는 문제가 됩니다.
• 슥슥 짰고 슥슥 맞았습니다.

1:29~2:04

• 슥보에 풀린 게 H밖에 없었고 그래서 H를 잡았습니다.
• 막 트리가 나오는데, balanced binary tree에 익숙하지 않아서 문제의 상황과 친숙해지는 데 시간을 조금 썼습니다.
• 그러다 보니까, 어차피 정점을 지우는 것만 할 수 있으므로, 어디까지 지우면 되는지를 잘 구하면 되겠다 생각했습니다.
• 탑-다운이랑 바텀-업 중 한 방향으로 밀면서 정리하면 정점을 최대한 적게 지우는 것을 그리디하게 만들 수 있을 것 같았고,
• 실제로 리프에서 루트로 올라오는 방향으로 하면 꺠끗하게 정리할 수 있었기에 DFS를 짰습니다.
• 어느 깊이까지의 정점을 지울지를 그때그때 선택하는 것을 하려고 했고,
  • 아마 작큰을 아주 잘 쓰면 가능할 것으로 보입니다만,
• 생각해보니까 어떤 깊이까지 쓸 수 있는지 그 깊이만 저장해도 나중에 다시 탑다운으로 밀어주면서 못 쓰는 정점을 세 주면 되기 때문에 작큰 같은 게 다 필요 없었습니다.
• 그래서 처음에 생각했던 것보다 매우 간단하게 구현을 했습니다. 꽤 오래 걸렸지만 아무튼 맞았습니다.
  • 지금 보니까 J랑 H 난이도가 같네요. 믿을 수 없습니다.

2:04~2:53

• 그새 G가 조금 풀렸길레 G를 봤습니다.
• 지를 수 있는 쿼리 횟수가 $3n+500$인 인터랙티브 문제인데, 여기서 $n$을 찾는 게 문제라는 게 문제입니다. 쿼리를 얼마나 질러도 되는지를 알 수 없습니다.
• 거리 범위를 알고 있으면 정확히 어느 정도인지 confirm하는 정도는 할 수 있기 때문에, 그 범위를 늘려 가면서 무언가를 잘 할 수 있나 싶었습니다.
• 그러나 이렇게 고능한 문제라면 제가 풀 수 없을 것이라고 생각했고(이때가 2:30 언저리였습니다), 그냥 저능하게 뚫을 수 없나 생각했습니다.
• 얼마나 쉽게 막힐 지는 모르겠으나 랜덤으로 뚫으려면 뚫을 수는 있어 보여서, 해봤습니다.
• 맞았습니다. 으으랜덤싫어

2:53~3:44

• 그새 K가 조금 풀리고 나머지 문제는 솔브가 없는 것 같아서 K를 잡았습니다.
• 색깔별로 정점으로 만들고 피자를 간선으로 보아 그래프로 모델링한 다음 그 안에서 규칙을 찾는 문제라는 사실은 거의 자명해 보였습니다.
  • 다른 방법으로 그래프를 모델링하거나 구간 그래프 문제 풀듯이 푸는 생각을 좀 해봤는데, 에바인거 같아서 접었습니다.
• 하나의 루프를 만들어야 하기 때문에, 리프 노드가 아닌 노드 3개 이상과 인접한 노드가 있는 순간 뒤진다는 사실은 어렵지 않게 알 수 있습니다.
• 사이클이 하나 생긴다면 그 사이클은 모든 정점을 연결하고 있어야 합니다. 사이클이 없다면 모든 연결 요소가 트리 비슷한 모양새를 띄고 있기만 하면 됩니다. 사이클이 두 개 이상이면 뒤지는 것은 자명합니다.
• 그걸 짰는데 틀렸습니다.
• 생각해보니까, 아예 쓰지 않는 토핑은 그래프에 나오지 않으므로 정점화시키면 안됩니다. 이걸 고려해서 사이클을 찾는 로직을 바꿔야 합니다.
• 짰는데 뭔가 틀렸습니다.
• 틀린 게 보여서, 고쳐서 냈는데 또 틀렸습니다.
• 갑자기 이상한 문제에 냈더라고요, 다시 냈더니 맞았습니다.
  • 다행히도 패널티가 올라가진 않습니다.

3:44~4:10

• F와 L을 봤습니다. A도 슬쩍 봤지만 슥보에 제출도 거의 없어서 만지면 안 될 것 같았습니다.
• L은 워들 문제였습니다. 지난번에 ICPC-ish 셋을 돌면서 워들 문제가 나온 적이 있는데 그때 플로우가 정해였습니다.
  • 스포일러하자면 L의 태그는 최대 유량과 서큘레이션입니다.
• 좀 아닌 것 같아서 F를 봤는데 이번엔 기하입니다.
• 몇 가지 발상을 했습니다. 나름 핵심적인 것 같습니다.
• 세상에서계산기하가제일좋아 씨에게 문제를 보내며 ‘이거 웰논임?’을 시전했습니다.

4:10~4:20

• 사실상 놀았습니다. 세상에서계산기하가제일좋아 씨가 남은 문제 중에서 F를 잡으라 했습니다.

4:20~5:07

• F를 더 잡았습니다.
• 잘 보아하니, 한 방향으로 대각선을 긋고 그 대각선 선분들을 다 지나는지 확인하면 됩니다.
• 대각선의 기울기가 모두 양수일 때 한번 모두 음수일 때 한번 확인합니다. 즉 각각의 상태에서 모든 대각선을 지난다는 것은, 대각선의 끝점들으로 만든 두 볼록 껍질 사이에 공간이 있어서 선분을 갖다 꽂을 수 있으면 됩니다.
• 까지 발상해냈을 때가 30분 전이었습니다.
• 솔직히 제 힘으로 PICP를 그 안에 컨헐과 함께 짜내는 것은 불가능하다고 생각했고, 적절한 기하 템플릿을 얻어왔습니다.
• 구현했고, 대회 시간 4분 전에 제출했는데, 틀렸습니다.
• 두 번 더 수정했지만 결국 못 고쳤습니다.
• 6분 뒤에, 인덱스를 잘못 썼다는 것을 깨닫고 고쳐서 냈는데 틀렸습니다.
• 10초 뒤에, 인덱스를 잘못 쓴 걸 다 고치지 않았다는 것을 깨닫고 고쳐서 냈는데 맞았습니다. 아오.

후기

• 솔직히 이정도면 존나 최상의 퍼포를 냈습니다. 물론 7분 오버하긴 했지만 다3까지 풀어냈고, 플레 이하의 9개 문제를 미는 데 3시간 44분이 걸렸습니다.
• 다만 쓸데없는 곳에서 WA를 남발하는 것은 아직 고치지 못했습니다. 꽤 오래갈 것 같습니다. E에서 3번, K에서 두 번 틀렸네요. F는 4분 전에 제출하려니까 정신없어서 막 박은 거라 할 얘기가 없고요.
• H에서 시간을 좀 오래 박은 것도 아쉽습니다. G와 K에서 각각 49분, 51분을 쓴 건 그만큼 어려웠기 때문인데, H는 풀 때 머리가 충분히 빠르게 따라오지 못했다는 느낌입니다.
  • J를 16분만에 푼 건 아주 좋습니다.
• 골드는 30분, 플레는 1시간이면 잘 잡힙니다. 적어도 이것의 2/3 수준은 가야 된다고 생각해서, 아직 속도가 부족하다고 느낍니다. 동시에 패널티도 줄여야 되네요, 으으…
• 그래도 F를 1시간 반만에 잡아냈다는 사실에 오늘은 기부니가 좋습니다.