Little Piplup 7월 31일 팀연습

UCPC Preliminary를 턱걸이로 (결과적으로 55등까지 붙었으니 턱걸이는 아니긴 한데..) 붙었기 때문에, 

5시간짜리 팀연습을 돌아야 한다 면서 찾다가 우리가 아무도 UCPC 18 문제를 풀지 않았다는걸 깨닫고 바로 셋 돌았다.

 

일단 본선이 당장 내일이기 때문에 팀연습 리뷰는 정말 대충 (...) 만 쓰기로 했다.

작년 UCPC 셋에 대해서 주워들어서 알고 있던건

- IMO를 참고하여 출제된 문제가 있다.

- 미친 빡구현 문제가 있다.

이정도? 그외에는 별로 아는게 없었기 때문에 그냥 이걸로 돌아도 되겠다는 판단이 들었다.

 

간단히 피드백을 하자면, 결과는 좋은데 과정은 안 좋았다는 생각이 든다. 이유는 끝에 후술.

 

UCPC 예선에서의 우왕좌왕을 방지하기 위해, 팀연습 때 전략을 새로 시도하기로 했다. 풀 수 있는 문제를 확실히 풀고, 풀 수 없는 문제를 거르기 위해서, 처음 시작때 쭉 읽다가 누군가 확실히 쉬운 문제를 잡으면 그냥 그거 풀고, 어느 정도 쉬운데 혼자 풀기 애매한 문제를 만나면 그냥 다같이 그문제를 붙잡기로 했다. 예선때 F I J 가 동시에 돌면서 우왕좌왕했는데, 3PC일때는 혼자 하나씩 잡아도 큰문제가 없지만 1PC에서는 그래야 할 것 같았다.

---

A. 더위 피하기

Solve : Diordhd, Coffeetea, Gratus907

Code : Diordhd

 

2018 본선 당시 정답 팀 48 (45 + 3) -> + 는 아마 스코어보드 프리즈 전/후를 나눈 것 같다.

 

$x, y$의 범위가 $10^5$ 이지만, 어차피 $T$ 초 동안 이동할 수 있는 점은 출발점으로부터 Manhatten distance 가 $T$ 이하인 점들 뿐이며, $T$의 값이 200으로 매우 작다.

400 * 400의 정사각형 안에 갈 수 있는 점들의 후보가 모두 들어가고, 그 외의 어떤 점도 도달할 수 없음이 보장되므로, 적당히 좌표를 옮긴 다음 400 * 400 * T 의 dp 테이블을 채우는데, dp[i][j][t] 는 $(i, j)$ 에 $t$초만에 도달할 수 있는 방법의 경우의 수를 가지고 있으면, 총 3200만 칸의 업데이트를 통해 문제를 해결할 수 있다.

 

$t$ 초보다 짧은 시간에 목표에 도착하면 다시 나오지 않으므로 더하지 않아야 한다는 조건을 빼먹어서 1WA 적립.

 

3200만 업데이트가 메모리를 혼자서 200MB 이상 쓰긴 하겠지만,시간과 메모리 제한에 어쨌든 잘 들어올 것 같으므로 그냥 짜기로 했다. 솔직히 940ms씩이나 걸릴 거라고는 생각 못했는데...;;

---

솔루션을 완성한 후 Diordhd가 코딩하러 가고, 우리는 다른 문제를 생각하기로 했다. Coffeetea는 C번을 읽고 생각하고 있었고, 다같이 문제를 쭉 읽어보다가 내가 E번이 쉬운 문제임을 찾고 잡았다. 그리고 아마 혼자 풀어도 될것 같아 보였기때문에 Coffeetea를 C번에 버려두고 (...) 내가 혼자 E번을 풀었다.

---

E. Thinking Heap

Solve : Gratus907

Code : Gratus907

 

2018 본선 당시 정답 팀 47 (45 + 2)

힙에 적당히 1부터 $n$까지의 숫자들을 집어넣어서, $k$라는 숫자가 반드시 $p$번에 위치하게 하고 싶다.

