leo020630의 블로그

A. AquaMoon and Strange Sort (00:06, +) 방향을 유지하며 이동하려면 짝수 칸만큼 이동해야 한다. 따라서 본인이 있던 칸과의 홀짝성은 변하지 않고, 정렬 후에도 홀짝성이 변하지 않으면 가능하다.

A. Potion-making (00:02, +) \(\frac{100}{\gcd(100,n)\) 이 답이다. B. Permutation Sort (00:19, +4) 양쪽 끝 수를 보며 최적의 경우를 생각해주면 된다. D. Armchairs (01:05, +1) \(DP[i][j]\)를 \(i\)번째까지의 의자 모두를 앞에서 \(j\)번째까지로 옮기는 최소 비용으로 정의하자. 이는 \(i\)번째 칸이 1이고 \(j\)번째 칸이 0인 경우에만 갱신 가능한데, \(dp[i][j-1]\)과 \(dp[i-1][j-1]+|i-j|\)중 작은 것을 선택해주면 된다.

A. Fair Playoff (00:02, +) 1위 실력과 2위 실력을 가진 사람이 서로 다른 그룹에 속해있는지 판별해주면 된다. B. Array Reodering (00:07, +) 짝수->홀수대로 정렬하되, 내림차순으로 정렬하는 것이 최적이다. C. Unstable String (00:20, +) 현재 위치에서 만들 수 있는 가장 긴 Stable String의 길이들을 저장하며 가면 된다. D. Playoff Tournament (00:42, +) 각 업데이트에서 바뀌는 결과가 최대 \( O(logN) \) 개이므로, Segment Tree등의 자료구조를 이용해서 업데이트하면 \(O(NlogN)\)에 문제를 해결할 수 있다.

A. Exciting Bets (00:05, +) \(a

A. Odd Set (00:02, +) 두 정수를 더해서 홀수를 만드는 방법은 홀수+짝수밖에 존재하지 않는다. 따라서, 각 그룹마다 홀수의 개수와 짝수의 개수가 같다면 Yes이다. B. Plus and Multiply (00:14, +) 1에서 a를 곱하거나 b를 더해 n을 만들 수 있는지 묻는 문제이다. n을 만들 때에 a를 k번 곱했다고 가정하자. 그렇다면 \( n=a^k+xb \) 꼴로 표현됨을 알 수 있다. 따라서 모든 \( a^k 10^{16} \) 이므로 \(O(40T)\) 정도에 문제를 해결할 수 있다.