https://codeforces.com/contest/1929
총평: 지금까지 봤던 Div2 중 가장 쉬웠네요. 그런데 삽질해서 올솔브는 늦었습니다 ㅠ
A: beauty의 합은 항상 a_n - a_1이기 때문에 a_n을 가장 큰거, a_1을 가장 작은거로 두면 됩니다.
가장 쉬운 방법은 a[1,n]을 정렬한다음 a_n - a_1을 출력하는것
B: (1,1),(1,2)...,(1,n-1),(n,1),(n,2)...,(n,n-1)을 놓으면 놓을때마다 +2점을 얻습니다
이것을 전부 다 채우면 4n-4개까지는 커버가 되는데, 여기서 (1,n)을 놓으면 +1, (n,n)을 넣으면 +1로 총 4n-2까지 가능합니다.
그래서 k==4n-2면 답은 2n, k==4n-3이면 답은 2n-1, 그 외에는 ceil(k/2)가 답이됩니다.
C: 꽤 복잡한 애드혹이네요. 카지노에서 항상 운이 더럽게 없어서 최악의 경우 성공이 나온다고 가정을 해야합니다.
그래서 처음에 1원씩 내다가, 어느순간 1원을 냈을때 이것이 성공하더라도 지금까지 잃은 돈까지 포함했을때 손해가 되면 절대 안됩니다
그래서 1원씩 내다가 어느 순간 2원, 또 어느순간 3원... 이런식으로 지불해야합니다.
좀 더 엄밀하게 말하면 처음 (k-1)번은 1원, 그 후 약 k/2번은 2원, 그 후 약 k/3번은 3원... 이런식으로 지불해야 합니다.
한 주기인 x까지 이런식으로 전부 지불했다고 했을때, 총 지불한 돈이 a이하면 YES, 아니면 NO입니다.
D: 단순 트리DP입니다.
v를 root로 가지는 subtree를 볼때, v위치가 dangerous하지 않음 / v만 dangerous함 / v와 v의 자식중 1개가 dangerous함 총 3가지로 나누어서 생각해보면 됩니다.
E: 문제 잘못읽어서 거하게 삽질했네요.
각 edge마다 k개의 path중 어떤것을 커버하는지 상태를 표현해보면, k크기의 bit로 표현할 수 있습니다. 즉, 0이상 2^k 미만의 숫자로 표현할 수 있습니다.
이러한 bit들을 몇개 모아 OR연산 하여서 2^k-1을 만들 수 있는지, 최소의 bit를 구하면 되는 문제입니다.
출제자 정해는 트리를 압축해서(Auxililary Tree를 만들어서) 최대 O(k)개의 edge들만 보고 DP를 돌려, O(2^k k)로 푸는것으로 예상됩니다.
하지만 저는 이걸 생각 못해서 OR convolution이라는 어려운 방법을 사용했네요(...)
SOS DP의 간단한 응용이긴 한데, SOS DP 자체가 백준 기준 P1~D5정도의 알고리즘이라 너무 overkill을 한것 같군요
OR convoluton을 1개씩 해가며 2^k-1 bit가 언제 값을 가지는지 보면 되고, 당연히 convolution을 k번 이상 할 필요가 없기 때문에
시간복잡도는 O(2^k k^2)입니다. k<=20이라 아슬아슬하긴 한데 아마 통과될거에요
F: 이렇게 쉬운 문제가 F에 있으면 안됩니다 -_-
그냥 트리를 inorder traversal해가며 방문한 vertex의 value들을 기록해 놓고,
-1인 값들을 적절하게 채우면 됩니다. 채우는 방법은 중복조합을 이용하면 됩니다.
문제는 nCr을 계산할때 n이 10^9이상이 될 수 있어서 O(r)시간에 계산해야한다는 것입니다.
그래서 nCr = n-1Cr-1 + n-1Cr 공식을 쓰지 않고, nCr = n-1Cr-1 * (n/r) 공식을 쓰면 됩니다.
진짜 이게 끝이에요.
질문은 환영입니다