hepheir   2년 전

출력 섹션의 아래의 내용 중 아래의 부분을 수정해야 할 것 같습니다.


수정 전:

각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

수정 후:

각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 이를 $10^9+7$로 나눈 나머지를 출력한다. (나머지를 출력하는 대상에 $S(A, x, y)$의 최댓값은 포함하지 않는다.)


근거:

문제의 예제출력1 은 다음과 같습니다.

2100 1
42 2
40 4
500 48
2799999944 1
91 227020758

이 중에서, 5번째 케이스에 해당하는 2,799,999,944 는 문제에서 제시하는 109+7 보다 큰 수로, 모듈로 연산을 적용하지 않은 경우에 해당합니다.

(1) 문제의 조건에 S의 최댓값은 나머지를 적용하지 않는다는 부연 설명을 추가하거나, 혹은 예제 출력이 잘못된 것이라면, (2) 예제출력1의 5번째 케이스의 답을 수정해야 할 것 같다는 의견입니다.

아래 첨부한 코드는 최악의 케이스에서 S의 값을 naive하게 계산한 것을 보입니다. 부동소수점 표현에서 근소한 오차가 발생했을 수 있으나, 499,896,666,441,675,008 으로 상당히 큰 수가 나옴을 알 수 있으며, 따라서 S의 값에도 나머지 연산을 적용하고 예제출력을 수정하는게 좋을 것 같아보인다는 의견입니다.

import numpy

MAX_A = int(1e8)
MAX_N = 50000
MAX_M = 200000

# A를 가장 큰, 고유한 값의 목록으로 이루어진 배열로 세팅
A = numpy.linspace(MAX_A-MAX_N, MAX_A, num=MAX_N, endpoint=False)

# x <= y 를 만족하는 서로다른 (x,y) 쌍
cnt = 0
for y in range(MAX_N-1, MAX_N-5, -1):
    for x in range(y, -1, -1):
        cnt += 1
print(cnt, '개의 ranges')


F = numpy.zeros(MAX_N)
base = numpy.ones(MAX_N)

for y in range(MAX_N-1, MAX_N-5, -1):
    for x in range(y, -1, -1):
        F[x:y+1] += 1

F.sort()
A.sort()

S = 0
for f, a in zip(F, A):
    S += f * a

print(int(A.dot(F))) # 499896666441675008

yup0927   2년 전

출력부에서 S(A, x, y)의 최댓값과 / 방법의 수를 출력하되, 방법의 수는 커질 수 있으니 나머지를 출력한다고 되어 있기 때문에 S(A, x, y)는 나누지 않는 것이 맞지 않나요?

hepheir   2년 전

네.. 아무래도 그 부분이 가장 애매한 것 같습니다. 그러면 이 문제는 BigInteger 분류에도 해당하게 되는 걸까요?

yup0927   2년 전

지문에서 '값이 커질 수 있으니 나머지를 출력하라'는 부분이 수식하는 게 방법의 수에만 한정되어 있기 때문에 서술에는 문제가 없다고 생각합니다.

추가로 제시해주신 값은 64비트 정수 안에 들어와서 빅인티져가 필요해보이지는 않습니다.

hepheir   2년 전

앗.. 제가 2^64의 범위를 혼동해서 생긴 문제 같습니다. 말씀해주신대로 빅인티져가 필요한 문제가 아니었네요.

글은 해결 됨으로 바꾸어 두겠습니다.

답변 감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.