2019 함수컵 (FunctionCup) 후기

2019 함수컵 (링크) 에 Little Piplup 팀으로 참가했다. 

 

일단 OI 스타일의 문제와 Grader가 따로 있어서 터미널로 컴파일해야 하는 상황이 익숙하지 않아서 꽤 많은 시간을 날려 먹었지만 그런거치곤 나름 성적은 나쁘지 않았다는 생각이 든다. 특히 오늘은 내가 평소보다 좀 못하고, Coffeetea가 (컨디션이 꽤 안 좋아 보였는데도) 상대적으로 잘해서 팀 실력은 그대로였던듯? 

 

Score : 33등 (594점)

---

4-2 Museum

Solve : Coffeetea, Gratus907

Code : Coffeetea

Score : 100

세 배열이 주어지고, 각 배열의 $i$번째는 $i$번째 사람의 그 물건에 대한 취향을 의미한다. 세 물건 중 하나라도 취향이 겹치는 쌍의 개수를 찾는 문제.

포함-배제의 원리를 이용해 (1개 겹치는 쌍의 개수) - (2개 겹치는 쌍의 개수) + (3개 겹치는 쌍의 개수) 해주면 되고, 각각은 Counting sort 한 다음 $\sum \binom{n}{2}$ 해주면 된다. 

이런 류의 문제는 평소에 Diordhd가 정말 잘 캐치하는 편이고, 나도 나쁘지 않은 편이라고 생각하고 있었는데 Coffeetea가 정말 보자마자 순식간에 포배를 찾아버렸다. :fan: 

---

1-3 UNIQUE 

Solve : Diordhd, Coffeetea 

Code : Diordhd

Score : 100

둘이 얘기하는 동안 나는 1-2번을 긁고, 3-1번을 긁고 제대로 풀 생각을 하고, 4-2번을 코딩하는 등 돌아다녔기 때문에 전혀 못 들었다. 무슨 문제인지도 안 읽었고... 아무튼 잘 풀었으니 :dhk:

Diordhd가 코딩에서 조금 고생하는거 같았다.

---

3-1 CROSS

Solve : Coffeetea, Gratus907

Code : Coffeetea

Score : 100

한 변의 길이가 $d_o$ 인 정사각형의 네 꼭짓점에서 한 변의 길이가 $\frac{(d_o-d_i)}{2}$ 만큼인 정사각형을 잘라낸 십자 모향의 도형을 $d_i, d_o$ 십자가 모양이라고 부를 때, 주어진 $n$개의 십자가 중 $k$개를 골라서 $(0,0)$ 에 겹쳐 놓았을 때 겹친 부분의 최대 면적을 찾는 문제.

나는 처음에 dp를 이용하여 $k$가 작을 때 문제를 해결하는 방법을 찾고 그걸 발전시킬 생각을 하고 있었는데, Coffeetea가 정해를 찾았다. 

먼저, 십자가 모양들을 $d_o$ 의 내림차순으로 정렬한다. 

일단 앞에 있는 $K$개를 골라서 교집합의 $d_i$ 랑 $d_o$ 를 찾자. $d_o$ 가 내림차순으로 정렬되어 있었으므로 $d_o[k-1]$ 이 교집합의 $d_o$와 같고, $d_i$는 지금까지 챙긴 십자가 모양들의 $d_i$ 중 최솟값이므로 Priority queue의 top을 이용해서 찾는다.

그 다음 십자가 모양을 넣을 때, 만약 새로운 십자가 모양을 챙겨 넣는다면 $d_o$는 내림차순이었으므로 반드시 새로운 십자가의 $d_o$가 된다. $d_i$는 Priority queue의 top과 새로운 모양을 비교해서 찾을 수 있다. 더 나은 결과를 제공한다면 챙기고, 그렇지 않다면 버린다. 끝 번호까지 반복.

---

1-2 CHAIRS

Solve : Gratus907, Diordhd

Code : Gratus907

Score : 100

라운드 시작 5분만에 그리디로 55점을 긁을 수 있다는걸 파악하고 그리디로 긁었는데 55점이 아니라 87점이 나왔다. 이때 뭔가 이상하다는 생각이 들어서 넘어갔었다.

문제의 요지는 어떤 배열 $W$와 $C$가 주어지는데, '왕' 은 이 두 배열을 모두 볼 수 있지만 '신하' 는 $C$만 볼 수 있고 $W$는 하나씩 하나씩 신하에게 주어진다.

이때, '신하' 는 $W$의 원소를 $C$의 몇 번에 Assign할지를 판단해야 하는데, $W[i]$ 를 $C[j]$ 에 Assign하기 위해서는 $W[i] \leq C[j]$ 여야 한다. 최대한 많은 $W$의 원소를 assign하고 싶다.

'왕' 은 힌트를 하나 줄 수 있는데, 신하에게 long long 범위 안의 음이 아닌 정수 하나를 던져 줄 수 있다. 다만, '왕' 이 던져주는 수가 작을수록 높은 점수를 받는다.

 

첫 아이디어는 '일단 왕이 무슨 말을 하든 알 바 아니고 오는대로 Assign 가능한 가장 작은 $C[j]$ 에 Assign하자' 는 거였고, 왕은 그냥 적당히 뭔가 말하게 했더니 ($W[0]+W[1]*10+W[2]*100$ 이었나? 아무튼 기본적으로 그런게 설정되어 있길래 내버려 뒀다. ) 87점을 받았다. 그리고 이 문제를 잊어버리고 다른걸 생각하러 갔다.

 

