AtCoder Beginner Contest 457 参加記録と解答例 (A D問題)

Context

대규모 수열 데이터 처리 시 발생하는 인덱스 계산 오버헤드와 시간 복잡도 제약 해결이 필요함. 특히 K값이 $10^{18}$에 달하는 극한의 제약 사항으로 인해 단순 반복문이나 Priority Queue 기반 접근은 TLE(Time Limit Exceeded)를 유발함.

Technical Solution

• 0-indexed 변환을 통한 인덱스 계산 단순화 및 경계값 조건 분기 제거
• modulo 연산을 이용해 거대 수열의 반복 구조 내 특정 위치를 상수로 산출하는 로직 설계
• 최솟값의 최대화 문제 정의에 따른 Binary Search 기반의 최적해 탐색 전략 채택
• 목표값 달성 가능 여부를 판별하는 check 함수를 통해 O(N)의 시간으로 검증 수행
• $10^{20}$ 범위의 Search Space 설정을 통한 정수 오버플로우 및 범위 부족 문제 해결
• 각 요소별 필요 연산 횟수를 몫과 나머지를 이용한 수식으로 계산하여 루프 횟수 최소화