leo020630의 블로그

A. There Are Two Types Of Burgers (00:04, +) 더 비싼 버거를 최대한 많이 만들어준 후 남은 빵으로 다른 버거를 만들어주는 것이 최적이다. B. Square Filling (00:08, +) 그리디하게 칠해준 후 두 배열이 같은지 확인하면 된다. C. Gas Pipeline (00:31, +) 길이가 2이상인 0을 만날때 마다 비용이 더 적은 경로로 이어주면 된다. D. Number Of Permutations (00:50, +) 전체 경우의 수인 \(N!\)에서 첫 배열로 정렬할 수 있는 경우와 둘째 배열로 정렬할 수 있는 경우를 빼준 후, 둘 모두로 정렬 가능한 경우를 더해주면 된다. 각 경우는 연속된 같은 수의 갯수만큼 팩토리얼을 해주면 구할 수 있다. E. XOR..

A. Simply Strange Sort (00:07, +) Div2 A답지 않은 구현 문제이다. 구현이 어렵진 않기 때문에 문제에서 하라는 것을 해주면 된다. B. Charmed by the Game (00:20, +) \(|a-b|/2\)의 값을 이용해 잘 탐색해주면 된다. 나는 머리가 안돌아가서 무지성으로 구현했다.. C. Deep Down Below (00:32,+) 각 동굴마다 \(A_i-i\)의 최대값을 저장해 준 후, 이를 기준으로 정렬한 후 파라메트릭 서치를 진행하면 된다. 이분탐색을 하지 않고도 답을 구할 수 있다 한다. D1. Up the Strip (01:06, +2) \(floor(N/i)\)의 값이 \(O(sqrt(N)\)개라는 것을 이용하면 \(O(Nsqrt(n))\)에 문제를 ..

A. Creating a Character (00:06, +1) \(max(0,min(exp+1,(str-int+exp+1)/2)\)가 답이다. B. Zmei Gorynich (00:14, +) 가장 효율이 좋은 무기를 사용하다 가장 공격력이 높은 무기로 마무리하면 된다. C. The Number Of Good Substrings (00:39, +) 관찰을 해보면, leading zero의 개수에 따라 해당되는 수가 최대 2개임을 알 수 있다. 따라서, 연속되는 0의 개수를 체크하다 1을 만났을때 가능한 수를 모두 체크하면 \(O(N)\)에 문제를 해결할 수 있다.

A. Dial Up (00:18, +1) *442 제자리에서 계속 더하다 처음 다른 값이 나오면 가장 가까운 곳으로 이동하고, 이후에는 나오는 값에 따라 1이나 2를 더해주면 된다. 불가능한 경우 처리는 쉬우니 생략하도록 하겠다. B. Squares (00:54, +) *1273 \(1\)부터 \(sqrt(N)\)까지는 모든 경우가 되므로 다 더해준다. 그러면 각 \(x\)당 가능한 \(y\)의 개수가 \(O(sqrt(N))\)개가 된다. 따라서 각 경우에 대해 구간의 길이를 곱해 더해주면 된다. C. LIS to Original Sequence (01:42, +4) *1896 다음과 같은 과정을 따른다. LIS의 원소를 \(A_1..A_k\)라 했을때 (1) \(i

A~B는 따로 적지 않겠다. C. One More aab aba baa (00:05, +) *178 next_permutation() 함수를 이용하면 쉽게 구현할 수 있다. D. Coprime 2 (00:37, +3) *736 에라토스테네스의 체의 메커니즘을 이용한다. 모든 \(A_i\)에 대해 소인수를 구해준 후, 구한 소인수들로 에라토스테네스의 체 배열을 채워주면 된다. \(O(Nsqrt(N)\)에 문제를 해결할 수 있다. E. Chain Contestant (00:84, +1) *1413 비트마스크 DP이다. \(DP[i][j][k]\)를 \(i\)번째까지의 원소를 이용해 집합 \(j\)에 해당하는 색을 사용해 끝 색을 \(k\)로 하는 경우의 수로 정의하면 DP 갱신을 \(O(10 2^{10})\..

A. 2048 Game (00:03, +) 2048 이하인 수들을 모두 더했을 때 2048 이상이면 가능하다. B. Knights (00:05, +) 체크무늬로 칠한 배열을 출력하면 나이트가 갈 수 있는 칸의 색이 항상 달라지므로 최적이다. C. Perfect Team (00:18, +) \(min(c,m,(c+m+x)/3\)이 정답이다. D. Make The Fence Great Again (01:23, +3) 한 울타리에 대해 최대 2번까지만 높여주는 것이 최적임을 알 수 있다. 따라서 \(DP[i][j]\)를 \(i\)번째 펜스를 \(j\)만큼 올려줬을 때의 최소 비용으로 정의하면 \(O(N)\)에 문제를 해결할 수 있다.

A. Prime Subtraction (00:01, +) \(A-B=1\)이면 NO이다. B. Kill 'Em All (00:07, +) 좌표압축+정렬한 후 가장 먼 적한테 폭탄을 쏘는 것을 반복하면 된다. C. Standard Free2play (00:17, +) 디스크립션을 이해하면 구현은 어렵지 않다. 규칙을 잘 지키며 낙하하면 된다. C까지 풀었을 때 6등인가 했던거로 기억하는데 그 뒤로 하나도 못풀었다..

A. Mocha and Math (00:07, +) 모든 수를 AND연산해 출력하면 된다. B. Mocha and Red and Blue (00:17, +) 문제에서 하라는 대로 나이브하게 색칠하면 된다. \(N\)이 작아 여러가지로 구현할 수 있다. C. Mocha and Hiking (00:25, +1) \(A_i = 0, A_(i+1) = 1\)인 구간이 있거나, \(A_1 = 1\)이거나, \(A_n = 0\)이면 경로를 찾을 수 있다. 어떤 경우에서든 셋 중 하나를 만족하기 때문에 탐색에만 집중하면 된다. D. Mocha and Diana (00:45, +) D1은 \(N^2\)개의 정점 쌍에 대해 더해도 되는지 판단한 후 Union-Find를 이용해 그리디하게 더해주면 시간 안에 문제를 해결할..

A. Ezzat and Two Subsequences (00:02, +) 가장 큰 원소만 포함하는 그룹과 아닌 그룹으로 나누어주면 된다. B. Moamen and k-subarrays (00:07, +) pair등을 이용해 등장 순서를 같이 저장해준 후 정렬한 배열에서와 원래 배열에서 모두 인접한 구간들의 개수를 세주면 된다. C. Moamen and XOR (00:43, +2) \( {n \choose 0}+{n \choose 2}+{n \choose 4}..\) 를 구해준 후 포함배제 원리를 이용해 계산해주면 된다. 위의 식의 값이 \(2^{n-1}\)이라는 것을 이용하면 쉽게 코딩할 수 있지만, 나는 빨리 풀겠다는 생각에 이항계수를 \(O(1)\)에 구하는 코드를 긁어와서 풀었다.

A~B는 따로 쓰지 않겠다. C. Reorder Cards (00:07, +) *481 2차원으로 들어오는 점들을 좌표압축 해주면 된다. D. Takahashi Tour (00:13, +) *710 기본 DFS 문제다.. 이게 왜 D인지도 모르겠다. E. Stronger Takahashi (00:55, +) *1423 https://www.acmicpc.net/problem/15944의 하위호환이다. 펀치 횟수를 1 증가시키며 BFS를 돌려주면 된다.