총 $m$개의 참가팀에게 경품상자를 주는데 $n$개의 상자가 있다. 모든 참가팀에게 동등하게 나누어 주어야하므로 상자수는 $m$으로 나누어 떨어져야만한다. 그러기 위해서 $n$개의 상자 중 몇 개를 버릴 수 있고, 또는 몇 개를 더 만들 수도 있다. 만드는데 드는 비용 $a$와 버리는데 드는 비용 $b$이 주어질 때 $상자수 % m$이 0이 되기위한 최소 비용을 구하는 문제다.
문제 그대로 $(n \% m) * b$와 $(n - (n \% m)) * a$의 최소값을 구하면 된다.
접시에 $n$마리의 박테리아가 살고 있다. 박테리아들은 서로를 잡아먹을
수 있는데, $i$박테리아의 크기 $a_i$가 $j$박테리아의 크기 $a_j$에 대해 $a_i > a_j$이고, $a_i <_= a_j + k$이어야 $i$가 $j$를 잡아먹는다. 이 때 접시에 남아있을 수 있는 최소 박테리아의 수를 구하는 문제다.
일단 박테리아의 크기를 오름차순으로 정렬해보자. $i$번째 박테리아가 어느 박테리아에게 먹힐 수 있으면 먹히고, 그 다음 $i + 1$박테리아가 먹힐 수 있으면 먹히고.. 이렇게 greedy하게 선택하면 무조건 최적답이 나온다는 걸 알 수 있다.
( ~~하다보니 ~~한더라~ 하는 풀이를 제일 싫어하는데 ps에서 직감만큼 중요한게 없기 때문에 어쩔 수 없다. )
한 가지 조심해야할 점은, $i$번째 박테리아가 먹히는 가를 판단할 때 upper_bound로 체크해준 뒤, 그 index - 1에 해당하는 값이 $a_i$와 같은지 판단해야한다. $a_i == a_j$이면 박테리아는 서로 먹을 수 없기 때문이다.
나는 생각하기 귀찮아서 map과 unique를 이용했다. map으로 원소의 값의 갯수를 저장해두고(값이 작아서 그냥 배열써도 무관하다) unique로 같은 값을 가지는 녀석을 모두 제외시켜주면, $i$번째 박테리아가 먹히는 박테리아면 무조건 $i + 1$번째 박테리아에게 먹힐것이기 때문에 그렇게 처리했다. 근데 풀고나서 upper_bound로 풀어보니 더 간단하다.
C. Bracket Sequences Concatenation Problem
문제를 요약하면, 합쳐서 올바른 괄호열를 만들 수 있는 두 괄호열 쌍의 개수를 구하는 문제다.
먼저, 어떤 괄호열을 '합쳐도' 절대 올바른 괄호열이 될 수 없는 괄호열 부터 제외시켜보자. ")("같은 녀석들이 그 예이다. 이런 괄호열은 혼자 따로 노는 ")"가 먼저 나온 뒤 혼자 따로 노는 "("가 나오게 된다. stack을 이용하든 어떻게 하든 올바른 괄호열을 판단하는 방법으로 이런 괄호열을 판단이 가능하다.
절대 올바른 괄호열이 될 수 없는 괄호열을 제외시키고 나면 혹시 짝이 맞는 괄호열이 있으면 올바른 괄호열이 될 수 있는 녀석들만 남는다. 그럼 이제 "("의 개수와 ")"의 개수를 세어보자.
만약 "("의 개수가 더 많은 괄호열이면 "("의 개수만큼 ")"가 더 많은 괄호열을 '붙여주면' 올바른 괄호열이 될 것이다.
")"의 개수가 더 많은 괄호열이면 어떤 괄호열을 붙여도 올바른 괄호열이 될 수 없다.
마지막으로, 이미 올바른 괄호열이면 올바른 괄호열끼리 붙여주면 올바른 괄호열이 된다.
"("가 더 많은 괄호열, ")"가 더 많은 괄호열, 이미 올바른 괄호열을 각각 센 뒤에, ("("가 더 많은 괄호열의 개수 $*$ 그 개수와 같이 ")"가더 많은 괄호열의 개수)의 합 $+$ 이미 올바른 괄호열 $*$ 이미 올바른 괄호열 이 정답이다.
$n$개의 vertex를 가진 무방향그래프에서 connected component의 개수가 $a$이고, 그 complement그래프의 connected component의 개수가 $b$인 그래프의 인접행렬을 구하는 문제다. (크게 상관은 없으나 그래프는 loop-free다)
$n$이 2와 3인 경우를 제외하고, $a$와 $b$는 둘 중 하나는 1이여야 하며, 나머지 하나는 1보다 크거나 같고 $n$보다 작거나 같아야한다.
왜 그런지는 조금만 그려보면 알 수 있는데, connected component(이하 cc)가 1개인 녀석을 만드는 최소 edge는 $n$개의 vertex를 모두 연결하는 최소 edge개수이므로 $n - 1$개이다. 이런 graph를 뒤집으면 또 역시 cc가 1개인 것을 알 수 있다.
여기서 edge를 아무렇게나 여러개 더해도 cc는 1개이며, 뒤집은 cc의 개수가 줄어든다. (아마 줄어드는 패턴은 랜덤일 것이다.) 그렇게 edge를 더하다가 complete graph가 되어버리면 cc는 여전히 1개이며, 뒤집은 그래프의 cc는 $n$개 이다. 따라서 (1, 1) ~ (1, $n$)까지 만들 수 있는데, 뒤집은 cc가 줄어드는 패턴이 랜덤이므로 1~$n$까지 모두 만들 수 있는지는 모른다.
이제 반대로 edge를 trail을 유지하면서 1개씩 줄여보자. 1개의 edge를 줄일 때 마다 1개의 cc가 늘어나며 뒤집은 그래프는 여전히 cc가 1개이다. 따라서, 여기서 1~$n$개 모두 만들 수 있다는 점을 알 수 있다.
이 두 경우를 봤을 때 모두 뒤집은 cc나 안 뒤집은 cc나 둘 중 하나의 cc의 개수는 무조건 1이어야된다는 점을 알 수 있으며, 다른 cc의 개수는 1~$n$이면 모두 만들 수 있다는 점을 알 수 있다. 인접그래프는 trail을 만들어 주게(1 -> 2 -> 3 -> 4 -> 5... -> $n$)만들어 주면 된다.
예외로 언급했던 $n$이 2와 3인 경우 $a, b$둘 다 1 인 경우를 만들 수 없다.
문제가 어려워보여서 손 못 대고 E문제로 넘어갔는데 문전박대당하고 다시 돌아와서 풀었다.
무려 총 4번이나 틀렸는데 너무 잠이 와서 문제조건을 좀 이상하게 이해했다. cc가 $a$인 그래프에서 complement그래프의 cc가 $b$인 그래프를 출력해야하는데, 문제에서 그런 그래프가 있으면 아무거나 출력하라 한것을 cc가 $b$인 그래프의 complement가 $a$인 경우도 출력해도 된다고 이해해서 2번이나 틀렸다.
그 다음 2번은 2번 틀리고 문제 다시 읽고 고친다고 고쳤는데 조금 덜 고쳐서 잔여물이 남아있었다. 그것 때문에 또 2번 틀렸다.
E번 안 가고 그냥 생각했으면 문제 제대로 이해했을텐데 괜히 E번왔다가 이것 저것 생각한다고 머리가 뒤죽박죽된데다가 피곤해서 문제조건을 잘 못 이해하는 바람에 4번이나 틀렸다 ㅠ
길이 $n, [0, n - 1]$인 거리가 모두 어둡다. 거리의 각 지점에 램프를 달 수 있는데 $i$지점에 밝기가 $l$인 램프를 달면 $[i, i + l]$의 거리가 밝아진다. 그런데 거리의 어느 지점에는 램프를 못 달게 금지되어 있다. 램프의 개수는 무제한으로 제공되며 램프의 밝기는 $[1, k]$까지 모두 준비되어있다. 각 밝기의 램프의 가격이 주어졌을 때, 딱 한 종류의 램프만 사용하여 거리의 모든 지점을 밝히는데 필요한 최소비용을 구하는 문제다. 만약 모든 거리를 밝히지 못 할경우 -1을 출력해야한다.
일단, 자명한 점 하나는 연속적으로 금지된 지점의 최대 길이 이하의 밝기를 가진 램프로는 절대 모두 밝힐수가 없다. 그 다음 부터는 그냥 문제에서 설명한대로 그대로 구현해버리면 된다. $l$자리 밝기를 가진 램프를 선택한다면 $i$위치에서 $i + l$위치로 점프하고, 만약 그 위치가 금지된 지점이라면 그 위치에서 왼쪽에 있는 가장 가까운 금지되지않은 지점으로 가서 거기서 또 램프르 설치하여 $l$만큼 점프하고 하는 방식으로 가면 된다.
문제는 시간복잡도가 O($kn(=n^2)$)이 아닐까 싶지만, O($klogn(=nlogn)$)이다. $n*(1/1 + 1/2 + 1/3 + ... + 1/ n) == nlongn$이라는데 아무리 찾아봐도 증명이 안 나와있다. 위키에 증명이 있다고는 하나 없으니 패스..
문제 살짝 봤을때 아 이거 $n*(1/1 + 1/2 + 1/3 + ... + 1/ n)$에 풀리겠는데? 느낌을 받았는데 이게 $nlogn$이 아니라 그냥 $n^2$와 비슷해 지는줄 알고 넘겼는데.... 에라토스테네스의 체 시간복잡도 계산할 때 똑같은 방식을 쓰는데 그때 조금 봐둘걸 아쉬웠다.
