Codeforces Global Round 4 후기

https://codeforces.com/contest/1178/standings/participant/26499798#p26499798

결과적으로는 만족스러운 라운드였다. :)

 

A. Prime Minister

그리디하게 가져올 수 있는 파티를 다 가져오면 된다. A번치고 문제가 길어서 읽기 힘들었다.

 

B. WOW Factor

o하나당 (좌측에 있는 w개수*우측에 있는 w개수)를 더하면 되고 왼쪽에서 오른쪽으로 순차적으로 보며 카운트를 잘 관리하는 식으로 O(n)에 풀 수 있다.

 

C. Tiles

대회 중에는 처음에는 dp쪽으로 생각해보다가, 예제를 보고 2**(w+h)라는 식을 찍어서 냈고 맞았다.이 식이 맞다고 확신한 결정적 계기는 14분여쯤에 맞은 사람 수를 봤는데 200명이 좀 넘었다. 정말 dp였으면 그랬을리가 끝나고 다시 생각해 봤는데, 첫 행과 열이 결정되면 나머지는 모두 결정되고, 첫 행과 열을 결정하는 경우의 수가 2**(w+h)이라 이 식이 맞다. 이런 문제에서는 나머지를 모두 결정지을려면 무엇을 고정시켜야 하는지 생각해봐야 할것같다.

 

D. Prime Graph

우선 n이 prime일 경우, 사이클을 하나 만들면 변의 개수도 n이고 degree는 모두 2이기 때문에 조건을 만족함을 관찰한다.

 

나는 여기에서 n을 최대 3개의 prime의 합으로 분해하고 각 term마다 사이클을 하나씩 만든 후, 사이클을 가로지르는 edge를 edge개수가 prime이 될 때까지 그었다. 여기서 추가하는 edge가 노드마다 최대 하나씩만 붙으면 degree는 2 or 3이기 때문에 조건을 만족한다. 그렇지만 n=4일때를 처리하지 못해 하드코딩으로 넣어야 했고, 그 외에도 자잘한 케이스가 많았고 추가할 수 있는 edge를 최대화하기 위해(n/2보다 좀 적은만큼 추가할수 있을 것이다) 구현이 너무 복잡해졌다.

 

정해는 사이클을 만든다는 아이디어에서 훨씬 깔끔한 솔루션을 도출한다. 우선 n개의 노드로 사이클을 하나 만든다. 이 때 모든 degree는 2이고, 에지 개수가 prime이 될 때까지 degree가 2이고 adjacant하지 않은 노드 사이에 에지를 놓으면 된다. 이러면 추가할 수 있는 edge가 아마 floor(n/2)일것이고, 비슷하게 사이클에서 에지를 추가하는 방식임에도 불구하고 내 방식보다 훨신 쉽게 더 많은 에지를 추가할 수 있다.

 

문제를 풀면서 이유를 알수없는 뇌절로 "n을 prime크기의 사이클로 분해하면 edge개수도 prime이다"라는 결론을 얻었고, 그 결론을 그대로 믿고 코드를 다 짜놓고 뇌절을 발견해서 거기서 "어 이걸 어떻게 맞게 고치지" 해서 발전시킨 풀이가 내 풀이다. 일단 이런 뇌절을 줄여야 한다.. 결국 두 솔루션 모두 어느정도 맞는 풀이를 만들어 놓고, 맞는 부분을 유지하면서 틀린 부분만 맞게 만든다는 아이디어를 이용했는데.. 처음부터 여기에서 시작했으면 정해같은 좀 더 간단한 솔루션을 얻지 않았을까 하는 생각이 든다.

 

두 솔루션 모두 [n, 3n/2)정도의 범위에 prime이 하나 이상 있다는 사실을 이용한다. n이 작으면 prime밀도는 높기 때문에 확인은 따로 안하고 맞을 거라고 믿고 제출했다.

 

