ABC_194_D - Journey
n개의 정점으로 이루어진 그래프가 있다. 현재는 그래프의 1번에 있는데 1/n 확률로 다른 정점을 선택할 수 있다. 이때 모든 정점을 선택하게 되는 시도 횟수의 기댓값을 구하는 문제. 위 블로그를 참고함. 일단, 성공 확률을 p 라고 할 때, 성공할 때까지 수행 할 때의 시도 횟수는 확률의 역수(1/p)가 된다. 라는 사실을 알아야 풀 수 있는 문제. 증명…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
study 29
68 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의 경우 어차피 상관 없기 …
62 ABC_194_E - Mex Min
0≤i≤N−M 범위에서 mex의 최솟값을 구하는 문제. Mex(x1...xk): x1...xk 에 속하지 않는 가장 작은 0이상의 정수. 아주 간단하게 생각해보면 쉽게 풀린다. Ai의 최대 범위가 N이므로 0부터 N까지의 수를 맵에 넣어 두고 범위 안에서 Ai의 값이 나오면 맵에서 제거, Ai값이 없어지면 맵에 추가하는 방식으로 할 수 있다. 즉, 속하지 …
61 TENKA1_2018_C - Align
적당히 N개의 배열을 정렬해서 양 옆 원소의 차이의 절대값의 합의 최댓값을 구하는 문제. 먼저 어떻게 하면 최대가 될지 대충 생각해보면 큰 값, 작은 값이 번갈아가면서 나와야 한다. 아래부턴 에디토리얼을 참고함. 예시로 홀수 번째 인덱스가 큰 값들, 짝수 번째 인덱스가 작은 값들이라고 놓으면, 절대값을 한 결과는 (큰 값 - 작은 값)이 된다. n = 5일…
60 ABC_115_D - Christmas
버거를 일정 규칙으로 쌓을 수 있다. 해당 레벨의 버거의 x층 까지 중에 패티가 몇 개인지 구하는 문제. 일정 규칙: 레벨 0의 버거는 패티 1개이다. 레벨 L의 버거는 번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 + 번이다. 분할 정복으로 레벨 L의 버거의 패티 수를 빨리 구할 수 있다. 번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 …
59 ARC_100_A / ABC_102_C - Linear Approximation
N 개의 a 배열에서 적당한 b 값을 구해서 아래 식을 최소로 만드는 b 값을 찾는 문제. 먼저 자기 인덱스 + 1만큼 빼고 시작하자. 그러면 | a[i] - b | 의 최솟값을 찾는 문제가 되는데.. 이건 중앙값을 쓰면 된다. 자세한 증명은 참고. a[i]를 정렬한 다음 중앙값으로 b를 설정하고 정답을 구하면 된다. 위 중앙값을 골라야 한다는 사실을 모르…
