10월 4일 오후 8시에 진행되었던 SRM 369의 DIV 1 결과입니다. 이 때 서버 렉이 한동안 너무 심해서, 결과가 레이팅에 반영되지는 않았습니다.

1-10위 결과입니다. 별로 안예쁘지만 그래도 예쁘게 봐주세요~~~
상위 10명이 저빼고 다 동구권이네요 -_-; 러시아4 우크라이나3 폴란드1 슬로바키아1 - 상위랭커 분포가 이럴때는 문제가 수학문제스러운 경우가 많습니다. 저는 챌린지빨... ㄱ- 150위권 내에 한국인 중에서는 astein님이 111위를 차지했습니다.
Easy(250pt) - 총 maxA개의 'A'와 maxB개의 'B'가 있고, 이것으로 string을 만들려고 합니다. 그런데 'A'는 연속으로 countA번 넘게 나올 수 없고, 'B'는 연속으로 countB번 넘게 나올 수가 없습니다. 가능한 최장 string 길이는 얼마일까요?
이 수들의 범위가 100만 이하이므로, 모든 가능한 경우에 대해 계산할 수는 없습니다. 제 경우에는 휴리스틱 or 그리디를 사용했습니다. 설명도 좋지만 프로그램을 따라가면서 분석해보시는 것도 좋겠습니다. (설명하기 귀찮아서라던가 시간이 오래 지나서 까먹었다던가 하는게 아니라.. 하하하하하하)
[code c++]
class BeautifulString
{
public:
int maximumLength(int countA, int countB, int maxA, int maxB)
{
if (!maxA) return min(countB, maxB);
if (!maxB) return min(countA, maxA);
int result = 0;
while (countA>=1 && countB>=1)
{
if (countA {
int diff = maxB - 1;
if (countB-diff result += 1 + (diff+1);
countA -= 1;
countB -= diff+1;
}
else
{
int diff = maxA - 1;
if (countA-diff result += 1 + (diff+1);
countB -= 1;
countA -= diff+1;
}
}
if (countA)
result += min(countA, maxA);
if (countB)
result += min(countB, maxB);
return result;
};
};
[/code]
Medium(500pt) - f(0), f(1)이 주어지고, n>=2에서 f(n)=abs(f(n-1)-f(n-2))로 정의될 때, 아주 큰 i에 대해서 f(i)를 구하라는 것이 문제의 골자입니다. i가 아주 크므로 노가다로 구할 수는 없습니다. 그러나 어떤 특별한 경우만 처리해주면 노가다스럽게 구할 수가 있습니다.
f(0) = 29, f(1) = 27라고 합시다. 그러면 f(2)부터는 다음과 같습니다.
(29 27) 2 25 23 2 21 19 2 17 15 2 13 11 2 9 7 2 5 3 2 1 1 0 1 1 0 ...
경향성을 찾으실 수 있겠죠? 마지막에 (5 3) 2 (1 -1)이 되어야 하는데 마이너스는 불가능하므로 1이 됩니다. 즉 f(1)이 f(0)에 비해 많이 작지 않다면, 어떤 범위까지는 수식을 통해서 f(i)들을 구해나갈 수 있음을 알 수 있습니다. 이렇게 '점프'를 통해서 찾아나가면 i가 아주 커도 쉽게 구할 수가 있습니다. 마지막엔 반복이 이루어지는데 이 문제에서의 모든 수열은 이런식으로 3개씩의 반복으로 끝납니다. 이 경우에도 점프를 통해서 쉽게 i를 키울 수 있습니다.
엄밀하지 않은 증명은 다음과 같습니다 : f(i), f(i+1), f(i+2)는 항상 f(i+3), f(i+4), f(i+5)보다 작거나 같게 됩니다. 일정 비율 이상으로 급격히 작아지는 경우에는 그냥 계산해도 됩니다. (이 속도로 작아지면 금방 0에 가까워지고 무한한 반복구간이 임박하므로) 그렇지 않다면 위의 '점프'를 사용해서 i도 키우고 수도 급격히 작게 만듭니다. 이렇게 하면 log(처음 주어진 수) 정도의 시간복잡도로 답을 구할 수 있습니다.
[code c++]
class AbsSequence
{
public:
long long get_next(long long a, long long b, long long index)
{
while (1)
{
if (a==0 || b==0) { index %= 3; }
if (index==0) return a;
if (index==1) return b;
if (a>b && 2*b-a>0 && 3*b-2*a>0 && b)
{
long long expected_step = b/(2*(a-b));
if (index if (expected_step > 1)
{
long long new_a = a - 2*(a-b)*expected_step;
long long new_b = b - 2*(a-b)*expected_step;
a = new_a; b = new_b;
index -= expected_step*3;
continue;
}
}
long long new_a = b;
long long new_b = abs(b-a);
a = new_a; b = new_b;
index --;
}
}
vector getElements(string first, string second, vector indices)
{
long long s0;
long long s1;
sscanf(first.c_str(), "%lld", &s0);
sscanf(second.c_str(), "%lld", &s1);
int i;
int n = indices.size();
vector res;
for (i=0; i {
long long ind;
sscanf(indices[i].c_str(), "%lld", &ind);
long long result = get_next(s0, s1, ind);
char temp[30];
sprintf(temp, "%lld", result);
res.push_back(temp);
}
return res;
};
};
[/code]
Hard(1000pt) - 문제를 풀고 다시 찾아뵙도록 하겠습니다 ㅠㅠ