WA한번은 흥미로운(?) 뇌절이였는데, n을 prime의 합으로 분해할 때 n이 odd면 3짜리 term을 하나 빼놓고 남은 숫자를 원 2개로 분해해서 그 원 사이를 이었는데, 문제는 내가 그 원 2개의 edge개수가 prime인걸 확인한 후에 멈추고 3짜리 사이클을 추가했다는 것이다. 그러면 당연히 원래 prime이였던게 그냥 even number가 되죠.. 항상 side effect는 조심히..!

 

E. Archaeology

개인적으로 맞긴 맞았는데 내 풀이가 매우 더러웠던 문제였다. 내 알고리즘은 palindrome함을 유지하면서 내 방식 내에서 최대한 많이 그리디하게 문자를 집어넣은 방식이엿고, 그 팰린드롬이 원 문자열의 반을 넘어선다는 증명은 아예 없었고 감으로 IMPOSSIBLE은 없다고 생각했다. 동시에 두 consecutive character가 다르다는 걸 명시적으로는 사용하지 않았다. (결국 이게 없었으면 통과 못했을것도 같지만..)

 

정해는 비둘기집의 원리와 induction을 이용한 멋진 풀이이다. 길이가 4보다 길 때 왼쪽 끝 2개와 오른쪽 끝 2개 중에서는 반드시 2번 나타나는 character가 있고, 문제 조건에 의해 이 character는 한쪽에 쏠려있지 있다. 그 두 character를 골라서 답에 넣는다. 그러면 4개 character마다 2개씩 답에 포함되는 글자가 있고, 원래 문자열에서 양쪽에서 2개씩 inductive하게 줄여나가면 된다.

 

induction을 이용한 풀이는 항상 뭔가 뜬금없이 나와서 찾아내기 힘든 거 같다. 흠.. 생각해보면 두 consecutive character가 다르다는 걸 아예 사용 안하고 풀었으니 이걸 생각했어야 하고, palindrome자체가 inductive하게 정의 될 수 있으니 정의로부터 출발해봤으면 어떨까 하는 생각이 든다.

 

F1. Short Colorful Strip

재미있는 DP문제다. 아래와 같은 2가지 관찰을 하면 m^4 dp로 쉽게 전환시킬 수 있고, 결합법칙을 이용해 식을 잘 끄적여보면 거기서 m^3이 나온다. (01:54의 제출은 m^4여서 시간초과가 났다.)

 

1. i번 차레에는 반드시 (딱 하나 있는) i번 블록을 덮어야 하고, 거기서 왼쪽 또는 오른쪽으로 칠하는 부분을 늘릴 수 있다.

2. i번 차레에 이미 페인트한 segment를 가로지르거나 걸쳐서 페인트를 할 수는 없다. 또한, 페인트한 segment 안에서 칠할 때에도 i번이 있는 위치를 가로지를 수는 없다. 즉, (페인트 밖 왼쪽 블럭/i번 차레에 페인트한 블럭 중 i번의 왼쪽/i번이 있는 위치/i번 차레에 페인트한 블럭 중 i번의 오른쪽/페인트 밖 오른쪽 블록) 이렇게 5개의 서로 간섭할 수 없는 subproblem으로 잘 나뉜다.

 

subproblem을 찾았으면 [l, r]구간에서의 경우의 수를 구하는 dp[l][r]의 식은 금방 나온다. 아쉬운게 있다면 뭔가 써놓고 보니 별거 없는데 여기서 50분이나 쓴거? 이런 솔루션을 좀 더 빠르게 찾을 수 있도록 연습해야겠다. 이 문제에서는 칠하는 segment가 "currently painted with a single colour"여야만 한다는게 상당히 강력한 조건이였는데, 이 조건 덕분에 한번 칠해진 구간이 문제를 나누고 subproblem이 성립한거고.. 그러니까 이런 류의 조건에서부터 "아 이 조건을 이용하면 잘하면 독립된 subproblem으로 나눌 수 있겠구나!" 를.. 바로 떠올릴 수 있을까?

 

 

(TODO: F2번 업솔빙)