숫자가 적혀있는 코인이 $n$개 있다. 같은 숫자를 갖는 코인끼리는 같은 주머니에 넣지 못 할때, 필요한 최소 주머니 수를 구하는 문제다.
가장 많은 같은 값을 갖는 코인의 개수를 구하면 된다.
$a$개의 0과 $b$개의 1을 사용하여 string을 구성하는데 $s[i] != s[i + 1]$인 원소의 개수가 총 $x$개 이어야한다. 그런 string을 출력하는 문제다.
먼저, $a$가 더 크다고 가정해보자. 그러면 0으로 string을 모두 채운 후 $b$개의 1을 적절히 박아넣으면 된다. 먼저 $s[0]$ 에1을 넣고 x를 1개 빼자. 그 다음, x가 2 이상일 때 까지 $s[n - 2]$부터 2칸 간격으로 1을 채워 넣자. $x$가 0이면 $s[0]$에 딱 맞춰 남은 1을 오른쪽으로 모두 채워넣고, $x$가 1이면 $s[0]$의 1을 $s[1]$로 옮기고 $s[1]$에 딱 맞춰 남은 1을 오른쪽으로 채워 넣으면 된다.
만약 $b$가 더 크면 $a$가 0과 1을 서로 바꾸어 구현하면 된다. 두번 코드를 적을 필요 없이 무조건 $a$가 크다고 가정하고 0을 채우고 1을 박는 식으로 한 뒤, 만약 $b$가 더 크면 1과 0을 서로 뒤집어주면 된다.
10분동안 봐도 생각이 안 나서 갑분싸당한 문제. 여러가지 case가 막 떠올라서 어떻게 다 처리해줄지 고민하다가 그냥 C, D모두 풀고 다시 봤다. 이 문제에 거의 20분은 쓴듯.
$n$일의 온도가 주어지는데, 연속된 $k$일 이상의 온도의 평균의 최대값을 구하는 문제다.
부분합만 구할줄 알면 푸는 문제다. double형 쓰면 실수오차 없다.
$2^d$형태의 값을 갖는 동전 $n$개가 주어진다. 그리고 쿼리가 주어지는데, 각 쿼리마다 주어지는 값을 만들기 위해 써야하는 최소 동전을 출력하는 문제다.
가장 큰 동전부터 greedy하게 쓰면 된다. 동전을 하나하나 보면 O($q * n$)으로 시간초과가 뜰것이다. 동전의 종류는 최대 31개이므로 동전 종류마다 보면 O($q * 31$)이 된다.
처음엔 큰 순서대로 정렬해놓고 하나하나 지우려고 했는데 최악의 경우 O($q * n$)으로 나와서 map에 동전 개수를 넣어서 큰 순서대로 각 동전의 최대개수를 소모하도록 처리했다.
노드의 개수가 $n$개, 트리의 지름은 $d$, 각 노드의 degree는 $k$이하가 되도록 트리를 모델링해서 출력하는 문제다.
먼저, $k$가 1일 때 예외가 생기는데, degree가 모두 1이하가 되어야하므로 $n$이 2이고 $d$가 1이어야 YES가 되고 나머지 경우는 전부 NO다. 물론 $n$이 1인 경우도 생각해볼수 있는데 $d$가 1이상이므로 $n$이 1이면 무조건 NO이고 위에 말한 조건에 의해 같이 걸러진다.
$k$가 2이상인 경우를 보자. 지름이 정확히 $d$가 되야하므로 linked list형태로 $d + 1$개의 노드를 쭉 나열해놓자. 그리고 이 list에 노드를 추가해나갈건데, list의 양 끝에 추가해버리면 지름이 증가해버리므로 양끝 안쪽 점에만 추가할 수 있다. 양끝 안쪽 점들은 degree가 모두 2이므로 최대 $k - 2$개의 노드를 추가할 수 있다. 최대로 추가하고 나면 추가한 노드에 또 노드들을 추가할 수 있다. $k - 2$개를 추가한 노드들의 양끝(linked list의 양끝의 바로 옆점)점들에 추가한 노드에는 더 이상 추가하지 못한다. 그 외의 노드들은 degree가 1이므로 $k - 1$개의 노드들을 추가할 수 있다. 또 추가한 노드에 추가할 수 있는데, 이전에 추가함 노드들의 양끝 외의 노드들에 또 $k - 1$개를 추가할 수 있다. 이 과정을 반복하면 된다. 더 이상 추가할 수 없는데 마지막에 추가한 노드의 번호가 $n$보다 작으면 NO이고, 아니면 트리를 출력해주면 된다.
한 10분 생각하고 이 방법을 생각해냈는데 생각보다 구현이 힘들었다. 재귀로는 너무 복잡해보여서 for문으로 구현했는데 그래도 복잡하다. 구현하고 쳐낼것 쳐내니 깔끔해지긴 했는데 그래도 복잡하다.
contest 끝나고 1시간 정도 구현하고 제출하니 ac받아서 마음놓고 잤는데 system test에서 틀려서 다시 구현했다. 그 만큼 구현이 까다로웠는데, 다른 사람들도 contest중에 푼 사람이 200명이 넘었는데 hack에서 거의 150명이 날라가고 system에서 2~3명 정도 날라간 것같다.
코포 데뷔전이었는데 무난하게 풀었음에도 불구하고 바로 blue로 떡상했다. div3업데이트를 알리는 소식의 댓글에 raing inflation얘기가 여러개 들렸는데 그도 그럴것이 B번을 이렇게 늦게 풀었음에도 불구하고 바로 blue로 올라가버리니 분명 문제가 있는것 같다.
