원문 : http://hongjun7.tistory.com/16...

이번 마라톤 매치에는 50등 이내의 참가자들에게 티셔츠를 주는 이벤트가 있었습니다.

문제는 상당히 단순합니다. H*W 크기의 격자 판이 있습니다. 각 격자 칸에는 0 ~ C-1의 숫자가 있습니다. 여러분은 숫자가 같은 두 격자 칸을 선택해서 없앨 수 있는데, 추가적인 조건으로 두 격자 칸을 대각 꼭짓점으로 하는 직사각형 내에 다른 숫자의 격자칸이 있으면 안됩니다. 삭제된 칸은 숫자가 쓰여 있지 않다고 가정합니다. 가능하면 많은 수의 격자 칸을 없애야하는 것이 본 문제의 목표입니다.

문제 본문은 다음 링크( MM 100 Problem Statement )에서 보실 수 있습니다.
대회 결과는 다음 링크( MM 100 Standings )에서 보실 수 있습니다.

제가 작성한 프로그램이 시뮬레이션 되는 영상은 블로그 글을 참고해주세요! :)

저는 아래와 같은 방법을 사용했습니다.

1. 이분 매칭을 통해 인접하면서 같은 숫자가 적힌 격자 칸은 모두 없앤다.
2. 조그마한 직사각 영역을 지정하여, 해당 영역 내에서 없앨 수 있는 격자 칸들을 없앱니다.
숫자가 적혀진 격자 칸을 랜덤하게 선택하여, 짝이 될 수 있는 격자 칸 중 가장 가까운 것을 선택합니다.
3. 남은 전체 영역에 대해 없앨 수 있는 격자 칸들을 모두 없애봅니다.
이 때에도 2번 단계와 동일한 방식으로 수행합니다.

2번 단계에서 후보군을 몇 개 선택한 후, 그 후보군에 대해서 3번 작업을 최대한 많이 수행해보다가 가장 좋은 답을 출력하는 식으로 프로그램을 작성했습니다. 10초의 시간제한은 2번 단계에서 3초 정도 수행하고, 3번 단계에서 6.5초 정도 수행하도록 배정하였습니다.

없애고자 하는 두 격자 칸을 대각 꼭짓점으로 하는 직사각형 내에 다른 숫자의 격자칸이 있는지는 2차원 fenwick tree를 이용하여, 해당 직사각 영역 내에 삭제된 격자 칸의 개수를 세아려 그 값이 (넓이 - 2)인지 확인하는 방식을 사용했습니다. 가장 가까운 것끼리 짝 지어주는 전략을 사용했기 때문에 해당 영역 내에 같은 숫자가 적힌 격자 칸이라도 존재해서는 안되기 때문입니다.

대회가 끝난 후, ainu7님이 O(4*logn*logm)의 2차원 fenwick tree보다는 O(루트(nm))의 sqrt decomposition이 더 빠를 수 있다는 조언을 해주셨습니다. 실제로 구현해보니 2배 가량 속도가 더 빠른 것을 확인하였습니다ㅠㅠ

1000개의 랜덤 데이터에 대해, 로컬에서 테스트한 결과 평균적으로 98.5%의 격자 칸들을 없애는 것을 확인하였습니다.
고정된 Seed값으로 생성된 100개의 데이터로 채점하는 Provisional Score 상으로는 상위 40% 정도에 위치하는데, 글을 포스팅하는 이 시점까지 최종 System Test 결과가 나오지 않았습니다. 최종 System Test는 랜덤 Seed값으로 생성된 2000개의 데이터로 채점한다고 합니다.