leo020630의 블로그

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

이번에도 비대면으로 진행해 다른 팀원들의 진행 상태가 정확히 파악되지 않았다. 따라서 간략히 서술하도록 하겠다. (~01:19) 내가 보기로 한 문제는 H~J였고, 뭔가 생각하기 귀찮았던 H, 고급 트리 알고리즘이 필요해보였던 J를 거르고 I를 잡았다. I는 쉬워 보였지만 구현이 어느 정도 필요했고, 원체 코딩 속도가 느린 나인지라 코딩에 꽤나 오랜 시간이 걸렸다. 3700B짜리 코드를 짠 후, 2번 정도 틀리고 난 후 AC를 받았다. (~03:00) I를 풀고 오니, 다른 팀원분들이 다른 문제를 모두 밀어 놓은 상태였고, 가장 어려운 두 문제인 F와 J가 남은 상태였다. J는 풀이를 다른 팀원분에게 대강 들었지만 시간 안에 짤 자신이 없었다. 이후 F번으로 넘어왔다. 관찰을 통해 직선을 하나 고정한 후..

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 예선이 당장 내일인데.. 이런 경우가 생기지만 않았으면 좋겠다.

셋은 https://codeforces.com/gym/103091을 사용했다. Dashboard - Stanford ProCo 2021 - Codeforces codeforces.com 이런 팀 대회 후기는 전체적인 동향을 기술해야 하는 것이 맞으나, 원격으로 진행하여 다른 팀원분들의 진행 상황이 정확히 파악되지 않았기에 내 기준으로 서술하도록 하겠다 ~00:09 내가 맡은 문제는 J~N이었고, 쓱 훑어본 결과 쉬운 문제가 두 개나 있었다. J는 Div 3 A, N은 Div 2 A 수준의 쉬운 문제여서 간단히 밀 수 있었다. ~00:41 K, L, M중 가장 쉬운 K를 잡았다. 투 포인터를 응용해 \(O(N)\)으로 해결할 수도 있는 문제지만, 이분탐색을 써 해결하였다. Div2에서 이런 간단한 문제를 ..