leo020630의 블로그

A. Dial Up (00:18, +1) *442 제자리에서 계속 더하다 처음 다른 값이 나오면 가장 가까운 곳으로 이동하고, 이후에는 나오는 값에 따라 1이나 2를 더해주면 된다. 불가능한 경우 처리는 쉬우니 생략하도록 하겠다. B. Squares (00:54, +) *1273 \(1\)부터 \(sqrt(N)\)까지는 모든 경우가 되므로 다 더해준다. 그러면 각 \(x\)당 가능한 \(y\)의 개수가 \(O(sqrt(N))\)개가 된다. 따라서 각 경우에 대해 구간의 길이를 곱해 더해주면 된다. C. LIS to Original Sequence (01:42, +4) *1896 다음과 같은 과정을 따른다. LIS의 원소를 \(A_1..A_k\)라 했을때 (1) \(i

A~B는 따로 적지 않겠다. C. One More aab aba baa (00:05, +) *178 next_permutation() 함수를 이용하면 쉽게 구현할 수 있다. D. Coprime 2 (00:37, +3) *736 에라토스테네스의 체의 메커니즘을 이용한다. 모든 \(A_i\)에 대해 소인수를 구해준 후, 구한 소인수들로 에라토스테네스의 체 배열을 채워주면 된다. \(O(Nsqrt(N)\)에 문제를 해결할 수 있다. E. Chain Contestant (00:84, +1) *1413 비트마스크 DP이다. \(DP[i][j][k]\)를 \(i\)번째까지의 원소를 이용해 집합 \(j\)에 해당하는 색을 사용해 끝 색을 \(k\)로 하는 경우의 수로 정의하면 DP 갱신을 \(O(10 2^{10})\..

A. 2048 Game (00:03, +) 2048 이하인 수들을 모두 더했을 때 2048 이상이면 가능하다. B. Knights (00:05, +) 체크무늬로 칠한 배열을 출력하면 나이트가 갈 수 있는 칸의 색이 항상 달라지므로 최적이다. C. Perfect Team (00:18, +) \(min(c,m,(c+m+x)/3\)이 정답이다. D. Make The Fence Great Again (01:23, +3) 한 울타리에 대해 최대 2번까지만 높여주는 것이 최적임을 알 수 있다. 따라서 \(DP[i][j]\)를 \(i\)번째 펜스를 \(j\)만큼 올려줬을 때의 최소 비용으로 정의하면 \(O(N)\)에 문제를 해결할 수 있다.

A. Prime Subtraction (00:01, +) \(A-B=1\)이면 NO이다. B. Kill 'Em All (00:07, +) 좌표압축+정렬한 후 가장 먼 적한테 폭탄을 쏘는 것을 반복하면 된다. C. Standard Free2play (00:17, +) 디스크립션을 이해하면 구현은 어렵지 않다. 규칙을 잘 지키며 낙하하면 된다. C까지 풀었을 때 6등인가 했던거로 기억하는데 그 뒤로 하나도 못풀었다..

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