2017-2018 ACM-ICPC NEERC Northern Subregional 복기글

지난번에 이어서 다시 모여서 셋을 돌기로 하였다. 셋 선정에 관해서는 또 rkm0959님께 신세를 졌고, 추천해 주신 셋 중에 갑자기 lotus가 무조건 매운맛으로 돌자고 하는 바람에 2017-2018 ACM-ICPC NEERC Northern Subregional로 돌게 되었다. solved.ac 기준 4다이아 1루비인 무서운 셋! stonejjun,lotus(easrui),karuna 가 같이 돌게 되었다.

백준에서는 https://www.acmicpc.net/category/detail/1795 에서 볼 수 있다.

결과는 다음과 같다.

 

 

솔직히 정말 많이 놀랐다. 이정도 성적이면 이대로 바로 대회를 나가도 꽤나 준수한 성적을 거둘 정도의 상황이 나왔다. 셋을 추천해주신 rkm0959님도 조금 놀라시더라... 이렇게 된 이유에는 내가 기복이 말도 안되게 심한 코더 중 하나인데, 오늘은 굉장히 좋은 컨디션이었던 것 같다. 

+레전드!! 2020.2.14 새벽 3:34에 D를 풀었다. 백준 기준 루비다!! 

A. Auxiliary Project

문제 : 성냥개비 n개가 주어진다. 그 성냥개비를 모두 사용하여 숫자 몇 개를 만든다. 이 때 만들어진 숫자의 합의 최댓값을 구하시오. 

풀이 : 7을 많이 만드는 것이 효율이 굉장히 좋아 greedy 적으로 풀 수도 있지만, 그러기 위해서는 해주어야 할 초반 값등의 예외처리가 많다. 그래서 DP로 짜면 훨씬 더 편하고 간단하게 문제를 해결할 수 있다.

여담 : 앞의 4문제를 보기로 한 Lotus가 굉장히 빨리 풀어줬다. 코포에서 충분히 볼만한 형태의 문제라고 생각한다.

B. Boolean Satis

문제 : 2sat과 비슷한 형태로 정의가 된 진위식이 주어진다. 이때 가능한 경우의 수를 구하시오.

풀이 : 문자열을 주는데, 이를 잘 분리하면 된다. ~a 와 a가 둘 다 있을 때, 하나만 있을 때, 각각 경우의 수에 어떤 영향을 끼치는지를 잘 살펴보고 식으로 풀면 된다. 

여담 : 난 아무리 봐도 문제 이해를 잘 못하겠다. 물론 4틀을 박아서 페널티는 포기 했지만, easrui가 가볍게 풀어냈다. 역시 그는 갓이야!

C. Consonant Fencity

문제 : 영어 단어가 주어진다. 이 때 알파벳 몇 개를 대문자로 바꾼다. (같은 알파벳은 다 같이 바꿔야 한다.) 그 상황에서 문자열의 값은 연속된 두 문자가 둘 다 자음이며, 대소문자가 다른 쌍의 갯수이다. 문자열의 값이 최대가 되도록 대소문자를 바꾼 단어를 출력하시오. 

풀이 : 자음이 총 19개라고 주어졌으므로 노드가 19개인 그래프를 생각하자. 이때 인접한 두 개의 자음 하나당 그 두 개의 자음에 해당하는 노드사이에 가중치를 부여하는 것이다. 이 때 노드에 색을 잘 부여해서 양 끝의 색이 다른 가중치의 합이 최대가 되게 하면 된다.
사실 말을 거창하게 해놨지만, 총 가짓수가 2^19로 다 해보면 된다.

여담 : Lotus가 문제를 읽고 그래프 문제로 변형 시켜 주었다. 내가 슬쩍보고 2^26이 몇인지 물어봤는데, 시간 초과가 날만한 숫자였다. 이후에 karuna가 26이 아닌 19임을 보고 코딩을 시작해서 바로 풀어냈다.

D. Dividing marbles

문제 a,b,c,d 가 주어진다. 총 구슬의 갯수 n은 2^a+2^b+2^c+2^d이다. 이 때 우리는 최소횟수의 시행으로 모든 구슬 그룹의 크기를 1로 만들어야 한다. 할 수 있는 시행은 크기가 a인 모든 그룹을 b+c=a인 크기 b의 그룹과 크기 c인 그룹으로 나누는 것이다. 이때 최소 횟수와 그 방법을 출력해야 한다. 

예제 : 예를들어 1,0,1,0을 입력받으면 총 구슬의 갯수는 6개이다. 이는 3번의 시행으로 가능하다. 
1. 크기가 6인 모든 그룹을 3,3으로 쪼갠다.  현재 상태 3,3
2. 크기가 3인 모든 그룹을 2,1으로 쪼갠다. 현재 상태 2,1,2,1
3. 크기가 2인 모든 그룹을 1,1으로 쪼갠다. 현재 상태 1,1,1,1,1,1

