여전히 한국분들은 참가를 안하시고.. 저 혼자 외로이 -_-; 마무리하였습니다.

문제는 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초가 경과하였으면 대~충 칠한다.

자~ 이제 시간 문제를 해결하였으니.. 문제의 핵심인 점수 구하는 방법을 다듬을 차례입니다.
학생때 배운 확률 기억을 더듬어서 어찌어찌 공식을 만들어 보니.. 다음과 같은 공식이 나옵니다.
 



아래 공식으로 돌렸는데 점수가 생각보다 좋게 나오지 않았습니다.
일단 적당히 도박을 해줘야 하는데.. 너무 확률을 계산한 나머지 안전빵으로만 계산하는 것이 눈에 보입니다.

여러가지 바꿔가면서 테스트를해 봤는데.. 마지막으로 결정한 공식은...
 

역시 단순한게 최고라는 생각입니다.

이 때가 점수 178점 등수는 50위 바깥이었습니다.
문제에는 나와 있지 않았지만, forum 에 기발한 아이디어를 쓰는 사람들이 있습니다. forum을 기웃기웃하다보니 다음과 같은 글이 있더군요.

원문보기 -> Some questions
 c) I'm not sure if I had stated it properly, what I meant is if this valid? 

...A**A...
...****...
B********B
**********
B********B
...****...
...A**A...

d) idem with this case

A**A...
****...
**B***B
*******
**B***B
****...
A**A...


In both cases the A rectangle was there before the B rectangle.

이 질문에 대해서 주최측은 Yes, you can. 이라는 답을 남겼습니다.

따라서... 소스를 수정했습니다. ㅎㅎ (주워먹기 -_-;)

    1) 네모칸..  -> 아직 색칠되지 않은 칸..

이 기능 적용하고 버그와의 싸움을 대충 마치고.. 역시 마감 56초 전에 아슬아슬하게 SUBMIT..

provisional rank 10등.. 1주일간의 system test 후에 나온 final score 7등..

8등이었던 최고 등수를 갱신. rating 1710으로 상승.. ^^

기분좋게 마감한 대회입니다.

다음 MM에는 많은 분들의 참석 기다립니다..



이 게시물을..