TopCoder SRM 427

오전에 SRM이 있었다.

오전에 열리는 SRM에는 대체로 참가하는 사람들이 적은 것 같다. 그리고 그런 SRM에서 망하는 경향이 있는데 오늘도 어김없이 망했다. ㅠ

비교적 쉬운 250과 600 그리고 900이 출제됐는데 하나도 pass를 받지 못해 안드로를 향했다.

600문제는 사이클을 도는 동안 좌표 이동에 대해서 구현을 깜빡하고 안한 부분이 있어서 틀릴 줄 알고 포기하고 있었는데 나중에 보니 사이클 동안 좌표이동이 (0, 0) 이라 구현 안해도 상관없는 것을 알고 설마 맞나하고 기대했다가 결국은 0으로 나누는 버그로 어이없게 sys fail 나는 김빠지는 SRM이었다. 250은 쓸데없는 코드 한 줄 때문에 망쳤다. 그 한 줄을 넣는 순간에는 정신줄을 놓고 있었나보다.

8월 이후 괜찮은 추세를 타고 있었는데 이번 폭락으로 다시 원점으로 돌아왔다. 레이팅이 약간 하락했던 SRM 426은 unrated가 되었는지 그래프에서 사라졌다.

6월 중에 찍었던 1768점은 더더욱 멀어졌다.


250 - Design Calendar

외계 문명이 자신이 사는 행성에 맞게 달력을 만들고자 한다. 이 외계 문명이 사는 행성은 1회 공전하는데 yearLength가 걸리고 1회 자전은 dayLength가 걸린다. 지구에서와 같이 이 행성은 공전주기가 자전주기로 나눠떨어지지 않기 때문에 윤년이 생긴다.
이 달력을 기준으로 하면 매 P년 마다 달력상의 날짜 길이와 실제 날짜길이가 일치하게 된다. P를 구하시오

dayLength * d = yearLength * y
를 만족하는 최소의 d와 y를 구하는 문제라고 생각할 수 있다. 정답은 y가 된다.

식을 y에 관해 정리하면

y = dayLength * d / yearLength

가 된다. 여기에서 d는 미지수이다.

최소의 y는 dayLength와 yearLength를 통분하여

y = dayLength' * d / yearLength' (dayLength' 와 yearLength'는 서로소)

꼴로 바꾸면 알기 쉽다.
dayLength'와 yearLength'는 서로소이므로 y가 정수가 되기위한 최소의 d는 d = yearLength' 가 된다. 즉

y = dayLength' = dayLength / gcd(dayLength, yearLength)

이다.
int GCD(int a, int b) { if (b==0) return a; return GCD(b, a%b); } int shortestPeriod(int dayLength, int yearLength) { return dayLength / GCD(yearLength, dayLength); }
대회 중에는 멍청하게 yearLength가 dayLegnth로 나눠떨이지면 0을 리턴하는 코드를 집어넣었다가 틀렸다

500 - Locate Treasure

우선 아래와 같이 dig()를 정의하자

dig(x) := x                          if 0 <= x <= 9
dig(x) := dig(sum of digits of x)    if x >= 10

For example: dig(49) = dig(13) = dig(4) = 4.

당신은 초기에 (0, 0) 위치에서 북쪽을 보고 있다. 그리고 K와 multi가 주어지면 아래의 지시대로 움직어 보물을 찾는다.

1. Take dig(Gold number) steps forward, and then turn 90 degrees right.
2. Multiply Gold number by multi.

보물이 있는 위치를 "X Y" 포멧으로 리턴하시오

-	K will be between 1 and 10^9, inclusive.
-	multi will be between 1 and 1000, inclusive.

우선 dig() 에 대해 생각해 볼 필요가 있다.
dig() 함수는 어떤 숫자를 한자리 숫자로 변환하는 함수이다. 즉 변환 별과는 1~9사이의 숫자로 9가지 중 하나가 된다.
또한 dig(a) = dig(b) => dig(a*c) = dig(b*c) 가 성립한다. 이는 매우 중요하다.

step = dig(goldNumber), goldNumber = goldNumber * multi

를

step = dig(step), step = step * multi

로 고쳐쓸 수 있다.
별거 아닌것 같지만 step은 1~9 사이의 숫자이므로 step의 수열은 주기가 9 이하인 cycle을 형성하리라는 것을 알 수 있다. 정확하게는 주기가 1, 2, 3, 6 인 사이클이 생길 수 있다. (초기값을 1~9까지 변환해 가면서 구해보면 알 수 있다)

이제 K번의 이동후에 최종좌표를 구하는 일이 남았는데 K가 10^9 까지 주어지므로 단순히 계산해서는 시간이 너무 오래 걸린다. 여기에서 step이 사이클이 생기는 성질을 이용하자

보물을 찾아가는 이동은 북, 동, 남, 서를 번갈아 가면서 그때그때 step번 이동한다.
step의 사이클이 1인 경우 명확하게 북, 동, 남, 서를 돌면 제자리로 돌아온다.
step의 사이클이 2인 경우 마찬가지로 북, 동, 남, 서를 돌면 제자리로 돌아온다.
step의 사이클이 3인 경우 북, 동, 남, 서를 4회 돌면 제자리로 돌아온다
step의 사이클이 6인 경우 사이클이 3인 경우와 같다.

즉 어쨌던 사이클 주기 동안은 제자리에 머물로 있다는 계산이 나오고 이를 바탕으로 K를 팍팍 줄일 수 있게 된다.

말보다 코딩이 더 쉽다. 코딩 ㄱㄱㅆ
int dig(int a) { if (a < 10) return a; int res = 0; while (a > 0) { res += a % 10; a /= 10; } return dig(res); } string location(int K, int multi) { int i,j,k; int g = 1; vector<int> dd; int x = 0, y = 0; int dir = 0; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; bool loopfalg = true; while (loopfalg) { dd.push_back(g); x += dx[dir] * g; y += dy[dir] * g; dir = (dir+1)%4; K--; if (K == 0) break; g *= multi; g = dig(g); for (i = 0; i < dd.size(); i++) { if (dd[i] == g) { if (i != 0) { dd.erase(dd.begin(), dd.begin() + i); } loopfalg = false; break; } } } int loop = 4 * dd.size(); int rep = K % loop; for (i = 0; i < rep; i++) { int idx = i % dd.size(); int move = dd[idx]; x += dx[dir] * move; y += dy[dir] * move; dir = (dir+1)%4; } char buffer[100]; sprintf(buffer, "%d %d", x, y); return buffer; }

900 - P Sequence

이건 나중에 풀어봐야지