[Codeforces] Codeforces Global Round 4

https://codeforces.com/contest/1178

 

몇일 전에 진행되었던 대회입니다. 썩 잘하지는 못했네요.

 

A - Prime Minister (Code)

 

그냥 넣을 수 있는 Party는 다 넣었을 때 값이 어떻게 되나를 보면 됩니다.

 

B - WOW Factor (Code)

 

DP table 2개가 각각 1부터 자신까지, 혹은 자신부터 끝까지에서 w의 갯수를 저장하면 됩니다.

 

C - Tiles (Code)

 

처음에 좀 헤맸는데, 잘 생각해보면 결국 제일 상단 혹은 제일 왼쪽의 타일을 자유롭게 배치하고 나면 나머지 타일들은 자신의 위와 자신의 왼쪽으로 인접한 색에 따라 놓는 방향이 고정됨을 알 수 있습니다. 그러므로 답은 $2^{w+h}$ 입니다.

 

D - Prime Graph (Code)

 

1, 2, 3, 4, ... , $n-1$번 노드는 그냥 알아서 edge를 2개 가지게 하고, $n$이 홀수면 $n-3$과 $n-1$을 추가로 이어준 뒤 $n$번 노드에 edge를 몇 개 붙일지를 정하면 됩니다. 이 때 $x$개를 더 붙인다고 하면 $x$의 범위가 $n-1$ 이하로 제한이 되기 때문에 $x$와 $x+n-1$(혹은 $x+n$)이 모두 소수인 $x$가 존재하지 않는 경우가 있다면 껄끄러울 뻔 했으나 직접 돌려보니 다 있길래 다행히 편하게 처리가 가능했습니다.

 

E - Archaeology (Code)

 

앞 2개, 뒤 2개 문자를 보면 그들중에 겹치는게 반드시 있고, 연속한 것은 같은 문자일 수 없다는 조건으로 인해 겹치는 문자는 반드시 앞에 1개, 뒤에 1개이므로 이런 식으로 계속 palindrome에 추가해나가면 됩니다.

 

F1 - Short Colorful Strip (Code)

 

대회중에는 해결하지 못한 문제였습니다. 색깔을 역순으로 배치하며 어떻게 해보려고 했으나 잘 안됐고, 나중에 풀이를 확인해보니 $D[i][j]$를 $i$부터 $j$까지 규칙에 맞게 칠하는 경우의 수로 두어 해결하는 문제임을 알게 되었습니다. 이 문제 정도는 풀어냈어야 했는데 아쉽네요.