$a $/=$ b$와 $b $+=$ 1$의 연산 2가지를 해서 $a$를 0으로 만들어야 할 때, 최소 연산 수를 구하는 문제이다.
간단하게, bfs돌리면 $log_2(a)$만에 풀린다.
8분이나 걸린 이유는 $b$가 1일때 때문에 살짝 멈칫했고, visited check 때문에 set을 쓴다고 좀 오래 걸렸는데,
사실 visited check할 필요도 없이 그냥 $log_2(a)$만에 풀린다.
배열 $b_i$가 $a_i$와 $k$-닮음 이려면 $a_i, b_i$
모두 단조 증가해야하고,
같은 길이를 가지며,
원소가 $1$~$k$여야 하며
모두 distinct하며
정확히 한 원소만 달라야 한다.
증가하는 배열 $a_i$와 범위에 대한 쿼리가 주어질 때, $a_i$의 그 범위의 수열과 $k$-닮음인 $b_i$배열을 모두 구하는 문제다.
오랜만에 하는 코포라서 그런가 영어 해석이 빠르게 안 되서 예제를 손으로 많이 그려본다고 오래걸렸다.
각 $b_i$의 원소가 될 수 있는 가지수를 모두 더하면 답이 된다. 각 원소가 될 수 있는 경우의 수는 문제 조건으로 인해 간단하게 구해지고, 그 원소들을 모두 더 하면 되니.. 이렇게 하면 각 쿼리에 대해서 $n$만큼 걸려서 O($n*q$)가 걸린다.
그런데, 이 각 원소의 경우의 수를 다 더할 때, 계산 하지말고 식으로 전개해서 더해보면 O($n + q$)에 풀리는 해답이 보인다.
설명이 귀찮으니 최종 식을 적어보면
$ans = (k + 1) + a[r] - a[l] - (r - l + 1) * 2$
이다.
$a / b == a $%$ b$인 모든 쌍의 개수를 구하는 문제다.
충분히 많이 풀어 봤을 법 한 문제라 기억속에서 끄집어 낸다고 뻘짓을 많이 해서 좀 오래걸렸다.
공식 solution과 좀 많이 다른 풀이를 했는데, 아래와 같다.
$b = 2 : a = 3$
$b = 3 : a = 4, 8$
$b = 4 : a = 5, 10, 15$
$b = 5 : a = 6, 12, 18, 24$
$b = 6 : a = 7, 14, 21, 28, 35$
$(b,a)$쌍을 구해보니 이런식으로 나왔는데, 정리를 해보면
$b = n$ 일때 $a = (b + 1), 2(b + 1) ..... (b - 1)(b + 1)$
이다.
여기까지 해놓고 어떻게 이걸 이용할지 많은 뻘짓들을 해보았는데, O($x$)나 O($y$) 가 걸리면 시간초과가 걸리기 때문에 이걸 $log$로 만들 생각을 하고, ($x, y$)를 (12, 11)을 입력으로 받았을 때를 생각해보았다.
$b$가 11부터 6일때 까지는 전부 $a$는 1개 밖에 없고, $5$일때 부터 비로소 2개씩 될 수 있었다.
이런 식으로 생각을 전개 해 나가니, $b / div - 1 - (div + 2)$이라는 식이 나왔고, 여기서 $div$는 1부터 쭉 증가한다.
만약 이 식이 0이 되거나 음수가 되면 더 이상 진행하지 않고, 이 식이 양수라면 이 값을 모두 더 한게 $a,b$쌍의 총 개수다.
어떻게 저런식이 나왓냐면, $a = i * (b + 1)$에서, $x$를 $i$로 나누고 1을 빼서 $a$를 구한다는 생각을 했고, 위에 $(b,a)$쌍 table에서 $a$의 column의 수를 각각 구해나가자 하는 생각을 하다보니 저런 식이 나왔다.
시간복잡도가 아리까리했는데, 저 식의 상수들을 정리해서 언제 끝나는 지를 보면 $b/ div - div \leq 0$일때 끝이 난다.
즉, $div^2 < b$일때 까지 돌아가기 때문에 O($\sqrt{b}$)이다.
D. Multiples and Power Differences
어디까지 생각을 했냐면, 이웃한 두 수의 관계식이 $|ax - by| = k^4$인 점에 착안해서 gcd로 갖고 노는 거구나 까지는 생각을 했는데, 거기까지 였다. 약 30분간 쳐다봤음에도 풀이가 나오지않아 $F$번 문제로 넘어갔는데, 그냥 계속 봤으면 풀었을지도 모르겠다..
solution은 다음과 같다.
$a_{i,j}$의 값은 16이하의 자연수로, 매우 작다. 1부터 16까지의 모든 수의 lcm을 구하면 720720이다.
즉, 모든 수를 720720으로 만들어 준 뒤에(여전히 각 원소의 배수라는 점은 성립한다.),
각 원소에 $a_{i,j}^4$을 더해주면 모든 조건을 만족한다.(각 원소의 배수여야하며, 각 원소의 차는 $k^4$의 형태이어야 한다.)
여기서 $a_{i,j}^4$을 더해줄 때, 모든 원소에 더해주는 것이 아닌, 바둑판 모양으로 건너뛰어가며 더해주어야 조건에 부합해진다.
전체적으로 너무 arithmetic한 문제들만 모여있어서 조금 아쉬웠다.
알고리즘적인 사고보다는 수학적인 사고가 더 우선되어있는 round였다.
