pangitwise   2년 전

정해인 O(NlogN+NS)가 N = 100000, S = 5000일 때 최대 5억이므로, 주어진 시간 제한과 문제 조건상 풀이자의 입장에서 정해가 돌 수 있을 것이라는 보장을 가지기가 어렵습니다. 원본 서브테스크 6번 데이터를 검사한 결과 ∑c ≤ 5×107이라는 것을 확인하였으므로, 서브테스크 6번 제한에 대한 설명을 다음과 같이 바꾸어 주세요.


No further constraints.  

→ ∑c ≤ 5×107

or

→ It is guaranteed that the sum of all c is less than or equal to 5×107.



doju   2년 전

해당 조건이 크게 의미 있어 보이지는 않습니다. 배열을 매번 정렬된 상태로 유지하면서 시뮬레이션하는 것이 정해로 보이는데, 가장 machine이 많은 data center 하나에서 아주 많은 machine을 사용할 경우 c = 1이지만 배열 전체를 움직여야 합니다.

덧붙여 정해가 통과되는 것은 데이터가 약하기 때문이 아니라, 컴퓨터가 실제로 그 정도로 빠르기 때문입니다. 출제자가 이를 이용하는 것은 상당히 조심스러운 영역이고 문제를 푸는 사람에게도 유쾌하지 않은 경험을 줄 수 있지만, 어쨌든 문제를 푸는 입장에서 이를 받아들이고 컴퓨터가 좋아할 것 같은 프로그램을 의식하는 것은 앞으로 유용할 것입니다.

pangitwise   2년 전

 로컬에서 처음 시간 측정할 때 무엇 때문인지 임의 테스트케이스와 차이가 극단적으로 나와서 제가 잠시 착각을 했습니다. 다시 돌려보니 차이가 두 세 배 안팎으로 그렇게 크진 않네요.

말씀대로 c 조건이 큰 의미가 없는 것이 맞습니다.


 원래 C++에 익숙한 것도 아니고, 돌릴 때마다 시간 오차가 너무 크게 나와서 테스트케이스가 보강될 때 어디까지 터질 수 있을지 감이 안 잡히네요.

doju   2년 전

c가 실행 시간에 영향을 줄 수는 있지만 정해를 따른다면 그로 인한 차이는 커 봐야 두 배 이하일 것으로 예상하며, 실제로 공식 풀이를 사용해 실험했을 때도 거의 예상대로의 결과(약 440ms → 약 780ms)가 나왔습니다.
따라서 더 강한 데이터가 추가되더라도 지금 제출된 풀이들이 시간 초과까지는 받지 않을 거라고 생각하는데, 데이터 하나를 참고용으로 남겨 둡니다.

pangitwise   2년 전

시간 오차는 컴퓨터 성능 문제였나 봅니다... 다른 컴퓨터에서 돌려보고 계측대로임을 확인했습니다.

참고가 되었습니다. 감사합니다.

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