힙에서 어떤 자리에 있기 위해서는, 그 $p$번의 부모 노드들에는 $k$보다 작은 수가 들어가야 하고, $p$번을 루트로 하는 서브트리에는 $k$보다 큰 수들만 들어가야 한다. 처음부터 이걸 맞춰서 집어넣어 주면 된다.

힙에서 부모 노드는 그냥 while문으로 찾으면 되고, 자식 노드는 재귀로 찾았는데 (...) 생각해보니 이것도 while로 짜면 더 간단했을 것 같다.

그리고 가장 작은 수 (1) 부터 작은 수들을 부모노드들에 집어넣고, 가장 큰 수 ($n$) 부터 큰 수들을 자식노드에 집어넣으면 된다. 사실은 가장 아래부터 큰 수를 서브트리에 넣으면 교체가 덜 일어나겠지만, 어차피 $k$ 외의 수들이 어디로 가는지는 내 알 바가 아니며, judge가 힙을 열심히 만들고 위치를 바로잡아서 그 결과만 맞으면 되기때문에 서브트리에는 아무렇게나 넣어도 된다.

그리고 그 외의 숫자들도 아무렇게나 넣는다. 어차피 $p$번 노드의 부모와 자식노드들만 관리하면 나머지는 어딘가로 옮겨지든 말든, 자기들끼리 교체되어도 상관 없다.

---

Coffeetea는 C번이 풀 만 하다고 주장했고, 실제로 몇가지 좋은 관찰들을 발견했다. 50분 가량 C번을 붙잡은 보람이 있었는지, A번을 풀고 C번에 빨려들어간 Diordhd와 함께 $\mathcal{O}(n^2)$ 솔루션 처럼 보이는 것도 찾았고($n = 200,000$ 이다...) 이걸 어떻게 잘 최적화해서 $\mathcal{O}(n)$이나 $\mathcal{O}(n \log n)$ 에 찾아야 하느냐, 뭐 이런 얘기들을 하고 있었다. 그동안 일단 나는 남은 문제들을 한번 쭉 읽어보고 C번으로 돌아가기로 했다.

---

J. 아기 석환 뚜루루 뚜루

Solve : Gratus907

Code : Gratus907

 

2018 본선 당시 정답 팀 50 (49 + 1)

 

시키는 대로 잘 구현하면 된다. 배열에 미리 14단어 집어넣고 잘 돌려 주자.

---

이제 계획대로라면 내가 다시 C번으로 돌아가서, 같이 풀 만해 보이는 C번을 공략해야 하는데, 내가 일단 지금까지 진행된 C번에 대한 논의들을 이해하지 못했다. 컴퓨터가 비는 상황도 너무 마음에 안 들기도 했고.

 

이 시점쯤 팀원들에게서 점점 더 복잡한 솔루션들이 나오고 있었고, 둘이 같이 "이거 이렇게 이렇게 줄이면 일단 돌긴 하나?" 와 함께, "맞다고 쳐도, 우리가 짤 수는 있냐?" 라는 말들이 나오고 있었다. 그런데 솔직히 지금까지 찾아낸 관찰들이 너무 아쉬웠기 때문에, 내가 다시 앞으로 나가면서 문제들을 읽어보기로 했다. 결과적으로는 한명이 앞으로 나가는 상황이 되면 그나마 문제 유형을 덜 타고 밸런스가 비슷한 편인 내가 가는게 낫기는 했는데, 실제 셋이었다면 솔직히 여기서 과감히 결단을 내리고 C를 포기했어야 한다는 생각도 든다. 

---

H. Make Similar 

Solve : Gratus907, Diordhd

Code : Gratus907

 

2018 본선 당시 정답 팀 30 (19 + 11)

 

사실 30솔브보다는 많을 줄 알았는데...흠...

$n$ 개의 숫자가 주어질 때, 어떤 수를 다른 수에 더하는 연산을 원하는 만큼 할 수 있다. 연산을 끝낸 후에 최댓값과 최솟값의 차를 최소화해야 한다. 