생각해 보니, 왕이 미리 assign을 시뮬레이션 해보고 "몇 이하의 $W[i]$ 는 모두 assign 가능하다" 라는 정보를 말해 주면 신하가 그 값을 초과하는 $w$는 모두 버리면 된다. 이걸로 95점을 받았다.

한참동안 나랑 Diordhd가 이걸 어떻게 구겨넣어서 왕이 말하는 숫자를 줄일지 생각하다가, 첫 아이디어로 돌아왔다. 잘 보면, 어차피 왕이 말하는 정보를 신하가 무시할 계획이라면 왕은 그냥 0을 말해도 된다. 왕이 0을 말하고 greedy하게 배치하는게 100점 정해.

 

조금만 더 꼼꼼하게 읽고 차분하게 생각했으면 00:30분쯤 100점 AC를 받을 수 있었을 텐데 좀 아쉽다. 

---

2-2 BULB

Solve : Gratus907 

Code : Gratus907

Score : 36

리프 노드는 전구 (빨간색 또는 파란색) 이고 나머지 노드는 스위치인 이진 트리에서 게임을 하는데, 스위치를 켜고 끄는 행동을 두 플레이어가 $T$번씩 한 다음 결과가 빨간 전구인지 파란 전구인지에 따라 승자를 가르는 게임을 한다. 스위치가 켜지면 전기는 오른쪽, 꺼지면 전기가 왼쪽으로 흐른다.

꽤 많은 시간을 나는 이 문제에, Diordhd는 3-1에 투자해서, 둘다 꽤 많은 관찰들을 찾았다. 대략 처음 시점에서 임의의 $k$번 전구로 도달하기 위해 켜야 하는 스위치의 개수를 찾아야 한다는 것과, 어차피 후공은 선공의 행동을 캔슬할 수 있으므로 턴이 매우 많은건 별로 의미가 없다는 것도 알았다. 
노드가 많을 때 구현을 어떻게 해야 할지 잘 몰라서, $O(n^2)$ 구현으로 서브태스크를 긁어서 36점을 받았다. 정해를 보니 특별한 알고리즘이 필요한 거 같지는 않았고, 조금만 더 관찰해서 구현하면 되는 것 같다. ㅠㅠ

---

4-1 SQUAD

Solve : Diordhd, Gratus907

Code : Diordhd

Score : 19

먼가 쿼리 문제인데 쿼리를 처리하려면 Convex Hull 같은걸 사용해서 잘 처리해야 할 것 같았는데, 우리는 Convex Hull 관련 알고리즘을 아직 잘 모르므로 $Q = 1$ 인 첫 번째 서브태스크만 긁기로 했다. Diordhd가 거의 다 짜 놓은 코드에 내가 약간 숟가락만 얹어서 19점 긁고 다같이 1-1 Hiccup을 잡으러 갔다.

---

1-1 HICCUP

Solve : Diordhd, Coffeetea

Code : Diordhd, Coffeetea

Score : 100

$X$-Hiccup 문자열의 정의를 주고, 주어진 문자열이 최대 $X$-Hiccup 문자열일 때 $X$를 찾는 문제.

이런 유형의 문제는 많은 경우 Parametric Search가 좋은 접근인데, 코너케이스가 꽤 많아서 Coffeetea가 거의 2시간 가까운 시간을 코딩하고서도 $X = 0$ 과 $X = -1$ 케이스에서 걸려서 Diordhd가 일부 코드를 수정하고 내서 맞았다.

사실은 이렇게까지 오래 걸렸어야 할 일은 아닌거 같은데, 코드 짜면서 다같이 뇌절을 상당히 많이 했다. 

---

4-3 WINDOWS

Score : 39

windows OS 바탕화면에서 방향키로 파일 아이콘 간을 이동하는 규칙을 제시해 주고, $1000 \times 1000$ 그리드에 아이콘 1000개를 잘 뿌려서 임의의 아이콘 $p$ 에서 $q$까지 최소 횟수의 방향키 입력으로 도착하려고 할 때, 이 이동 횟수의 최댓값을 최소화하는 문제. (즉, 아이콘 간을 이동할 때 1에서 2는 3번, 2에서 3은 10번, 1에서 3은 4번에 할 수 있으면 $K = 10$ 이고 이 $K$를 최소화)

뭘 해야 할 지 전혀 모르겠길래 어떻게 나오나 싶어서 랜덤하게 점을 뿌렸더니 30점 조금 넘는 점수를 받았고, 시드를 바꿔 넣어서 1분에 한번씩 제출해 보면서 (각자 생일 같은거 넣어 보고...)  최대 39점을 얻었다. :uwek: 

정해는 K-ary 트리를 평행선을 기준으로 대칭한다 뭐 그런게 써있었는데 모르겠다.

---

방학 중에 팀연습 많이 돌다 보니 강점/약점이 조금씩 비슷해져 가고 있다는 생각이 들었는데 (상대적으로 구현과 그래프 계열 문제에 약했던 나랑 Diordhd가 그쪽에서 예전보단 많이 나아진 편이고, Coffeetea가 수학문제에서 직관이 굉장히 좋아졌다) 오늘은 Coffeetea가 4-2, 3-1 두문제를 순삭해버려서 내가 거의 할 게 없었다. 내가 한건 코딩 조금 하고 (이건 누가 하든 상관 없었다) CHAIRS 풀고 (사실 쉬운 문제였다는걸 한참 나중에 알아버린...) BULB 긁은거 정도? ㅠㅠ