leo020630의 블로그

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, ..

A. Donut Shops (00:05, +) 한 가게는 도넛 하나를 $a$원에 판매하고, 다른 가게는 도넛 $b$개를 $c$원에 판다. 이 때 첫 가게가 유리한 시점은 무조건 도넛을 1개 구매하는 시점이다. 이때 첫 가게가 더 싸지 않다면 언제나 두 번째 가게를 이용하는 것이 효율적이다. 다른 경우도 마찬가지로, 도넛을 b개 구매하는 시점이 두 번째 가게가 가장 효율적인 순간이다. B. 01 Game (00:09, +) 연산 한번당 0과 1이 각각 하나씩 사라지므로 min(0의 개수, 1의 개수)의 홀짝성을 따지면 답을 구할 수 있다.대회 중에는 머리가 빠르게 돌아가지 않아 stack을 통해 구현했다. C. Pluses and Minuses (00:20, +) 주어진 수도 코드를 해석해야 한..

A. Digits Sum (00:01, +) $(N+1)/10$을 출력하면 된다. B. Reverse String (00:26, +) 문자열의 크기가 상당히 작으므로 만들 수 있는 전체 문자열에 대해 모두 확인해보아도 $O(N^2)$으로 시간 내에 문제를 해결할 수 있다. C. Penalty (00:13, +) 어느 한 팀에게 골을 몰아주는 것이 항상 최적이다. D. Backspace (00:35, +) 뒤에서부터 홀짝성을 판별하며 그리디하게 선택해주면 된다.