음수와 양수가 둘 다 있다면, Extended Euclidean Algorithm을 이용하여 전체 배열의 gcd를 찾을 수 있고, 이 gcd (이걸 $g$ 라고 하자) 들을 잘 더하고 빼서 모든 수를 0으로, 하나를 $g$로 만든 다음, 전부 $g$로 만들면 차가 0이 된다.

---

K. 간단한 문제

Solve : Gratus907, Diordhd

Code : Gratus907

 

2018 본선 당시 정답 팀 14 (8 + 6)

 

사실 따로 포스팅하고 싶은 문제이므로, UCPC가 끝나고 포스팅하기로 하자.

대충 얘기하면, 모든 $B_i$를 $A_i$의 배수만으로 고정해도 원하는 결과를 항상 만들 수 있다고 일단 믿으면, 다음 식을 만족하는 수열 $x_i$ 를 찾는 것으로 문제를 해결할 수 있다.

$$1 + \frac{2^m-1}{n} = \prod \frac{1+x_i}{x_i}$$ 

이러한 $x_i$ 가 항상 존재함은 이진법을 잘 활용하여 증명할 수 있다. 실제로는 더 쉽게 푸는 방법은 이걸 재귀적으로 잘 풀어 쓰면 매우 쉽게 보일 수 있는데 (귀납법이 잘 적용되며, 코딩은 재귀적으로 쉽게 할 수 있다), 연습 중에는 재귀적인 생각이 잘 안 들어서 그냥 Straightforward하게 보이고 들어갔다.

---

나랑 Diordhd가 레이팅에 비해 수학에 강한 편이기도 하고, 이런 문제들을 좋아하기도 해서 나름 재밌게 풀었다. 그동안 Coffeetea가 C번과 G번을 보다가, 계속 여러 관찰들을 찾아냈지만 문제 해결의 키 스텝에는 접근하지 못했다.

이때쯤, 사실 C번이 매우 어려운 문제인 것 아닌가? 라는 생각이 들었고, 결과적으로는 그 생각이 맞았다. 

 

K번을 AC 받은 시간이 180분 정도쯤이고, 2시간이 남아서 Coffeetea가 Piet을 코딩하러 갔다. Piet은 진짜 빡구현 문제로, 시키는 대로 잘 구현하면 되지만 시키는게 너무 많아서 오래 걸리는 문제였는데, 우리중에 이런걸 그나마 맞출 희망이 조금이나마 있는게 Coffeetea뿐이라서...

그렇게 2시간동안 끝없이 출력 초과를 받다가 라운드가 끝났다.

---

결과적으로는 이정도 솔브 / 페널티는 20등대 성적으로, 우리 팀의 올해 예선 성적 (43등) 이나 본선에서의 목표 (35등~40등만 했으면 좋겠다;;;) 에 비해서는 많이 높다. 그런데 사실 과정으로는 조심해야할 문제가 많은데

 

- C번에 묶여서 Coffeetea가 300분 중 180분 이상을 쏟아붓고, 결국 우리 현재 코딩 실력으로는 풀 수 없다는 것을 깨달았다. (다행히, 문제에 필요한 관찰들은 거의 다 찾아냈었는데, 확실히 오래 생각하는 것이 의미가 없지는 않은 듯 하다) 어쨌든, 현실적으로는 "빠르게 풀 수 있는 문제들을 먼저 풀기" 는 중요한 전략이다.

 

- 그래서, J번 같이 다른 팀이 10~20분만에 찾아내서 챙겨간 솔브도 69분이나 걸렸고, H번도 꽤 많은 페널티를 먹었다. 페널티 관리를 해야한다면 초반이 가장 중요하긴 하니까..

 

- Coffeetea가 그냥 처음부터 끝까지 고통만 받았다. 대신 수학틱한 문제들 구현을 내가 했는데, 내가 꼼꼼한게 떨어지긴 하지만 팀원들에 비해 구현이 빠른 편이기도 하고, Diordhd나 Coffeetea중 한명이 거의 코딩 내내 붙어서 페어코딩을 해서 덜 틀리기도 했다. 페어코딩 자체는 필요하다면 애용해야 하는 전략인 듯 하다.