각 테스트 케이스의 정답인 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
hepheir 2년 전
출력 섹션의 아래의 내용 중 아래의 부분을 수정해야 할 것 같습니다.
수정 전:
각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.
수정 후:
각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 이를 $10^9+7$로 나눈 나머지를 출력한다. (나머지를 출력하는 대상에 $S(A, x, y)$의 최댓값은 포함하지 않는다.)
근거:
문제의 예제출력1 은 다음과 같습니다.
이 중에서, 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