ARC_061_A / ABC_045_C - Many Formulas
문자열 s의 문자 사이에 + 를 넣어 만들 수 있는 수를 전부 더하는 문제. 그냥 말 그대로 +를 문자 사이에 다 한 번 씩 넣어서 만들 수 있는 수를 더하면 된다. 비트 연산으로 간단하게 가능.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
study 29
58 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…
52 ARC_084_A / ABC_077_C - Snuke Festival
n개의 배열 a, b, c가 주어진다. a[i] < b[j] < c[k] 를 만족시키는 모든 쌍의 개수를 구하는 문제. 순서 상관 없으니 정렬부터 해보면 뭔가 보인다. b를 기준으로 살펴보자. b의 원소 중 하나를 정했다면 가 해당 b 원소를 뽑았을 때 만들 수 있는 경우의 수가 된다. 모든 n에 대해 돌리면서 b의 원소를 기준으로 a, c 배열에 대해 이…
51 DIVERTA2019_D - DivRem Number
주어진 N에 대해 나눈 몫과 나머지가 같도록 하는 m을 모두 구해 더하면 된다. 수식을 조금 이용하면 된다. 먼저 구하고자 하는 favorite number를 m으로 두면 이 성립해야 되고, 양쪽으로 식을 정리하면 이 된다. 단, 1부터 모든 n까지 탐색은 시간 초과가 되므로 sqrt(n) 까지만 돌려주면 된다.
50 ABC_182_E - Akari
n개의 전구가 4방향으로 빛을 쏘고, m개의 블럭은 빛을 차단한다. 전체 그리드 (H*W)에서 총 몇 칸이 빛이 도달하는지 확인. 간단한 시뮬레이션 문제. 모든 전구에서 상 하 좌 우로 빛을 쏴주면서 카운트를 해주면 된다.
49 ARC_110_C - Exoswap
배열이 주어지고, 임의의 순열 P의 순서대로 swap을 했을 때 오름차순이 되는지 확인하는 문제. 그리디하게 접근해보자. 가장 큰 수는 가장 오른쪽으로 이동해야 되므로 가장 큰 수부터 탐색을 진행한다. 오른쪽으로 swap이 가능하면 swap을 해주고 자기 위치까지 계속 swap을 한다. 일종의 버블 정렬 느낌. 이때 P가 순열이므로 visited를 넣어 한…