배열이 주어지는데 하나의 연산을 할 수있다. 배열에 0이 아닌 모든 값에 똑같은 숫자를 더하거나 뺄 수 있다. 그렇게 모든 배열이 0이 되면 멈추는데, 최소연산 횟수를 구하는 문제다.
한번에 연산마다 하나의 숫자를 0으로 바꿀 수 있다. 배열이 똑같은 숫자를 가지면 똑같은 숫자도 모두 0이 되므로 distinct한 숫자의 개수를 세어주면 된다. 숫자가 작으니 bool형 배열로 깔끔하게 처리가능하고, 느리지만 set으로 해도 가능하다.
어떤 수 $a, b$의 $gcd$가 $x$이고, $lcm$이 $y$이다. $a, b$의 범위가 $[l, r]$이다. $l, r, x, y$가 주어졌을 때 가능한 $a, b$쌍의 개수를 구하는 문제다. $(a, b)$와 $(b, a)$는 서로 다른 쌍으로 취급하며, $a == b$이면 같은 쌍으로 취급한다.
$lcm = gcd * n * m$이다(n과 m은 서로소). $lcm / gcd = n * m$이고 $n, m$은 서로소 이므로 $lcm / gcd$의 약수 $n$을 구해서 $a( = n * x )$와 $b( = y / (x * n) * x)$이 $[l, r]$범위 내 인지, $n, lcm / gcd / n$이 서로소인지 판단해주고 두 조건을 만족하면 $ans += 2$를 해주면 된다. 물론 $n == lcm / gcd / n$이면 $ans += 1$이다.
단, 한가지 더 체크해주어야할 것이 있는데, 정말로 $y == x * n * m$인지 체크해주어야한다. $y / x$의 약수를 구해서 체크해준 것이기 때문에 $y == x * n * m$인지 체크해주어야 원하는 답을 얻을 수 있다.
2번이나 틀렸는데, 한번은 $a == b$이면 1을 더해준다는걸 처리 안 해주었고, 한번은 $y == x * n * m$인지 체크를 안 해주었다. $a == b$은 실수라고 쳐도 $y == x * n * m$을 체크해줘야하는게 조금 까다로웠던 편인것 같다.
1년에 $k + 1$달이 있는 마법의 세계에 마법의 옷장에 옷이 있는데, 이 옷장에 옷은 매달 마지막 날마다 안에 있는 옷의 개수가 2배로 늘어난다. 그리고 2배로 늘어난 뒤에 50% 확률로 옷이 1개 없어진다. 단, 매년 마지막 달에는 옷이 없어지지않고 2배로 늘어나기만 한다. 처음 옷장에 있는 옷의 개수 $n$과 $k$가 주어질 때, 1년 뒤 옷의 개수의 기대값을 구하는 문제다.
첫 달에 $n$이 50%확률로 각각 $2n$과 $2n - 1$이 되고, 2월달에 각각 25%확률로 $4n, 4n - 1, 4n -2, 4n - 3$이 된다. 또 3월달에 12.5%확률로 $[8n, 8n - 7]$이 된다. 모든 경우가 확률이 같으므로 기대값을 구할 때 확률은 고려대상이 되지 않으며, $k$달에는 $[n * 2^k, n * 2^k - 2 ^ k - 1]$의 경우가 모두 나옴을 알 수 있다. 그럼 이제 $k$번째 달의 평균은 $(n * 2 ^ k + (n * 2 ^ k - 2 ^ k - 1)) / 2$임을 알 수 있다(모든 수가 1씩 차이나므로 모든 수를 합할 필요 없이 가장 큰 값과 가장 작은값의 합의 절반이 평균이다).
3번째 예제 예시
우리가 구하는 것은 $k + 1$번째 달의 평균이고, $k$번째 달에서 $k + 1$번째 달은 2배로 늘어나기만 하므로 $k + 1$번째 달의 평균은 $k$번째 달의 평균의 2배가 될것이므로 $n * 2 ^ k + (n * 2 ^ k - 2 ^ k - 1)$이 될것이다.
깔끔하게 풀었지만 안타깝게도 한 번 틀렸는데, 한 가지 예외가 있었다. $x$가 0인 경우도 있다는 것... 뺄셈의 MOD연산때문에 $x$가 0인경우에 0을 출력하지않고 다른 값을 출력해버린다.
배열이 주어지고, $k$가 주어진다. 부분배열의 원소들의 곱 $p$와 합 $s$에 대해 $p / s == k$인 부분 배열의 개수를 구하는 문제다.
$s * k$는 최대 $2 * 10^5 * 10^5 * 10^8 == 2 * 10^18 < LLONG_MAX$이다. 따라서 $p$가 $2 * 10^18$을 넘어가면 더이상 확인하지 않도록해주면 모든 범위에 대해서 O($n^2$)으로 풀 수 있다.
이제 이걸 O($60n$)으로 줄여보자.
한 가지 자명한 점은 $a_i$가 1이면 분모만 1씩 늘어나며, 1이 아닌 경우에는 분모도 커지고 분자도 커지지만 분수의 값이 무조건 커지거나 같아진다. 따라서, $a_i$가 1이면 무시하고 1이 아닌 경우에 분모에 더해주고 분자에 곱해주다가 $k$보다 커지거나 앞서 말했듯이 $p$가 $s * k$의 범위를 벗어나면 break해주고 범위의 left를 1 늘려주고 다시 체크해주면 될것이다.
그리고 $a_i$가 1인 경우에는 분모가 1씩 커져 $p / s == k$가 될 수 있으므로 체크해주어야 하는데, $p$와 $s$를 각각 계산해주다가, $s <= k && s + (연속적인 1) >= k$이면 분모가 1씩 거지면서 $p / s == k$가 되는 경우이므로 처리해주면 된다.
이게 어떻게 O($60n$)이 되냐면 1이 나타나면 범위의 right를 ++해주는 것이 아니라 1이 나타나면 1이 아닌 다음 원소를 가르켜주는 배열을 미리 전처리 해두어서 1이 아닌 값만 $p$를 계산해주도록 해보자. 그러면 $a_i$가 2이상인 값들만 $p$에 곱해질텐데, $2 * 10^18 < 2 ^ 61$이기 때문에 최대 60번만 계산된다. 즉, 최대 60번만 $p$가 $a_i$에 곱해질 수 있다.
1이 아닌 다음 원소로 점프해주고, 그 점프한 index만큼 1이 있다는 뜻이므로 앞서 말했듯이 1로 인해 $k$를 만들 수 있는지 체크해주면 된다.
$a_i$가 1인 경우에는 분모만 증가하고 나머지 경우에는 분자도 증가하면서 분수의 값이 증가하게 되니 이걸 이용해야겠다 생각은 했다. 그런데 그렇게 해도 O($n^2$)인 것 같아서 복잡도를 줄이려고 생각해봤는데 그냥 구현했으면 60번 내로 되면서 커팅되서 됬을텐데...
조금 아쉽긴하지만 어쨋든 몰랐던거니 공부도 했고 tutorial 코드도 상당히 깔끔하고 좋아서 얻을걸 많이 얻은 문제였다.
