leo020630의 블로그

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\)와 연결된 노드..

A. PizzaForces (00:02, +) 모든 피자의 크기 대비 가격이 동일하기 때문에 만들 수만 있다면 해당 크기에 2.5를 곱한 값이 답이 된다. 6 이상의 모든 짝수를 만들 수 있음이 자명함으로 홀수와 6 미만일 때에만 예외처리를 진행하면 된다. B. Two Tables (01:16, +3) 단순 Case Work 문제지만, 코딩 뇌절으로 인해 가장 늦게 맞춘 문제가 되어버렸다. Case Work 문제일 때에는 손코딩을 하고 들어가는 습관을 기르자. C. Coin Rows (00:36, +) 문제 이해를 잘못해 해결에 오랜 시간이 걸렸다. Alice가 내려갈 칸을 정하면 Bob의 점수는 누적합을 이용해 \(O(1)\) 에 구할 수 있으므로 총 \(O(N)\) 시간에 해결할 수 있다. D. Sa..

대차게 망했다... A. Cherry (00:03, +) 잘 관찰하면 구간의 길이가 2보다 큰 경우는 필요 없음을 알 수 있다. 따라서 이웃된 원소들의 곱 중 최댓값이 답이다. C. Mikasa (01:51, +8) B를 보고 거의 바로 넘어왔는데, B보다 풀이가 먼저 떠올라 잡게 되었다. 하지만 정제되지 않은 상태에서 코딩을 잡아서인지 코드가 끝도 없이 길어지기 시작했고, 끊임없는 맞왜틀에 빠졌다. 결국 맞긴 했지만, 반성할 부분이었다고 생각한다. 전체적으로 한숨만 나오는 라운드였다. UCPC 예선이 당장 내일인데.. 이런 경우가 생기지만 않았으면 좋겠다.

A. Level Statistics (00:05, +1) 각 과정에서 시도 횟수와 성공 횟수가 단조증가인지, 성공 횟수의 증가량이 시도 횟수의 증가량보다 낮은지를 판별해주면 된다. B. Middle Class (00:14, +) \(x\) 초과인 점들을 세며 \(x\) 미만인 점들 중 가장 큰 점부터 나누어주면 된다. C. Circle of Monsters (-6) 다음 몬스터를 폭발 데미지로 죽일 수 있는 몬스터들을 하나의 구간으로 묶은 후, 가장 효율적인 시작점을 찾아주면 된다. 엄청난 구현 실력으로 대회 안엔 해결하지 못했다.

A. Alarm Clock (00:07, +) 문제를 이해하기 힘들어 예제를 보고 문제를 예측했다. 문제 자체는 간단한 if문을 사용하면 풀린다. B. Ternary String (00:10, +) 각 문자별로 마지막에 나온 위치를 저장하며 가면 \( O(N) \)에 해결할 수 있다. C. (Not So) Simple Polygon Embedding (00:41, +) 공책에서 풀고 \(O(1)\) 로 출력하는 기하 문제이다. 이외에도 이진탐색을 이용해 해결하는 방법이 있다고 한다. D. Multiset (01:00, +2) Multiset을 구현하는 문제인데, 메모리 제한이 \(O(N)\)이라 Heap 자료구조를 사용하기 힘들다. 이는 펜윅 트리를 사용하면 해결된다. 주어지는 값이 최대 \(10^6\)..

A. Subsequence Permutation (00:03, +) 문자열을 sort한 문자열과 기존 문자열이 얼마나 일치하는지 세주면 된다. C. Maximize the Intersections (01:19, +) 연결되지 않은 정점을 \( 2a \)개라 할 때, 1번째와 \(1+a\)번째를 잇는 식으로 진행해주면 된다. B로 인해 멘탈이 나가있었던 상태기 때문에, 정당성은 증명하지 않았다. D. Array Differentiation (01:01, +) 주어지는 \(n\) 개의 값중 \(n-1\) 개는 \(B_1-B_k\) 꼴로 만들 수 있다. 이후에는 남은 하나의 값을 \(n-1\)개로 만들 수 있는지 판별하면 된다. 남을 하나의 값을 정하는 데에 \(O(N)\), 완전탐색에 \(3^N\)이 소요되..

A. LR Constraints (00:06, +) *214 \(O(N)\)짜리 배열을 이용해 Counting 해주면 문제를 해결할 수 있다. \( N

A~B는 따로 복기하지 않겠다. B에서 Yes를 YES로 출력하는 코포식 출력으로 한번 틀렸다. C. chokudai (00:13, +1) *559 주어진 문자열에서 "chokudai"를 순서대로 읽는 방법을 출력하는 문제이다. 찾아야 하는 문자열에 같은 문자가 없기 때문에 DP를 사용하면 \( O(8N) \) 정도에 문제를 해결할 수 있다. D. Number of Shortest paths (00:24, +) *755 다익스트라에 DP를 얹는 방법으로 해결할 수 있다. 대회 중에는 멍청하게도 pq를 사용했지만, 간선의 길이가 모두 1이라는 성질 덕에 일반 queue를 사용해도 문제를 해결할 수 있다.

A. Polycarp and Coins (00:38, +) \(n\)을 3으로 나눈 후, 나머지가 1이라면 1원 동전을, 2라면 2원 동전을 하나씩 더 써주면 된다. B. Wonderful Coloring (01:12, +1) 주어진 수들을 정렬한 후, 각 숫자의 갯수가 \(k\) 개 초과인 경우를 주의하며 색을 차례대로 부여하면 풀린다. B1은 수를 문자열로 바꾸고, k를 2로 고정한 버전이다. C. Interesting Story (01:25, +1) 과반수 이상 등장하는 알파벳이 a라 하자. 이는 각 문자열마다 "a의 등장 횟수 - 다른 알파벳의 등장 횟수" 를 계산하고, 이를 내림차순으로 정렬해 누적합이 양수인 조건을 만족하며 더해주면 최대 개수의 문자열을 선택할 수 있다. 이를 b, c, d, ..