230716 팀 연습 (LARC 2016)

셋 : https://www.acmicpc.net/category/detail/1572

스코어보드에 나타나는 각 팀의 구성 인원은 아래와 같다. 마찬가지로 3시간 N컴 환경으로 진행하였다.
team_000102 : leo020630, minsung05
menborong : menborong
slahpasa : slah007, pasa3232

 

minsung05가 앞, 내가 뒤를 보고 시작했다.
 
~0:02
minsung05가 가장 쉬운 문제인 A를 풀어주었다. 
 
~0:07
F를 읽고 풀었다. 그냥 브론즈 구현 문제였다.
 
~0:37
minsung05는 스코어보드에서 풀린 D를, 나는 G를 잡았다. G는 대충 읽어 보니 아는 문제였다. SCPC와 20 선발고사에 나온 기출문제와 완벽히 똑같은 형태라 얼른 짜서 맞았다. 이후에는 minsung05가 D를 물어보길래 대충 될 것 같은 방법을 말해주고 다른 두 팀이 모두 푼K를 보러 갔다.
 
~0:57
minsung05가 D를 짜서 맞았다. 나는 그 사이 K를 좀 생각해봤는데, 처음에는 그냥 구현인 줄 알았지만 더 생각해보니 플로우로 될 것 같았다. 어차피 2컴 연습이었기에 플로우를 짤 줄 아는 minsung05에게 모델링을 설명해주고 짜게 시킨 후 다른 문제를 보러 갔다.
 
~1:12
J를 봤는데, 예제에서 나올 수 있는 코드가 아무리 생각해도 하나라 그대로 내서 맞았다. 그 후 스코어보드에서 풀린 B를 좀 봤으나, 잘 모르겠어서 다른 문제인 H를 보러 갔다.
 
~1:40
minsung05가 K를 열심히 짜서 냈지만 틀렸다. 코드를 열심히 보던 나는 모델링을 뭔가 잘못 했다는 사실을 알아차렸고, minsung05의 코드에서 몇 글자를 바꿔 내 맞았다. 이후 minsung05는 B를 보러 갔고, 나는 H를 마저 풀었다.
 
~1:44
K를 푸는 동안 H도 조금 짜놓은 상태였는데, 1번 틀려서 틀린 것 같은 부분을 고쳐 냈더니 맞았다. 솔직히 증명을 좀 대충 했는데 맞아서 다행이었다. 

 

~2:06

이후 minsung05는 B의 풀이를 찾아 코딩에 들어갔고, 나는 C를 봤다. 크게 어려운 문제는 아닌 것 같아서 조금 생각했더니 풀이의 가닥이 나와서 짰다. 이 문제는 다행히 예제가 강해서 한번에 맞을 수 있었다.

 

~2:57

나는 E를 열심히 고민했지만 모르겠어서 포기했다. 이후 minsung05가 완성한 B 코드를 계속 제출했는데, TLE를 받았다. 코드를 대충 보니 뭔가 느려 보이는 부분이 있어서 이를 빠르게 고치니 AC를 받았다. 다행히 1등과 같은 솔브 수로 마무리할 수 있었다.
 

문제별 요약

A (B4, solved by minsung05) : 문제를 읽지 않았다. 대충 쉬운 브론즈 문제라는 것 같다.
B (P3, solved by minsung05, leo020630) : 집합에 속한 모든 원소들이 degree에 대한 부등식 조건을 만족하는 최대 크기의 집합을 찾아야 한다. 우선 모든 정점을 집합에 넣고, 만족하지 않는 원소를 하나씩 제거해주면서 연결된 정점들의 degree를 갱신해주자. (차수, 정점 번호)의 pair를 원소로 하는 set을 관리해주면 쉽게 구현할 수 있다.
C (P4, solved by leo020630) : 모든 점이 격자점이기 때문에 180도만이 유효한 각도임을 유추할 수 있다. 따라서, 중심점을 고정하고 해당 점을 중점으로 하는 선분의 개수를 구하자. 해당 중점이 입력으로 주어졌는지에 대한 여부만 잘 생각하면 전체 경우의 수를 조합으로 계산해 줄 수 있다.
D (G5, solved by minsung05, leo020630) : 큰 수들이 중앙에 최대한 모여 있는 것이 최적이다. 넓이는 간단한 수식으로 계산해주면 된다.
E (D5, Not solved) : 문제를 읽었는데 풀이를 찾지 못했다.
F (B3, solved by leo020630) : 하라는 대로 구현해주자.
G (P2, solved by leo020630) : 우선 문자열의 각 값을 (자기 자신 이전에 있는 가장 가까운 같은 문자와의 거리) 로 바꾸어주면 대강 매칭이 된다. 처음 등장했다면 -1 등으로 사용해주면 된다. 이렇게 변환했다면 KMP를 돌려주면 되는데, 이 때 등호 기준을 조금 바꿔주어야 한다. 실제 배열에서는 -1이 아니지만 현재 고려하는 부분문자열에서는 -1로 취급해야 하는 경우가 있기 때문이다. 이를 잘 생각해서 구현해주면 문제를 해결할 수 있다.
H (P5, solved by leo020630) : \(K+1\)의 배수마다 무료 이용권이 하나씩 주어진다. 따라서 \(K+1\)의 배수일 때는 일단 무료 이용권을 써 주고, 그렇지 않을 때에는 현재 쓰고 있는 이용권의 가격들 중 바꿀 수 있는 것이 있다면 바꾸어주면 된다.
I (D4, Not solved) : 문제를 읽지 않았다.
J (G3, solved by leo020630) : 주어진 수보다 작은 소수 중 최댓값이 답이다. 소수간의 간격이 충분히 작아서 주어진 수에서 1씩 줄여가며 루트 시간복잡도로 소수인지 확인해주면 된다.
K (P2, solved by minsung05, leo020630) : \(i\)가 늑대라고 가정하자. 그러면 후보에 \(i\)를 포함한 사람들은 무조건 늑대에 투표할 것이다. 이런 사람들의 수를 \(M\)이라 하자. \(M\)이 1 이하이면 늑대가 항상 이기므로 2 이상이라고 가정하겠다. 사람->투표 관계를 마치 이분 매칭처럼 모델링해보자. 늑대도 아니고, 늑대를 투표할 수도 없는 사람들에 대해서 싱크->사람으로 용량 1의 간선을, 사람->두 명의 투표 후보에 각각 용량 1의 간선을 연결해주자. 싱크 쪽에서는 늑대가 지려면 다른 모든 후보의 득표수가 \(M\)보다 작아야 하므로, 늑대가 투표할 수 있는 두 사람에 대해서는 용량 \(M-2\), 다른 사람들에 대해서는 \(M-1\)의 간선을 싱크와 연결해주면 된다.
 

느낀 점

나름 풀 만한 문제는 다 푼 것 같다. 대회 중에 정신을 더 똑바로 차려야겠다고 생각했다.