풀이 : 예외가 어느정도 있는 풀이와 특수한 상황의 예외를 처리해 준 풀이를 더하니까 맞았다. 알고보니 그 특수상황이 예외의 전부였다. 이 문제는 흠... 딱히 풀이를 밝히고 싶지는 않아 일단은 풀이를 생략하려고 한다. 풀이를 작성했다. 링크는 여기다.

여담 : 끝나고 이상한 풀이 시도해보다가 하루 동안 잊고 있다가 코포 끝나고 easrui랑 같이 고민했다. 진짜 별의별 상황 분류를 하고, 그 경우에 대한 처리 과정을 찾았는데, 생각보다 빠르게 보였다. 굉장히 재미있고 매력있는 문제였다. 결국 새벽 3시 30분에 맞았습니다!를 받았는데, 루비를 손으로 풀었다는 기분이 너무 행복했다.

E. Equal numbers

문제 : N이 주어지고 길이 N의 배열이 주어진다. 우리는 이 배열에 시행을 할 수 있다. 한 시행은 배열의 어떤 한 원소에 임의의 수를 곱하는 행동이다. 시행을 0번 했을 때 부터 n번 했을 때까지 각각 배열에 나타날 수 있는 서로 다른 숫자의 최솟 값을 구하시오.

풀이 :  몇가지 관찰을 해야한다. 숫자의 종류만 중요하니 그 숫자와 숫자의 갯수로 생각해 주어야 한다. n번 시행하면 다 최소 공배수로 만들어 줄 수 있고 따라서 값은 무조건 1이다. 
우리가 할 수 있는 행동은 두가지이다. 1.숫자 종류 하나를 선택해 존재하는 그의 배수로 만들어 주기 2. 숫자 두 종류를 선택해 둘 다 전체의 최소 공배수로 만들어주기. 둘 다 가짓수 하나를 줄이는 과정이지만, 1은 어떤 숫자의 배수가 존재할 때만 사용할 수 있다. 하지만 2를 한 번 사용해 준다면 언제든지 가능하다. 그대신 2는 숫자 두 종류의 갯수의 합이라는 디메리트가 있다.
따라서 우리는 두가지를 고려할 것이다. 2를 한 번도 사용하지 않는 경우와 시작부터 2를 쓰는 경우이다. 우리는 그리디하게 그 종류의 갯수가 적은 것 부터 지워나갈 것이다. 2를 사용하지 않는다면 초반에는 좋으나 후반에 효율이 떨어진다. 그와 반대로 2를 사용하게 된다면 무조건 갯수가 적은 것을 사용할 수 있으므로 일정 이후로는 더 좋을 것이다. 이 두 가지 배열을 저장한 후, 둘 중 작은 값을 고르면 된다. 

여담 : 내가 본 문제중 그나마 풀 수 있는 문제였다. 이런 저런 경우를 많이 대조해보고 특징들을 관찰한 후 직관적으로 종합해서 풀었다. 딱 내가 푸는 스타일이지만, 경험을 통해 '당연히 이렇지 않을까?' 하는 부분이 많아서 작성한 풀이가 이해하기 어려울 수도 있다. 굉장히 좋은 문제였다고 생각한다. 

F. Fygon 2.0

문제 : for문이 주어졌을 때, 시간복잡도의 차수와 최고 차항의 계수를 구하시오.

풀이 : 뭔가 위상정렬 가짓수 세면 될 것 같은 느낌? 

여담 : 문제를 보자마자 당황했다. 그런데 생각보다 다른 팀들이 많이 풀었던 것 같다. 위상정렬 가짓수가 맞는 지는 모르겠지만, 맞다면 비슷한 문제를 풀어봤을 것이라고 생각한다.

G. Grand test

문제 : 노드와 간선이 주어졌을때(더블 엣지는 없다), a에서 b까지 중간에 어떤 노드도 겹치지 않는 서로 다른 세가지 경로가 있는 a,b 가 존재하는지 구하시오. 있다면 그 세가지 경로를 출력하시오. 

풀이 : 여러개의 컴포넌트가 있을 수도 있으니 하나에 대해서 만 이야기 하려고 한다. dfs 트리를 만들어 보자. 이때 트리에 사용되어지지 않은 간선은 모두 벡에지라고 칭한다. 하나의 백에지는 어떠한 구간을 담당한다. 그러한 구간이 두 개 이상 겹치는 간선이 있으면 a,b 가 존재 한다고 할 수 있다. 이를 구하기 위해서 모든 백에지에 대하여 아래노드에 +1 윗노드에 -1을 더해준다. 그러면 tree dp를 통해 각 노드를 포함한 서브트리의 합을 구할 수 있을 것이다. 이를 어떤 노드의 값이라고 하자. 이때 노드의 값이 2이상인 노드가 있음과 문제에서 만족해야하는 조건을 만족함은 동치이다. 
 판별은 했으니 경로 3개를 구해야 하는데  시작지는 값이 2이상인 노드이며 목적지는 그 노드의 조상중 최초로 노드의 값이 1이하가 되는 노드이다. 경로는 진짜 다 해보는 느낌으로 해주어야 한다.

