leo020630의 블로그

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를 돌려주면 된다.

A. New Year Garland (00:02, +) 가장 큰 수가 나머지 두 수+1보다 크다면 NO이다. B. Verse For Santa (00:18, +1) 누적합 - 최댓값을 관리하며 가장 많은 값을 선택할 수 있는 상황을 골라주면 된다. C. Stack of Presents (00:28, +1) 한번 꺼내졌던 값은 다음 시도에 무조건 1의 비용으로 꺼낼 수 있다. 이가 가능한 값들을 저장해주면 된다. D. Santa's Bot (01:17, +3) 모듈러 인버스를 구할 줄 안다면, 단순한 확률론 문제가 된다. 분수 덧셈은 그냥 모듈러 값들을 더해도 성립한다.

A. Erasing Zeroes (00:03, +) 문자열 가장자리의 0들을 모두 지워준 후 해당 문자열의 0의 갯수를 센다. B. National Project (00:54, +4) 수식을 적당히 세워주면 되지만, 난 굉장히 더럽게 세워 알아보기도 힘들고 실제로도 많이 틀렸다. C. Perfect Keyboard (00:40, +) 나이브하게 구현해주면 된다. Deque을 이용하면 구현을 비교적 간단하게 할 수 있다. D. Fill The Bag (-2) 문제를 잘못 읽어 맞왜틀했다. 끝나고 한줄 고쳐서 맞았다.. 풀이 자체는 쉽게 떠올릴 수 있는 그리디한 발상이다. 버츄얼을 돈지도 어느덧 한달인데 레이팅이건 퍼포먼스건 어째 점점 내려만 가는 것 같다..

A. Two Regular Polygons (00:01, +) \(m\)으로 \(n\)이 나누어떨어지면 YES다. B. Bogosort (00:04, +) 내림차순으로 정렬하면 해당 경우가 발생하지 않는다. C. Adding Powers (00:13, +1) 모든 수들을 \(k\)진수로 나타내며 한 비트당 최대 1개의 1이 나타나는지 세어주면 된다. D. Count the Arrays (01:18, +) 생 조합 문제. 경우를 잘 정리하면 \({m \choose n-1}\times{2^{n-3}}\times(n-2)\) 임을 알 수 있다.

A. Sum of Odd Integers (00:01, +) 홀짝성을 판단한 후, \(n\)이 만들 수 있는 최소 보다 큰지 확인해주면 된다. B. Princesses and Princes (00:11, +) 매칭되지 않은 쌍이 하나라도 있다면, 매칭되지 않은 사람 중 가장 뒤의 공주와 가장 앞의 왕자를 이어주는 것이 최적이다. C. Game with Chips (00:23, +) 제한으로 주어진 \(2NM\)은 상당히 큰 수다. 따라서, 모든 칩을 한쪽 모서리로 모으고 완전탐색하는 전략을 사용할 수 다. 이 전략의 이동수는 \(NM+N+M-3\)이므로 항상 성공함을 알 수 있다. E. Count The Blocks (-5) 간단한 DP이나, 모듈러를 잘못 해 5번이나 틀렸다.