leo020630의 블로그

A. Mocha and Math (00:07, +) 모든 수를 AND연산해 출력하면 된다. B. Mocha and Red and Blue (00:17, +) 문제에서 하라는 대로 나이브하게 색칠하면 된다. \(N\)이 작아 여러가지로 구현할 수 있다. C. Mocha and Hiking (00:25, +1) \(A_i = 0, A_(i+1) = 1\)인 구간이 있거나, \(A_1 = 1\)이거나, \(A_n = 0\)이면 경로를 찾을 수 있다. 어떤 경우에서든 셋 중 하나를 만족하기 때문에 탐색에만 집중하면 된다. D. Mocha and Diana (00:45, +) D1은 \(N^2\)개의 정점 쌍에 대해 더해도 되는지 판단한 후 Union-Find를 이용해 그리디하게 더해주면 시간 안에 문제를 해결할..

D-1 대회를 위해 팀원분들이 있는 포항으로 내려갔다. 간단하게 식사를 하고 https://codeforces.com/gym/103049 로 팀연습을 했다. 내가 푼 문제는 쉬운 구현문제인 I와 K였는데, 간단한 구현문제임에도 불구하고 각각 8틀, 4틀을 하면서 다음날 있을 대회가 불안해졌다.. 페널티로 순위가 갈리는 일만 만들지 말자고 생각했다. D-Day ~00:13 약간의 issue로 인해 문제를 2~3분 늦게 보기 시작했다. 내가 잡은 문제는 I~L이었는데, 만만한 문제가 하나 없어보였다. 그러던 중 J의 범위가 상당히 작다는 것을 깨달았다. 하지만 문제는 생각보다 더 작다 생각한 것으로, \({20 \choose 10}=184756\)을 계산하고 무지성 브루트포스를 냈다 시간초과를 받았다. 1분..

A. Ezzat and Two Subsequences (00:02, +) 가장 큰 원소만 포함하는 그룹과 아닌 그룹으로 나누어주면 된다. B. Moamen and k-subarrays (00:07, +) pair등을 이용해 등장 순서를 같이 저장해준 후 정렬한 배열에서와 원래 배열에서 모두 인접한 구간들의 개수를 세주면 된다. C. Moamen and XOR (00:43, +2) \( {n \choose 0}+{n \choose 2}+{n \choose 4}..\) 를 구해준 후 포함배제 원리를 이용해 계산해주면 된다. 위의 식의 값이 \(2^{n-1}\)이라는 것을 이용하면 쉽게 코딩할 수 있지만, 나는 빨리 풀겠다는 생각에 이항계수를 \(O(1)\)에 구하는 코드를 긁어와서 풀었다.

A~B는 따로 쓰지 않겠다. C. Reorder Cards (00:07, +) *481 2차원으로 들어오는 점들을 좌표압축 해주면 된다. D. Takahashi Tour (00:13, +) *710 기본 DFS 문제다.. 이게 왜 D인지도 모르겠다. E. Stronger Takahashi (00:55, +) *1423 https://www.acmicpc.net/problem/15944의 하위호환이다. 펀치 횟수를 1 증가시키며 BFS를 돌려주면 된다.

[1차 예선] 후기는 쓰는 걸 까먹어서 없다. 문제 난이도는 전반적으로 어렵지 않았는데, 알고리즘 배치가 그리디 4개+Union-Find 1개인건 좀 그랬다.. [2차 예선] 이번엔 캡처를 까먹었다.. 내 점수는 1번+2번+3번+4-1번 = 681점이다. [1번] 체감상 1차예선 1번보다도 쉬웠다. 원의 방정식을 알고 정수의 제곱근을 구할 수 있다면 어렵지 않게 해결할 수 있을 것이다. [2번] 처음 봤을때는 잘 가늠이 가지 않았다. 그림을 조금 들여다보다 계산기에 \(8!\)을 넣었는데 40320이 나왔다. 굉장히 작다는 것을 깨닫고 풀이의 방향이 완전탐색임을 직감했다. 각 꼭짓점에 점들을 배정해준다면 거리는 간단한 관찰을 통해 구할 수 있다. 관찰 : 만약 직8각형을 일정 방향으로 밀었을 때 거리가 ..

셋은 https://codeforces.com/gym/102625/standings 을 사용했다. ~00:23 내가 A~C를 보기로 했다. 처음에 A를 보았지만, 디스크립션이 너무나도 이상해 잘 이해가 되지 않았다. 15분쯤 보다 B가 주르륵 풀리길래 넘어갔다. B는 알파벳의 홀짝성을 이용한 문제이다. 난 원소 3개짜리 pair를 정렬하는 더러운 방식을 썼지만, 더 깔끔한 풀이가 있을 수 있을 것으로 보인다. ~01:15 A의 거지같은 디스크립션을 가까스로 이해해 AC를 받았다. 문제 자체는 간단한 if문으로 해결된다. ~01:58 그 다음으로 많이 풀린 문제인 F를 잡았다. 자리수가 최대 9자리이고 쓸 수 있는 숫자도 3개이니 완전탐색으로 해결될 것 같았다. 풀이와 구현 모두 빠르게 했지만, \( [L..

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번이나 틀렸다.