leo020630의 블로그

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번이나 틀렸다.

A. Gregor and Cryptography(00:04, +1) 주어지는 수가 5 이상의 소수이므로 홀수임이 보장되고, $N \equiv 1 \pmod {N-1}$ 이므로 2와 $N-1$을 출력하면 된다. B. Gregor and the Pawn Game (00:08,+) 앞에서부터 보며 해당 칸에 올 수 있는 폰들 중 가장 왼쪽에 있는 것을 선택해주면 된다. C. Web of Lies (00:20, +) 본인보다 큰 노드와 하나라도 연결되어 있으면 죽음을 알 수 있다. 따라서 각 연결을 큰 쪽에서 작은 쪽으로의 일방향 연결이라 생각했을 때의 indegree 갯수를 관리해주면 된다. D. Integers Have Friends (01:54, +5) 말할 거리가 많은데, 처음 봤을 때 파라메..

A, B는 복기하지 않겠다. C. Min Difference (00:05, +) *246 $min \left| a_i-b_j \right|$ 를 구하는 문제이다. a의 모든 원소를 b에 대해 이진탐색 해주면 가장 가까운 원소 후보 2개를 $O(logN)$에 구할 수 있다. D. Querying Multiset (00:16, +) *775 지금까지 더한 가중치를 저장한 후, 새로 들어오는 원소는 그 만큼을 빼준 후 pq, set 등의 자료구조에 넣는 것으로 해결할 수 있다. E. Safety Journey (01:05, +4) *1410 $DP[i][j]$를 $i$로 끝나는 길이 $j$의 여행으로 정의하자. 이렇게 정의하면 점화식을 다음과 같이 세울 수 있다. $i$와 연결된 노드..