@shiftpsh

IOI에 출제되었던 문제 중 하나인데, 이 문제가 무엇을, "어떤 알고리즘 및 해법을" 의도하고 출제한 문제인지 도저히 이해하지 못하겠습니다.

문제에 나온 그림들과 예제 첨부파일로 주어진 그림 집합들을 살펴보면, 4번이 가장 색이 통일되어 있고, 3번이 색 불규칙성이 가장 심하며, 1/2번이 그 중간인데 1번이 조금 더 색 통일도가 높습니다.

저는 이점을 활용해서 그림의 인접한 두 픽셀의 색 변화를 계산하여, 전체 경계 중 색이 변하는 경계의 비율을 계산하여 이 비율이 속하는 범위에 따라 그림을 분류하는 방식으로 10여 차례의 시행착오 끝에 일단 정확도 90% 이상(성공 기준입니다)를 받긴 했습니다.

그러나 문제에서 각 4가지 그림별로 어떤 그림인지 명백한 정의를 내리지 않았습니다. 이 세상에 인상주의, 표현주의 등 문제에서 소개한 작품들만 수천점이 넘어갈텐데, 그 모든 그림들이 특정한 잣대로 구분이 가능한 건지도 모르겠습니다. 랜덤을 써도 이 문제를 정확도 100%로 수렴하게 하는 방법이 존재하지 않습니다.

이는 "해결가능성"(문제에 주어진 조건만으로 첫 시도의 정답률을 99.99% 이상으로 만들기)에 명백히 위배되는 상황인 것 같습니다.

혹시 이 문제에 대하여 정확도 100%를 보장하는 풀이가 존재하나요? 만일 그런 풀이가 존재하지 않는다면 테스트 케이스를 한 수천개 정도를 만들어 비교하거나, 본 문제를 번외 및 solved.ac 기준 unrated 처리하는 것이 맞는 것 같습니다.(작품을 한 1000개 정도는 찾아서 더 추가해야 할 것 같습니다.)

인터넷에도 본 문제의 공식 풀이가 보이지 않아서 질문드립니다...