여담 : Lotus가 dfs트리를 예기했고 그래서 꽃히게 되었다. dfs트리에서 여러가지 상황을 그려본 결과 확신은 없었지만, 대충 서브트리 합>=2 를 보면 될 것 같다는 관찰을 했다. 사람들이 거의 못푼문제의 풀이를 발견하여 기뻤지만, 사실 이 문제는 구현, 경로 찾기 부분이 어려운 문제였다. 난 구현에 자신이 없어 풀이를 들고 Lotus에게 맡겼고, 갓-Lotus가 13틀을 박고 끝나기 5분전에 풀었다. 

H. Hidden Supervisors

문제 : n 이 주어지고 2~n까지 각 노드의 부모가 주어진다. 1은 항상 루트이며 주어지는 숫자에 0이 있는데 이 경우는 그 노드에 대한 부모가 아직 정해지지 않은 상태이다. 우리는 트리에서 그룹을 만들어 줄 것이다. 한 그룹은 2명이며 바로 부모와 자식관계이다. 한 노드는 최대 한 개의 그룹에만 속할 수 있다. 이때 1을 제외하고 아직 정해지지 않은 노드들의 부모를 잘 정해서 전체 트리에서 만들 수 있는 팀의 갯수가 최대가 되도록 해야한다 그때의 팀의 갯수와 각 노드의 부모를 출력한다.

풀이 : 일단 문제의 상황을 트리 몇 개가 있고 그 트리를 1번에 붙이는 형식으로 진행 될 것이다. 기본적인 상황에서 만들 수 있는 그룹이 있을텐데, 어떤 새로운 트리를 붙일 때마다 최대 한 개의 그룹이 더 생길 수 있다. 붙이는 트리의 루트가 아직 선택이 안되었고, 또다른 아직 선택이 안된 노드가 있다면 그 노드를 부모로 가짐으로서 그룹을 만들 수 있다. 어떤 노드가 처음 상태에서 그룹에 사용되어지는지에 대한 여부는 맨 처음에 greedy 또는 dp로 해결 가능하다. 

여담 : 문제를 보고 greedy가 생각이 나서 전체적인 아이디어를 던졌다. Karuna와 이야기 하며 세부적인 아이디어를 다져나갔다. 코딩은 내가 방송으로 보면서 Karuna가 코딩을 하였고, 확실한 것을 좋아하는 Karuna는 greedy대신 tree dp를 선택했다. 예외처리가 좀 있었지만, 생각보다 할 만한 문제였다. 라고 하기에는 코딩을 내가 잡았으면 못 풀었을 수도 있다. Karuna의 구현력이 진짜 대단한 것 같다. 

I. Intelligence in Perpendicularia

문제 : 볼록다각형이 주어진다. 위, 아래 왼쪽, 오른쪽 어디서 봐도 보이지 않는 둘레의 길이를 구하시오. 

풀이 : 바깥에서 보이는 길이는 직사각형의 둘레와 일치하므로 전체에서 그만큼 빼면 된다.

여담 : 우리는 편하게...

K. Kotlin Island

문제 : n*m 필드에 가로줄 또는 세로줄을 웅덩이로 만들 수 있다. 이어진 필드의 그룹의 갯수가 정확히 k개가 되는 방법을 있으면 출력하시오.

풀이 : 양쪽을 웅덩이로 만듦으로서 하나의 필드 줄을 만들 수 있다. 이렇게 세로 필드 줄 * 가로 필드 줄이 총 필드 그룹의 갯수가 된다.

여담 : 생각보다 많이 예외 처리도 해야하고 까다로울 것 같은데 Kauna가 깔끔하게 풀어냈다.

L. Little Difference

문제 : 수 n 이 주어질 때 그 수를 최대 1차이 나는 수들의 곱으로 표현하는 방법을 모두 출력하시오.

풀이: n으로 표현 가능하다. n^(1/2) 스케일의 숫자 2개로 표현이 가능할 수도 있다. n^(1/3)의 스케일 3개로 표현이 될 수도 있다. 이때 최대 횟수가 정해져 있고 각 상황에 따라 정수들의 곱으로 제대로 표현이 가능한지를 확인해 주면 된다.

여담 : Lotus가 자신의 풀이를 의심하면서 풀었다!! 실수오차 때문에 조금 애를 먹었지만, 정풀이 맞았다.

 

후기

굉장히 좋은 문제들이었다. 4/4/4문제씩 문제를 읽었는데 운이 좋았던 것 같다. 나는 풀이를 열심히 만들었지만, 둘의 구현력이 굉장히 부러웠다. 앞으로 많은 대회들을 위해서 나도 구현력을 열심히 키워야 할 것 같다..