DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

사과 먹기

문제로 돌아가기

해설

먹는 순서를 100개 칸의 순열로 나타낸다. 칸 vvv의 사과를 먹기 전에, vvv와 거리가 2 이하인 다른 칸의 사과를 kvk_vkv​개 먹었다면 해당 사과에서 얻는 점수는 100⋅0.9kv100\cdot0.9^{k_v}100⋅0.9kv​이다. 따라서 평가 함수는 ∑v100⋅0.9kv\sum_v100\cdot0.9^{k_v}∑v​100⋅0.9kv​이다.

무작위 순열에서 시작하여 담금질을 수행할 수 있다. 두 위치를 교환하거나, 한 위치의 사과를 다른 위치로 옮겨 사이 구간을 밀어내는 이동을 사용한다. 점수가 증가하면 이동을 받아들이고, 감소량이 ddd이면 온도 TTT에 대해 확률 exp⁡(−d/T)\exp(-d/T)exp(−d/T)로 받아들인다. 온도를 점차 낮추고 여러 번 재시작하며, 탐색 도중 찾은 최고 점수의 순서를 따로 보관한다.

각 칸에는 거리가 2 이하인 다른 칸이 최대 12개 있다. 이웃 목록과 현재 순서에서의 위치를 저장하면, 순서 변경 때문에 선후관계가 바뀌는 이웃들의 kvk_vkv​만 갱신하여 점수 차이를 빠르게 구할 수 있다. 이동 연산 후 위치 배열을 갱신하는 데는 최대 O(100)O(100)O(100)이 필요하다. 전체 점수를 다시 계산하는 단순한 평가도 O(100⋅12)O(100\cdot12)O(100⋅12)에 가능하다.

담금질에는 AC 기준에 도달한다는 보장이 없다. 이 고정 격자에서는 실행 전에 충분히 탐색한 순서를 제출 프로그램에 저장해 출력해도 된다. 제공된 기준 풀이는 교환과 삽입 이동으로 탐색한 순서를 저장하며, 정확한 점수는 6391.44590319386391.44590319386391.4459031938이다. 따라서 6391.46391.46391.4점 이상으로 AC를 받으며, 기준 만점을 초과한 점수도 그대로 유지된다. 이 순서가 전역 최댓값이라고 주장하지는 않는다. 기준 풀이의 실행 시간은 출력 크기에 비례하고, 별도의 탐색을 실행하지 않는다.

나이브 풀이로 행 순서대로 먹으면 유효한 순열을 출력하지만 낮은 점수만 얻는다.

정확한 판정에는 정수 계산을 사용할 수 있다. 0≤kv≤120\le k_v\le120≤kv​≤12이므로 점수에 101210^{12}1012를 곱하면 각 항은 100⋅9k인 정수이다. 이 합을 상한 없이 계산하고, 로 나눈 비율을 체크러의 점수 배율로 반환한다. 서브태스크 배점이 점이므로 실제 점수 합계가 그대로 최종 점수가 되며, 점수 배율이 을 초과해도 유지된다. 최종 점수가 해결 기준인 점 이상이면 AC가 된다. 각 항은 최대 , 전체 합은 최대 이므로 부호 있는 64비트 정수로 안전하다.

Solution written by GPT6

v⋅1012−kv100\cdot9^{k_v}\cdot10^{12-k_v}
100⋅9kv​⋅1012−kv​
6391.46391.46391.4
6391.46391.46391.4
111
6391.46391.46391.4
101410^{14}1014
101610^{16}1016