A. Pizza, Pizza, Pizza!!! $\!$
$n$이 주어지면 피자를 칼로 균등하게 $(n + 1)$조각 시키려한다. 칼은 피자 도우부분에서 시작해서 도우까지 또는, 중간에 멈출 수도 있고, 중간에서 시작해서 중간에서 멈출수도 있다. 단, 직선으로만 잘라야한다. 칼질횟수를 구하여라.
정말 간단하다.
$(n + 1)$이 짝수면 그냥 중간을 쑥 쑥 지나가게 잘라버리면된다. 한번 중앙을 가로지르는 칼질을 반복하면 한번 칼질에 같은 크기의 피자가 2개씩 나오기 때문이다.
$(n + 1)$이 홀수면 중앙을 가로지르는 칼질로는 피자를 균등하게 자를수가 없다. 그냥 중앙에서 시작해서 $(n + 1)$번 잘라야 모두 같은 크기로 자를 수 있다.
너무 간단해서 2줄코딩했는데 $n$이 0일때 예외가 생겨버린다. $n$이 0이면 $(n + 1)$은 1이므로 혼자서 다 먹을 수 있기 때문에 칼질을 할 필요가 없다. 돼지..
$n$과 3개의 문자열이 주어진다. 총 $n$번 각 문자열의 문자 하나를 임의로 바꿀 수 있는데, $n$번 모두 바꾸었을 때 같은 문자의 개수의 최대값을 세어야한다.
먼저, 각 문자열의 각 문자의 개수를 세어주고, 개수가 가장 많은 문자로 다른 문자들을 바꾸어주면 된다. 문제는 모든 문자를 하나로 통일시켰는데 문자를 바꿀 수 있는 횟수가 남아있을 경우이다. 모든 문자가 통일 되기 직전 즉, 한 문자만 다른 경우로 되돌아가보자. 그 한 문자를 통일시킬 문자와 관계없는 아무 문자로 막 바꾸다가 마지막 1번 남았을 때 문자를 통일시키면 무조건 문자열 길이만큼 즉, 최대 크기만큼 만들 수 있다.
대부분의 사람들이(심지어 E번을 풀 정도로 대단한 사람들도) 문자를 바꿀 수 있는 횟수가 남았을 때 (문자열 길이 or 문자열 길이 - 1)를 최대 길이로 채택했다. 남은 횟수가 2의 배수면 문자열 길이를, 아니면 문자열길이 - 1을. 풀이를 보고 보면 정말 간단한 문제가 되지만 실제 대회에서 1000명 이상이 썰린걸 보면 정말 무서운 문제다.
트리와 $x, y$가 주어진다. 한 노드 $u$에서 다른 노드 $v$로 이동할 때의 경로를 $(u, v)$로 나타낸다. $(u, v)$사이의 경로에서 노드 $x$를 방문한 후 $y$를 방문할 경우 죽는다. 죽지않고 갈 수 있는 모든 경로쌍의 개수를 구하는 문제다.
일단 총 경로의 개수는 $n(n - 1)$개다. 그 중에서 죽는 경로의 개수를 세면 되는데, $x$에서 $y$로의 경로에서 가장 첫 번째 노드(즉, $x$의 자식)의 subtree외에 $x$의 자식의 subtree에서 $y$의 subtree로 가는 경로만 죽는 경로이다. 즉, $(subtree[x] + 1 - (subtree[x to y의 첫 노드] + 1)) * (subtree[y] + 1)$가 죽는 경로의 총 개수이다. 여기서 각 subtree배열에 1을 더해준 이유는 subtree뿐만 아니라 $x$자신도 포함해주어야 하므로 1을 더해주어야한다.
subtree와 $x to y$경로는 dfs한번으로 결정가능하다.
아이디어를 생각해내기까지는 얼마 시간이 안 걸렸지만, 이 풀이 맞는지 아닌지 검증하는데 조금 오래걸렸다. 그리고 root를 $x$로 고정시키지않고 그냥 root를 1로 잡고 dfs를 돌린다고 생각해버려서 $x$가 $y$의 조상일 경우, 반대일 경우, 둘다 아닐경우 총 3경우로 나누어서 계산하려고 하는 바람에 10분정도 잡아먹었다.
