leo020630의 블로그

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

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를 사용해도 문제를 해결할 수 있다.