ps대회에 참가하는데 나의 ps스킬이 수치상으로 $k$이다. $k$보다 어려운 난이도의 문제는 풀지 못 한다. 문제를 효율적으로 풀기위해 왼쪽부터 $k$보다 작거나 같은 문제들을 풀다가 $k$보다 높은 난이도의 문제를 만나면 오른쪽부터 $k$보다 작거나 같은 문제들을 쭉 푼다. 다시 $k$보다 높은 난이도의 문제를 만나면 문제 풀기를 멈춘다. 총 푸는 문제 수를 구하는 문제다.
for문 1개와 bool형 배열 하나면 해결된다.
길이 $n$의 문자열 $s$를 암호화하는 방법은 $n$의 약수를 모두 구하고, 약수를 오름차순으로 정렬한 뒤 각 약수마다 $s$의 부분문자열 $s[1, d]$를 뒤집는다. 암호화된 문자열이 주어지면 문자열을 리버싱해서 구하라는 문제다.
$n$의 약수를 모두 구한 후 약수를 내림차순으로 정렬한 뒤 각 약수마다 부분문자열을 뒤집어주면된다.
길이 $n$의 문자열 $s$의 문자를 $k$개 삭제하려고 하는데, 제일 왼쪽에 있는 a부터 삭제하고, a가 모두 삭제되면 제일 왼쪽에 있는 b를 삭제하고, b가 모두 삭제되면 ... 제일 왼쪽에 있는 z를 삭제하고 멈추는 방식으로 삭제하려고한다. $k$개를 모두 삭제한 뒤 문자열을 출력하는 문제다.
각 문자가 나오는 index를 vector에 저장해놓은 후 vector가 빌 때 까지 삭제해주는 작업을 $k$번 해주면 된다.
$n$개의 정수가 주어지고, $n$의 약수 $m$이 주어진다. 각 정수들을 $m$으로 나눈 나머지를 모두 계산하여 각 나머지의 값이 $n / m$개 나오게 하려고 한다. 한 번의 연산에 정수 하나에 1을 더 할 수 있을 때 최소 연산 횟수와 연산 후 배열을 구하는 문제다.
먼저, 각 정수를 $m$으로 나눈 나머지를 모두 구해놓고, 각 나머지값이 나오는 횟수를 세아려놓자. 만약 딱 $n / m$개 나온다면 이 값은 건드릴 필요가 없다. 왜냐면 이 값을 건드려 다른 값을 만든다 해도, 다른 값이 다시 이 값으로 만들어져야하기 때문에 불필요한 연산이 생기거나, 이 값으로 만들 다른 값을 그냥 이 값으로 만들 값으로 만들어버리면 되기때문이다. 따라서 $n / m$개의 보다 많이 나온 값을 $n / m$개 보다 작게 나온 값으로 만들어주어야한다.
$n / m$개 보다 작게 나온 값을 많이 나온 값들 중 하나로 채워주어야하는데, 어떤 값을 선택하면 최선일까? 먼저, 많이 나온 값들과 작게 나온 값들을 오름차순으로 정렬해보자. 작게 나온 값들 중 가장 작은 값부터 채울 녀석을 선택하는데, 그 값은 둘 중 하나다. 많이 나온 값들 중 안 쓴 값들 중 가장 작은 값 또는, 안 쓴 값들 중 가장 큰 값. 안 쓴 값들 중 가장 작은 값이 작게 나온 값들에서 채울 값보다 크면 가장 큰 값을 선택해야하고, 아니면 가장 작은 값을 선택해야한다.
왜 그렇냐면.. 그렇기 때문이다. 이런 greedy한 방법은 정말 설명하기도 이해하기도 어렵다. 그냥 예외일것만 같은 tc를 막 만들어도 너무 딱 딱 잘 들어맞아서 이 방법이 맞구나 하고 진행하는 경우가 대부분이라서..
2번이나 틀렸는데 둘 다 너무 greedy하게 생각한나머지 작게 나온 값들과 크게 나온 값들을 정렬하고 index가 같은 녀석들 끼리 매칭하는 식으로 해서 틀렸다. tc 하나 만들어서 해보니 아닌걸 알아채고 위에 설명한 방식으로 하니 바로 맞았다. 처음엔 확 마 mcmf로 풀어? 하는 생각까지 들었다. 역시 greedy는 힘들어
E. Reachability from the Capital
방향 그래프와 수도의 vertex번호가 주어진다. 도로를 최소한으로 놓아서 수도에서 모든 도시까지 도달할 수 있도록 만드는 문제다.
생각해보면 방향 그래프는 cycle인 경우 빼고는 무조건 indegree가 0인 시작점이 존재한다. 이 시작점에 수도에서 도로를 놓아주면 최소의 도로를 놓아서 모든 도로에 도달할 수 있을것이다. 그런데 cycle은 어떻게 처리할까? scc다. scc로 cycle을 모두 묶어주고, scc로 묶인 vertex까지 쳐서 indegree가 0인 vertex의 개수를 세어주면 된다. 근데 수도를 포함하는 scc도 indegree가 0인 경우가 있을 수도 있으므로 수도를 포함하는 scc의 indegree가 0인 경우는 빼주자.
한 번 틀렸는데, 처음엔 그냥 어? dfs그냥 다 돌리면 되는거 아냐? 왜이리 쉽지? 생각했는데 방향그래프이기 때문에 그게 아니였다..
$n$명에게 총 $n * k$개의 카드의 번호가 주어진다. 카드의 번호는 중복될 수도 있다. $n$명은 각각 자신이 좋아하는 카드의 번호가 있고, 이 번호 또한 중복될 수 있다. $n$명에게 각각 $k$개의 카드를 배분하려한다. 각 사람이 좋아하는 카드를 $i$개 받게 되면 $h_i$만큼 행복해한다. 모든 사람의 행복도 합의 최대값을 구하는 문제다.
정말 간단한 dp다. 먼저, 좋아하는 카드별로 사람 명 수를 세어놓자. 그러면 문제는 $a$카드를 좋아하는 사람 $b$명에게 그 카드 $c$개를 적절히 나누어 주어 행복로를 최대화 시키는 방법을 찾는 문제로 바뀐다. 왜 그렇냐면 모든 사람에게 각각 딱 $k$개의 카드가 배분되므로 좋아하는 카드는 무조건 좋아하는 사람에게 배분되는게 최대이득이기때문이다.
$dp[i][j]$를 $i$명에게 $j$개의 카드를 배분하여 얻는 행복도의 최대값이라 정의하면 $dp[i][j] = MAX(dp[i - 1][j - t] + h_t)$가 된다. 각 좋아하는 카드에 대해서 getDp($b$, min($c$, $b$ * k))함수를 호출해주면 된다.
조금만 생각하면 바로 풀 수 있는 문젠데 시간이 부족해서 생각할 시간조차 없었다. 그리고 끝나서고나서 푸는데 계속 시간초과가나서 왜 그런가 따져보니 점화식의 $t$가 $[0, k]$의 범위이어야하는데 $[0, n * k]$의 범위로 해버렸다. 그러니 O($n^2*k^2$)의 시간복잡도가 O($n^3*k^2$)이 되버려 시간초과가 뜬것이다. 문제가 간단해서 빠르게 코딩하다보니 생각을 안 해버렸다.
