ARC_091_B / ABC_090_D - Remainder Reminder
N을 넘지 않는 a, b 쌍 중에서 a % b가 K 보다 크거나 같은 개수를 구하는 문제. 예제 1에 힌트가 있는데, b에 대해 K + 1부터 N까지 다 돌려가면서 나머지가 K 이상이 되는 a의 개수를 구해주면 된다. N % b를 r로 두면, a가 r 이하인 경우엔 N / b + 1번 가능하고 r보다 큰 경우는 N / b번만 가능하다. K == 0일 땐, …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 34
72 71 ABC_226 - AtCoder Beginner Contest 226
A, B, C, D A, B: 간단 C: 그냥 dfs 탐색해주면 된다. D: x, y 모든 쌍에 대해 좌표의 차이 (기울기)를 gcd로 나눠서 중복을 제거하면서 저장하면 된다.
70 ABC_140_D - Face Produces Unhappiness
사람들이 L, R 방향을 바라보며 서 있고, 서로 같은 방향을 바라보면 happy이다. 이때 k 번의 횟수만큼 (l, r) 범위의 사람들의 방향을 뒤집을 수 있다. 최대로 happy 하게 만들 수 있는 사람의 수를 구하는 문제. 딱 보면 어려운데 포인트를 잘 알아채면 굉장히 쉬워지는 문제. 위 사실을 알면 쉽게 풀린다. 먼저 간단한 증명은 LLL ... R…
69 CODEFESTIVAL_2016_QUALA_C - Next Letter
문자열과 k가 주어진다. k번 연산을 통해 만들 수 있는 사전 순으로 가장 작은 수를 구하는 문제. 연산: 다음 문자로 변경, 단 z는 a로 변함. 일단 그리디 적으로 생각해보면 사전 순으로 최소가 되려면 앞 문자를 최대한 a로 만들어야 한다. a로 만들 수 없으면 아예 연산을 안 하는 것이 낫다. 위 두 규칙에 맞게 문자열을 돌면서 계산해주면 된다. 단,…
68 ABC_194_D - Journey
n개의 정점으로 이루어진 그래프가 있다. 현재는 그래프의 1번에 있는데 1/n 확률로 다른 정점을 선택할 수 있다. 이때 모든 정점을 선택하게 되는 시도 횟수의 기댓값을 구하는 문제. 위 블로그를 참고함. 일단, 성공 확률을 p 라고 할 때, 성공할 때까지 수행 할 때의 시도 횟수는 확률의 역수(1/p)가 된다. 라는 사실을 알아야 풀 수 있는 문제. 증명…
67 ARC_068_B / ABC_053_D - Card Eater
수가 적혀진 N개의 카드들이 있다. 카드 중에 3개를 고른 후 가장 작은 수와 가장 큰 수를 빼고 남은 수는 다시 덱에 넣는다. 다른 수의 카드의 개수의 최댓값을 출력하는 문제. 먼저 3개를 고르고 하나를 다시 집어넣는 연산을 잘 살펴보자. 그냥 아무 두 개의 카드를 제거하는 것과 같다는 것을 알 수 있다. 일단, 각 카드가 한 장밖에 없는 경우는 연산을 …
66 ARC_097_A / ABC_097_C - K-th Substring
문자열 s 의 모든 부분 문자열 중에서 k 번째로 작은 문자열을 구하는 문제. 일단 힌트는 k가 아주 작다는 것이다. (최대 5) s 의 길이가 최대 5000이므로 s의 모든 부분 문자열을 구하는 것은 n^2이 되고 이론상 시간 안에 들어올 수 있다. 중복을 제거하기 위해 맵을 사용하고, 구한 모든 부분 문자열을 맵에 넣으면 쉽게 풀 수 있다. 처음 제출한…
65 ABC_216_E - Amusement Park
n개의 a 배열이 주어지고 최대 k개를 골라서 최대가 되도록 고르는 문제. 단, 한번 고를 때마다 a 배열의 원소의 값은 1씩 감소한다. 뭔가 이분 탐색으로 가능할 것 같은데 생각보다 쉽지 않았다. 먼저 k개를 넘지 않는 최대 개수를 고르는 지점을 이분 탐색을 이용해서 구할 수 있다. k 개에서 남은 개수만큼 더 고를 수 있는데 이건 따로 한 번 더 탐색해…
64 CADDI_2018_B / CADDI_2018B_D - Harlequin
플레이어와 Lunlun이 번갈아 가며 게임을 한다. 한 턴에 다른 색의 사과만을 먹을 수 있다. 마지막 사과를 먹은 사람이 승자일 때 승자를 구하는 문제. 이런 게임류 문제가 생각보다 까다롭다. 일단, 예제 1번에서 얻을 수 있는 정보는 사과가 한 종류만 남았을 경우 짝수개이면 무조건 진다는 것이다. (하나씩밖에 못 가져가므로) 사과가 두 종류일 때를 시뮬…
63 ABC_219_D - Strange Lunchbox
도시락이 있고 최소 횟수로 x개 이상의 타코야키와 y개 이상의 타이야키를 고르는 문제 딱 보니 dp 냄새가 난다. 범위도 300으로 작으니 해볼만 하다고 생각. 위처럼 dp를 정의하고 다 돌려주면 된다. 단, j, k 값이 계산 중에 300 범위를 넘어갈 수 있는데, 이는 x, j 중에 최솟값으로 처리하면 된다. x 값이 넘는 j의 경우 어차피 상관 없기 …