이동식 저장소

보통 제목은 반대인 경우가 많다. Problem - 706C - Codeforces codeforces.com 문자열을 사전 순으로 정렬하는 문제인데, 특이하게도 문자열의 순서를 바꿀 수 없다는 제한이 있다. 대신 문자열을 앞뒤로 뒤집는 연산만 가능하다. 또, 뒤집는 비용도 문자열마다 모두 다르다. 이제 문자열을 정렬하는 데 드는 최소 비용을 계산해 보자. 문제에서 사전 순서대로 정렬하라고 했으므로, 앞에서부터 오름차순으로 정렬해야 한다. $cur$번 문자열을 뒤집는 상태가 $s$일 때, $cur$부터 끝까지 정렬하는 데 드는 최소 비용을 $dp(cur,~s)$라고 하자. $cur$번 문자열을 뒤집는다면 $s=1$이고, 뒤집지 않는다면 $s=0$이다. $cur$번 문자열에서 드는 비용을 $cur\_cos..

코드포스에는 왜 이리 지루한 사람이 많은가? Problem - 455A - Codeforces codeforces.com 지문이 헷갈리기 쉽게 쓰여 있어서, 일단 문제를 정확히 이해하자. $n$개의 정수 $a_{1},~a_{2},~\cdots,~a_{n}$이 있다. 임의의 $a_{k}$를 골라 지우고, 모든 $a_{k}-1$과 $a_{k}+1$을 지운다. 예를 들어 $2$를 하나 지웠다면 모든 $1$과 $3$도 지워야 한다. 이때 얻을 수 있는 점수는 $a_{k}$점이다. 수를 하나 지우면 양 옆의 수도 없어져서 골치아픈 문제이다. 만약 $a_{k}-1$만 지워지는 조건이었다면 골드 하위 수준의 문제였을 것이다. 그러나 아주 간단한 제한을 걸면 이 문제 역시 골드 하위급으로 만들어버릴 수 있다. 바로 수..

Problem - 327A - Codeforces codeforces.com 0과 1로 이루어진 길이 $N$짜리 수열이 있다. 이 수열에서 연속된 구간 $[i,~j]$를 단 한 번만 골라 구간 안에 있는 모든 0을 1로, 1을 0으로 뒤집는다. 뒤집은 후에 1은 최대 몇 개 있을 수 있을까? 이 문제는 제한이 매우 작아서 $O(N^{3})$에도 풀 수 있지만, $N$이 커지더라도 풀 수 있는 방법을 생각해 보자. Maximum Subarray 먼저 Maximum subarray라는 개념을 알아야 한다. Maximum subaray는 배열의 끝 칸에서 끝나는 부분합 중 최댓값을 구하는 알고리즘이다. 식으로 쓰면 $ms[i]$는 $[1,~i]$ 구간에서 $i$를 포함하는 부분합 중 최댓값을 의미한다. 배열 ..

매우 오랜만에 코포에 참가한다. Dashboard - Codeforces Round #677 (Div. 3) - Codeforces codeforces.com A. Boring Apartments 매우 간단한 수학 문제이다. 예상 난이도: 브론즈2 B. Yet Another Bookshelf 문제를 읽었을 땐 뭔가 어려워 보였는데, 생각해 보니 (인접한 두 segment 간의 거리)-1을 모두 더하면 답이 된다. B번을 너무 어렵게 생각해서(약 15분) D번 풀 시간이 부족해졌다.. 예상 난이도: 실버4 C. Dominant Piranha C번도 간단해 보이는 구현 문제이다. 우선 정답의 후보는 크기가 가장 큰 피라냐들로 한정한다. 가장 크지 않은 피라냐도 정답이 될 수 있는 경우가 있지만, 알고리즘을 ..

무려 3달만에 대회에 참여한다. 너무 오랜만이라서 조금 걱정도 되는데.. 잘 할 수 있겠지? Dashboard - Codeforces Round #661 (Div. 3) - Codeforces codeforces.com 0:00 ~ 0:14 A번을 본다. A번은 어려워 보이지만 알고 보면 간단한 경우가 많기 때문에 너무 어렵게 생각하면 안 된다. 그런데.. A. 배열 $a$가 주어질 때, 차이가 1 이하인 임의의 두 수를 골라서 크지 않은 수 하나를 지운다. 이 연산을 0번 이상 반복하여 $a$의 원소를 하나만 남게 할 수 있을까? 간단한 문제다. 모든 인접한 두 수의 차이가 1 이하이면 "YES"를, 그렇지 않다면 "NO"를 출력하면 된다. A번다운 문제다. 그런데 왜 틀렸지? ??? 내가 아직 알지 ..