먹는 순서를 100개 칸의 순열로 나타낸다. 칸 의 사과를 먹기 전에, 와 거리가 2 이하인 다른 칸의 사과를 개 먹었다면 해당 사과에서 얻는 점수는 이다. 따라서 평가 함수는 이다.
무작위 순열에서 시작하여 담금질을 수행할 수 있다. 두 위치를 교환하거나, 한 위치의 사과를 다른 위치로 옮겨 사이 구간을 밀어내는 이동을 사용한다. 점수가 증가하면 이동을 받아들이고, 감소량이 이면 온도 에 대해 확률 로 받아들인다. 온도를 점차 낮추고 여러 번 재시작하며, 탐색 도중 찾은 최고 점수의 순서를 따로 보관한다.
각 칸에는 거리가 2 이하인 다른 칸이 최대 12개 있다. 이웃 목록과 현재 순서에서의 위치를 저장하면, 순서 변경 때문에 선후관계가 바뀌는 이웃들의 만 갱신하여 점수 차이를 빠르게 구할 수 있다. 이동 연산 후 위치 배열을 갱신하는 데는 최대 이 필요하다. 전체 점수를 다시 계산하는 단순한 평가도 에 가능하다.
담금질에는 AC 기준에 도달한다는 보장이 없다. 이 고정 격자에서는 실행 전에 충분히 탐색한 순서를 제출 프로그램에 저장해 출력해도 된다. 제공된 기준 풀이는 교환과 삽입 이동으로 탐색한 순서를 저장하며, 정확한 점수는 이다. 따라서 점 이상으로 AC를 받으며, 기준 만점을 초과한 점수도 그대로 유지된다. 이 순서가 전역 최댓값이라고 주장하지는 않는다. 기준 풀이의 실행 시간은 출력 크기에 비례하고, 별도의 탐색을 실행하지 않는다.
나이브 풀이로 행 순서대로 먹으면 유효한 순열을 출력하지만 낮은 점수만 얻는다.
정확한 판정에는 정수 계산을 사용할 수 있다. 이므로 점수에 를 곱하면 각 항은 인 정수이다. 이 합을 상한 없이 계산하고, 로 나눈 비율을 체크러의 점수 배율로 반환한다. 서브태스크 배점이 점이므로 실제 점수 합계가 그대로 최종 점수가 되며, 점수 배율이 을 초과해도 유지된다. 최종 점수가 해결 기준인 점 이상이면 AC가 된다. 각 항은 최대 , 전체 합은 최대 이므로 부호 있는 64비트 정수로 안전하다.
Solution written by GPT6