꽃 $A, B, C$가 한 줄로 피어있다. 꽃이 시들면 꽃이 있던 위치와 그 양 옆 한 자리에 꽃잎이 떨어진다. 꽃잎이 모두 떨어졌을 때, 한 위치에라도 $A, B, C$의 꽃잎이 모두 떨어져 있으면 Yes를 아니면 No를 출력하는 문제다.
문제 그대로 구현하면 된다. 꽃잎 3개가 모두 있는지 판단하기 위해 배열 3개를 쓸 필요 없이 bit로 처리해주면 하나의 배열로 간단하게 처리 가능하다.
$1, 0, '.'$으로 이루어진 기록이 있다. '.'은 각각 0이나 1롤 바꿀 수 있다. 그리고 정수 $p$가 주어지는데 이 정수는 주어진 기록의 주기이다. 여기서 '주기'란 모든 $0 <= i <= size - p$에 대해 $arr[i]$의 값과 $arr[i + p]$의 값이 같으면 $p$가 주기가 된다. $p$가 주기가 될수 없도록 '.'을 적절히 바꾸는 문제다.
정리하면 '.'을 적절히 바꾸어 어떤 $0 <= i <= size - p$에 대해 $arr[i] != arr[i + p]$가 되도록 바꿀 수 있는가를 묻는 문제다. 바꿀 수 있으면 바꾼 기록을 출력해야한다. 바꿀 수 없으면 No를 출력해야한다.
먼저, 배열을 돌면서$([0, size - p))$ $arr[i] == 0$이고 $arr[i + p] != 1$이면 바꿀 수 있는 경우다(이하 true). $arr[i + p] == '.'$이면 마찬가지로 true이며 $arr[i + p]$를 1로 바꾸어주면 된다.
반대로 $arr[i] == 1$이고 $arr[i + p] != 0$이면 true다. $arr[i + p] == '.'$이면 마찬가지로 true이며 $arr[i + p]$를 0로 바꾸어주면 된다.
이제, $arr[i] == '.'$인 경우를 생각해보면 무조건 true다. 그리고 $arr[i + p]$의 값과 다르게 $arr[i]$를 바꾸어 주면 되는데, $arr[i + p] == '.'$인 경우는 서로 다르게 바꾸어주면 된다. 그러면 모든 범위의 '.'이 알맞게 치환된다.
처음에 모든 $0 <= i <= size - p$에 대해서 $arr[i]$의 값과 $arr[i + p]$이 같으면 $p$가 주기가 된다고 한 것을 어떠한 $0 <= i <= size - p$에 대해서 $arr[i]$의 값과 $arr[i + p]$이 같으면 $p$가 주기가 된다고 이해 해버려서 엄청 어렵게 풀었었다. 그나마 다행인건 예제에서 바로 틀려버려서 제출을 안 했지 아니었으면 두 세번 제출해봤을거다..
그럼에도 불구하고 한 번 틀렸는데, $arr[i]$가 '.'이 아닐 때 $arr[i + p]$가 '.'이면 $arr[i + p]$를 바꾸어 주어야하는데 안 바꾸어줘서 '.'이 그대로 남아있게했다.
문제만 제대로 이해했어도 빠르게 풀었을 문젠데 괜히 20분 넘게 날려먹었다.
꽃 $A, B, C, D$가 있다. 이 꽃들은 $n * m$짜리 배열의 한 칸에 하나 씩 들어있다. 각 종류의 꽃들의 component의 개수가 주어진다. 이 때, 이런 component 개수를 만족시키는 배열을 출력하는 문제다.
너무 다양한 풀이가 있지만 내가 푼 방법을 설명하면,
배열의 크기가 최대 $50 * 50$이므로 그냥 배열의 크기를 $50 * 50$으로 고정시켜놓자. 그리고 배열을 전부 $D$로 꽉 채우자. 그 다음 ($A$의 component개수 - 1)개 만큼 $D$위에 덮어 씌울건데, $D$가 끊어져서 compoent가 생기지 않도록 덮어 씌울것이다. 그럴려면 배열 왼쪽 위부터 차례로 체스판 처럼 $row \% 2 == 0 \&\& column \% 2 == 0$이 되는 경우에만 채워주게 되면 최대 8줄 내로 $A$를 모두 채울 수 있다. 마찬가지로 $B$와 $C$를 채울 건데, $B$는 8번째 줄 부터, $C$는 16번째 줄 부터 채우면 24줄 내로 $A, B, C$를 모두 채울 수 있다.($A$는 1개를 제외하고 채웠으므로 하나 남았다.)
이제 $A$는 1개, $D$는 $D - 1$개 남았는데(배열전체로 채워져 있으므로)$A$를 배열의 제일 아래쪽부터 $A$가 component를 유지하고, $D$를 최대한 원래 큰 component에서 끊어지도록 잘 채우면 된다. 말로 설명이 어려우니..
$50 * 50$배열이 상당히 크기 때문에 생각보다 간단한데 배열이 크다는걸 생각 못 하고 compact하게 짜려고 하다보니 엄청 복잡해지고 예외도 많고 어렵게 느껴졌다.
속도가 1이거나 -1이고 크기가 $l$인 구름의 좌표가 $n$개 주어진다(좌표의 시작점이 구름의 왼쪽, 좌표 + $l$이 구름의 오른쪽이다). 우리가 임의로 바람을 불어주어서 구름의 속도를 바꾸어줄 수 있다. 두 구름 $i, j(i < j)$를 뽑아서 바람을 불어주었을 때, 두 구름이 겹치는 공간중에 영점이 포함되는 두 구름 쌍의 개수를 구하는문제다. 단, 바람의 최대 속도는 $w_m$으로 제한 되어 있으며 언제 만나는 시간은 상관이 없다.
먼저, 자명한 점은 속도가 1인 구름과 -1인 구름만 만날 수 있다는 점이다. 그리고, 속도가 1인 어떤 구름 왼쪽에 있는 구름과는 어떠한 바람을 불어도 절대 만날 수 없다. 따라서, 속도가 1인 구름과 그 구름 보다 오른쪽에 있는 속도가 -1인 구름쌍만 고려해주면 된다.
그리고, 바람을 불어서 구름의 속도를 변화시킨다고 하지말고, 바람을 불어 영점을 움직인다고 생각해보자. 어차피 상대속도는 똑같기 때문에 전혀 상관이 없다.
이제, 임의의 두 쌍이 조건을 만족해서 개수에 세아려지는지 어떻게 판단할지 생각해보자. 바람이 불면 영점이 움직이므로 두 구름이 만나는 지점은 항상 일정하다. 속도가 1인 구름과 -1인 구름이 처음 만나는 지점은 $x_{left} + l$와 $x_{right}$가 만나는 지점이 될것이고, 두 구름이 만나서 서로 겹쳐지는 면적이 커지다가 점점 작아지며 처음 만나는 지점과 같은 지점에서 서로 헤어질것이다. 처음 맞닥뜨리는 지점은 $(x_{left} + l + x_{right}) / 2$(이하 $x_{meet}$)이고, 그때의 시간은 $(x_{right} - x_{meet}) / 2$(이하 $t_{meet}$)이 될것이다. 헤어지는 시간은 $t_{meet} + l / 2$(이하 $t_{separate}$)이다. 이제, $t_{meet}$와 $t_{separate}$사이에 어떻게든 영점에 바람을 불어 $x_{meet}$를 지나가게 할 수 있다면 두 구름은 영점에서 지나가게 할 수 있는 것이다. 그런데, $w_m$이하로는 얼마든지 바람을 불 수 있기 때문에, 영점이 $w_m$속도로 $t_{separate}$미만의 시간에 $x_{meet}$를 지나가게 할 수 있으면 얼마든지 바람을 조절하여 두 시간 사이에 영점이 $x_{meet}$를 지나가도록 할 수 있을 것이다. 따라서, $t_{separate} * w_m$ 보다 $x_{meet}$가 작으면 그 쌍을 세어주면 된다.
그런데 두 점이 영점에서 겹치는 점인지 판단은 이렇게 한다고 치고, 모든 쌍을 다 보면 O($n^2$)의 시간이 걸려 TLE가 뜰것이다. 이거는 two pointer로 해결가능한데, 먼저 구름들을 오름차순으로 정렬하고 왼쪽부터 보자. 속도가 1인 구름($l$)을 하나 잡고, -1인 구름($r$)을 순서대로 잡는데, $r$이 가능하면 $r$구름 이후의 모든 구름은 가능하게 될 것이다. $l$과 $r$이 시각 $t$일 때 점 $x$에서 만난다고 하자. $l, r$쌍이 가능하다고 가정했으므로 영점은 $x$점을 지날것이다. $r$와 구름$r + 1$사이의 거리가 $a$이면 $l, r+1$쌍은 점 $x + a / 2$에서 만날것이고, 시각은 $t + a / 2$이다. 따라서, $a / 2$시간안에 $a / 2$이상 움직이면 $r + 1$구름도 정답이 될것이다. 그런데 $w_m$이 1이상 이므로 $r + 1$구름도 정답이 된다. 따라서 최초로 $l$과 쌍을 이루는 구름 $r$을 하나만 찾으면 바로 $l$과 쌍을 이루는 구름의 총 개수를 구할 수 있다.
또한, 마찬가지 방법으로 증명할 수 있는데, $l$과 쌍을 이루는 최초의 구름 $r$을 찾았을 때, $l$과 $r - 1$뿐만 아니라 $l + 1$과 $r - 1$도 쌍을 이룰 수 없다. 따라서, 투포인터로 속도가 1인 구름과 -1인 구름을 쭉쭉 닦아 나가면 O($2n$)이 걸린다. 정렬때문에 O($nlogn$)이 걸린다.
밤 10시부터 다음날 오후 3시까지 계속 계속 생각해서 풀었는데 그래서 그런가 생각한게 많아서 풀이가 좀 길다. 힘들어서 풀이를 봐도 와닿지도 않고 이해도 안 되서 조금의 도움만 받고 그냥 내 힘으로 풀었다. 무슨 짓을 해도 두 구름의 속도차가 2이기 때문에 똑같은 시간에 만나게 되어 있으므로 O($1$)로 두 구름이 정답이 될 수 있는지 판단할 수 있다고 생각했는데 바람으로 구름을 움직인다고 생각하니 계산도 복잡하고 머리도 복잡해져서 어떻게 할까 하다가 영점을 움직인다는 얘기를 듣고 생각하니 수월하게 구할 수 있었다.
