TopCoder Marathon Match 100 후기

이번 마라톤 매치에는 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개의 데이터로 채점한다고 합니다.