8개의 댓글이 있습니다.
-
-
hyunhwan -
http://forums.topcoder.com/?module=Thread&threadID=507280&start=0&mc=9#511784
위의 스레드를 한번 참고해보심이 어떨련지요 보니깐 clock()의 경우 문제가 있는듯 하더라고요.
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
하나반
여전히 한국분들은 참가를 안하시고.. 저 혼자 외로이 -_-; 마무리하였습니다.
문제는 AreaFiller.
간략히 소개를 하면 바둑판 같이 생긴 네모판(가로세로크기 20~100)이 있다. 여기에 당신은 한번에 한칸을 색칠할수 있다. 그리고, 컴퓨터가 랜덤하게 2칸을 랜덤한 색깔로 색칠한다.
네 귀퉁이가 같은 색깔이고 안쪽에 다른 색깔이 없는 사각형을 만들면그 사각형의 빈칸의 갯수만큼이 점수이다.
일단 문제는 매우 단순합니다.
구현방법또한 거의 모두가 비슷하였을거라고 생각됩니다.
제가 구현한 방법은..
1) 네모판의 빈칸에 모든 색깔을 대입해보고 그릴수 있는 사각형의 크기를 계산하여 각 칸과 색깔에 따른 점수를 구한다.
2) 계산된 점수가 가장 큰 점을 칠한다.
3) 네모판을다 칠할 때가지 1~2)를 반복한다.
위 알고리즘의 문제는 최대값(크기 100x100, 10가지 색깔)으로 실행하면 제한시간 30초 -_-; 를 매번 초과하였습니다.
그래서 2차 수정.
1) 네모판의 빈칸에 모든 색깔을 대입해보고 그릴수 있는 사각형의 크기를 계산하여 각 칸과 색깔에 따른 점수를 구한다.
2) 계산된 점수가 가장 큰 점을 칠한다.
2-1) 이 때 계산된 사각형을 기억한다.
2-2) 다음기회에 이 사각형이 아직도 유효하면(컴퓨터가 내부에 다른 색깔의 점을 찍지 않았으면) 비어있는 모서리를 칠한다.
3) 네모판을다 칠할 때가지 1~2)를 반복한다.
최대값으로 다시 테스트 해보았는데.. 30초가 아슬아슬합니다.
그래서, 최후의 수단을 사용하였습니다.
0) 시간을 계산해서 29초가 경과하였으면 대~충 칠한다.
자~ 이제 시간 문제를 해결하였으니.. 문제의 핵심인 점수 구하는 방법을 다듬을 차례입니다.
학생때 배운 확률 기억을 더듬어서 어찌어찌 공식을 만들어 보니.. 다음과 같은 공식이 나옵니다.
[spoiler="더 보기..."] ~~~ c
// p - 확률
// in - 만들려고 하는 네모의 안쪽에 비어있는 칸의 수
// corner - 비어잇는 모서리의 개수
// C - 칠할 수 있는 색깔의 개수
// space - 전체 네모판에서 비어있는 칸의 수
p = in;
switch ((int) corner) {
case 1 :
break;
case 2 :
p *= (1 + 2 * (space - in) * (C - 1) / space + SQR((space - in) * (C - 1) / space) ) / C / C;
break;
case 3 :
p *= (1 + 4 * (space - in) * (C - 1) / space + 6 * SQR((space - in) * (C - 1) / space) + 4 * SQR3((space - in) * (C - 1) / space) + SQR4((space - in) * (C - 1) / space)) / C / C / C / C;
break;
}
17년 전