ABC_194_E - Mex Min
0≤i≤N−M 범위에서 mex의 최솟값을 구하는 문제. Mex(x1...xk): x1...xk 에 속하지 않는 가장 작은 0이상의 정수. 아주 간단하게 생각해보면 쉽게 풀린다. Ai의 최대 범위가 N이므로 0부터 N까지의 수를 맵에 넣어 두고 범위 안에서 Ai의 값이 나오면 맵에서 제거, Ai값이 없어지면 맵에 추가하는 방식으로 할 수 있다. 즉, 속하지 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 34
62 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를 설정하고 정답을 구하면 된다. 위 중앙값을 골라야 한다는 사실을 모르…
58 ARC_061_A / ABC_045_C - Many Formulas
문자열 s의 문자 사이에 + 를 넣어 만들 수 있는 수를 전부 더하는 문제. 그냥 말 그대로 +를 문자 사이에 다 한 번 씩 넣어서 만들 수 있는 수를 더하면 된다. 비트 연산으로 간단하게 가능.
57 ABC_222 - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）
A, B, C, D A, B, C: 쉬움 D: DP + prefix sum. 일반적인 DP로 하면 시간 초과가 되므로 prefix sum도 섞어서 계산해주면 된다.
56 PANASONIC_2020_D - String Equivalence
n 길이의 isomorphic 한 normal form를 전부 구하는 문제 예시에 2밖에 없어서 뭔가 애매한데 4 예시를 직접 만들어보자. 총 15개가 나오고 규칙을 찾을 수 있다. 좀더 formal하게는 이건 재귀적으로 간단하게 짤 수 있다.
55 ABC_129_D - Lamp
H * W 크기의 그리드가 있고 빈 칸에 램프를 놓을 수 있다. 램프는 장애물을 넘을 수 없고, 상하좌우를 밝힐 수 있다. 램프가 밝힐 수 있는 칸의 최대 수를 구하는 문제. 아주 간단하게 완전 탐색하면 시간 초과다. (모든 점에 램프를 넣어보고 칸 수를 계산) 빛이 비출 수 있는 칸 수를 계산할 때 시간을 줄일 수 있는데, 칸 별로 연속한 칸 수를 저장해…
54 ABC_099_C - Strange Bank
한 번에 인출할 수 있는 액수가 정해져 있고, 주어진 돈을 최소 몇 번만에 인출할 수 있는지 구하는 문제. 전형적인 DP 문제. 간단하게 로 정의하고 돌려주면 된다. 에디토리얼 보니 그리디로도 풀 수 있다.
53 AGC_034_B - ABC
주어진 문자열에서 ABC를 BCA로 최대 몇 번 바꿀 수 있는지 출력하는 문제. 생각보다 쉽지 않은데 몇 가지 특징을 써보자. A, BC는 덩어리로 움직이고 나머지 문자열은 무시할 수 있다. => 나머지 문자열이 나오면 더 이상 변환이 불가능하다. A, BC들이 적절히 만났을 때 모든 변환이 끝나면 A는 맨 뒤로 이동한다. (AABCBCBC => BCBCB…