leo020630의 블로그

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, +) 뒤에서부터 홀짝성을 판별하며 그리디하게 선택해주면 된다.

A. AquaMoon and Strange Sort (00:06, +) 방향을 유지하며 이동하려면 짝수 칸만큼 이동해야 한다. 따라서 본인이 있던 칸과의 홀짝성은 변하지 않고, 정렬 후에도 홀짝성이 변하지 않으면 가능하다.

A. Potion-making (00:02, +) \(\frac{100}{\gcd(100,n)\) 이 답이다. B. Permutation Sort (00:19, +4) 양쪽 끝 수를 보며 최적의 경우를 생각해주면 된다. D. Armchairs (01:05, +1) \(DP[i][j]\)를 \(i\)번째까지의 의자 모두를 앞에서 \(j\)번째까지로 옮기는 최소 비용으로 정의하자. 이는 \(i\)번째 칸이 1이고 \(j\)번째 칸이 0인 경우에만 갱신 가능한데, \(dp[i][j-1]\)과 \(dp[i-1][j-1]+|i-j|\)중 작은 것을 선택해주면 된다.