일주일 돌아보기 (2024-01-16 ~ 2024-01-22)
요새 문제 푸는 것을 등한시 했다.
1) 올해 ICPC는 일정상 나가지도 못하였고, playoff가 생긴 이상, 이것도 참가는 불가능해보임
2) 현대모비스나 SCPC에서 기존보다 높은 상을 얻을 수 없을 것 같음
3) 코포 레드를 찍어서 딱히 CP적인 목표도 없음
4) SCPC, HCPC 등에서 확인한 폼 저하
아무튼, 최근에 다시 1일 1문제 풀이를 하고 있어서 (플랜디) 기억나는 문제들 복습
여름 때는 거의 하루에 다5를 하나씩 풀었기에 그정도까지 올라가는게 목표
BOJ #7687 지구 직육면체설 (P1)
자주 보이는 PS 문제 형태는 아니지만 개인적으로 흥미로운 편. (+ P1은 overrated라고 생각한다)
직육면체 지구의 전개도를 여러 방법으로 펼쳐서 모든 경우에 대해 최단 경로를 구하면 된다.
PS는 어차피 컴퓨터가 계산을 하기에 대부분의 경우 안전빵으로 케이스를 넓게 잡아도 되는게 흥미롭다.
BOJ # 17118 갓 소수 (P1, 하지만 구데기컵이라 의미 없음)
페르마 소정리를 이용하면 문제에서 구하는 것이 단순히 (A * N + B) % MOD 임을 알 수 있다.
다만, MOD를 모른다는 것이 문제 -> 예제의 값을 통해서 MOD를 알아낼 수 있다.
이 문제의 포인트는 시간제한이 -2초라는 점.
0ms로 돌아가는 c++ 코드를 제출하더라도 TLE를 받게 된다.
따라서 https://www.acmicpc.net/board/view/60301 에서 볼 수 있 듯, 특별한 언어를 통해 제출해야 한다.
구데기컵에 알맞는 재미있는 컨셉
BOJ #21162 뒤집기 K (P3)
일반적으로 Suffix array를 만드는 알고리즘으로도 풀 수는 있다.
다만, 해싱을 이용하여 두 문자열을 sort하는 방식으로도 풀리는데, 이 방식을 상당히 오랜만에 보아서 기억남.
BOJ #3345 괄호 (P3)
계속 드는 생각...
일단 pos[i] = (i번째 ')'의 위치) 라고 한다면, 다음과 같은 생각을 할 수 있다.
-> x1 + 2 <= pos[1]
-> x1 + x2 + 4 <= pos[2]
...
-> x1 + x2 + ... + xk + 2k <= pos[k]
-> x1 + x2 + ... + xk + 2k + x0 = N
위의 식을 만족하는 모든 (x0, x1, ... xk)에 대해서 C[x0] * C[x1] * ... * C[xk]의 합이 답이 된다.
일단 기본적으로 시간복잡도를 무시하고 보면... 다음과 같은 dp를 생각할 수 있다
-> dp[L][R] = (L, R)범위를 통해 얻을 수 있는 올바른 괄호 문자열의 개수
-> dp[L][R] = sum( dp[L + 1][K] * dp[K + 1][R] )로 표현이 가능하다. (단, S[L] = ')'면 0이다)
단순하게 dp를 굴리면 O(N^3)으로 통과가 불가함
위의 dp를 보니까 근데 ')'이 하는게 딱히 없다. 즉, ()와 []의 차이가 따로 보이지 않는다.
따라서 그냥 ()로만 채워도 되겠다는 생각이 든다.
-> 좀 생각해보니 어차피 () + [] 의 괄호랑 일대일 대응이 된다.
이젠 쉽다.
괄호문제 답게 prefix_sum의 값을 고려하면서 하면 된다. 이때 prefix_sum의 값은 음수가 될 수 없다.
dp[i] = (prefix_sum의 값이 i인 경우의 수)라면
-> nxt[i] = dp[i - 1] + dp[i + 1] * (S[cur] != ')') 로 계산하면 된다.
BOJ #2095 티켓 (P3)
당연히 생긴게 그리디같아서 고민했었지만, 잘못된 생각으로 반려시켰다.
우선은 O(N^2)짜리 풀이를 통과시켰다.
이건 최대로 들어갈 수 있는 가족의 수가 N / L임을 활용한 적당한 dp를 통해서 가능하다.
다만, 정해는 이것이 아니기에 조금 더 고민해 보았다. (정해가 O(N + M)이라고 적혀있음)
쉽게 생각해낼 수 있는 그리디적인 사고부터 확인하자
claim) 원하는 좌석(앞으로 딱뎀이라 함)을 최대로 넣을 때 K개까지 가능하다면, 답이 되는 경우에도 딱뎀은 K개
proof) 귀류법으로 아니라고 가정하자. 최대로 밀어넣은 배치를 S, 답이되는 배치를 T라 하자
-> S의 딱뎀이 T의 안 딱뎀이 겹친다면 : T의 안 딱뎀을 제거하고, 딱뎀을 넣으면 이익이 감소하지 않는다
-> 항상 딱뎀이 겹친다면 : T의 딱뎀 x개가 S의 딱뎀 x + 1개와 겹치는 경우가 존재하고, 마찬가지로 교체가 가능하다
딱뎀의 개수가 K개로 확정되어있으니, (빈 좌석에 넣을 수 있는 가족의 수)는 최대화시키는 것이 무조건 이득
지금부터 "남는 좌석의 수"이라 한다면, 빈 좌석에 가족들을 최대한 밀어넣고도 남는 좌석의 수를 의미한다.
즉, 어떠한 배치가 완성되었을 때 sum( ( seat[i] - seat[i - 1] ) % L )의 값이고, 이 값을 줄여야 더 많이 태울 수 있다.
dp[i] = (i 뒤에 딱뎀을 최대한으로 밀어넣었을 때, 남는 좌석의 수의 최솟값)이라고 정의한다면
-> dp[i] = dp[i + L]이 될 수도 있고, dp[i] = dp[i + 1] + 1이 될 수도 있다.
-> 이때 "최대한으로" 밀어넣어야 하므로, 밀어넣는 수가 최대가 되는 방법을 골라서 선택해야 한다. (둘 다 가능할수 있음)
BOJ #31028 순열의 개수 (P3)
길이가 X인 순열을 만들 수 있는지 보자. (X = i + j)
1) i개와 j개는 서로 겹치면 안되므로 min( invb[a[0]], invb[a[1]], ... invb[a[i - 1]] ) = lim >= j 가 성립
2) min( inva[X], inva[X + 1], ... inva[N - 1] ) = minva[X] >= i가 성립
3) min( invb[X], invb[X + 1], ... invb[N - 1]) ) = minvb[X] >= j가 성립
위의 세 조건만 만족하면 i개와 j개를 합치면 반드시 순열이 형성된다.
i + j = X이므로, j = X - i로 변형하면
1') lim >= X - i이므로, i + lim >= X
3') minvb[X] >= X - i 이므로, i >= minvb[X] - X
따라서 2)와 3')이 만족하는 segtree (or pb_ds)를 만들어준 뒤, 이 중에서 i + lim 이하의 원소 개수를 세주면 된다.
O(N)짜리 풀이가 있는지 좀 살펴봤다.
우선 다음을 정의하자
-> maxi[i] = max(a[0], a[1], ... a[i]), lack[i] = Maxi[i] - i, cnt[i] = (lack[x] = i인 x의 개수)
그러면 이제 b에서 (a[0], a[1], ... a[i - 1])이 부족한(=Lack) 부분을 채워주기를 기대하면 된다.
b의 j개 원소를 사용한다고 했을때 이들이 a의 초반 i개의 부족한 부분을 메꾸는 것은 다음 조건과 같다
1) a와 b는 겹치는 원소가 없어야 하므로 min( inva[b[0]], inva[b[1]], ... inva[b[j - 1]] ) >= i
2) 우리는 a가 부족한 부분을 b가 채워주길 바라고 있으므로 maxi[i] > max(b[0], ... b[j])
3) a에서 부족한 원소가 j개여야 한다. 즉 lack[i] = j여야 한다.
-> 1의 조건은 i의 상한을, 2의 조건은 i의 하한을 나타내며, 이들은 각각 단조감소/단조증가 한다.
-> 따라서 만족하는 i의 범위에 대해서 cnt를 투 포인터로 관리할 수 있으며, 답에 cnt[j]를 더해주면 된다.
다만, 아직 고려하지 않은 경우는 b가 최댓값을 가지고, 반대로 a가 채워주는 경우이다.
swap으로도 구할 수 있지만 다른 방식으로도 구할 수 있다.
max(b[0], b[1], ... b[j - 1]) = k라고 하자. 그렇다면, b의 시점에서는 k - j개가 부족하다.
k = j가 성립한다면, 그냥 (0, j) 자체가 가능하다는 뜻이니 answer++를 해주면 된다.
그렇지 않다면 maxi[k - j - 1] < j이고, j - i - 1이 가능한 i의 상한보다 작거나 같다면, answer++를 해주면 된다.
BOJ #12515 챔피언소트 (P3)
dp[i] = (크기 i짜리 순열 cycle을 정렬하기 위해서 필요한 셔플의 수)라고 정의하자
Claim) 서로 다른 두 개의 순열 사이클을 굳이 섞어서 셔플을 할 필요는 없을 것 같다
Proof) 존나 강력한 직관
cyc 크기가 i이라면 첫 번째 원소는 1/i의 확률로 j 크기의 cyc를 새롭게 만들어내고,
나머지 i - j개의 원소는 ‘랜덤하게’ 셔플되므로, 이전 상황이 i - j의 cyc인 것과 필요한 셔플수가 같다.
수식의 편의를 위해 dp[0] = 0라고 그냥 정의한다면,
\(dp[i] * i = \sum_{1\leq j\leq i}( dp[j] + max(dp[i - j],1)\)
→ answer = \( \sum dp[size\_of\_cyc] \)
사실 재미있게도 위의 수식에서 dp[i] = i 이다. (단, i = 1인 경우 제외)
또한, 더 생각을 해보면 claim과 상관없이 제자리가 아닌 원소들만 모두 골라서 소트해도 된다!
그냥 제자리가 아닌 소트 사용시, DP[i] = (제자리가 아닌 숫자가 i개일 때 필요한 셔플 수)라 하면
DP[N] = N임은 직관적으로나 수식적으로나 보일 수 있다. (← 이거 생각보다 쉽지 않음)
-> p[i] = (제자리가 아닌 N개를 셔플했을 때 i개가 제자리가 아닐 확률)이라 하자
-> lemma) (N개 셔플시 제자리 아닌 개수의 기댓값) = \(\sum_{0\leq i \leq N}{p[i] * i} = N - 1\)
-> DP[N] = \(1 + \sum_{0\leq i \leq N}{p[i] * DP[i]}\) 인데, 귀납가정으로 DP[0 ~ N - 1] = 0 ~ N - 1임을 적용하면
-> \(DP[N] - N = p[i] * DP[i] - p[i] * N \Leftrightarrow (1 - p[i]) * (DP[N]- N) \Leftrightarrow DP[N] = N\)
그 다음 이게 최적임을 보이면 됨.
-> "최적의 방법" ans[i] = DP[i] 임을 귀납법으로 위와 유사한 방식으로 증명할 수 있다.