leo020630의 블로그

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에서 이런 간단한 문제를 ..

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\)..