Processing math: 100%
본문 바로가기

이진탐색

SCPC 2019 본선 5번 풀이. 정육면체 재구성 문제 설명(요약) 3차원 공간에 N개의 점 P1(x1,y1,z1), ⋯, PN(xN,yN,zN)이 주어져 있다. (정수좌표) 다음 조건을 만족하는 두 정육면체 Q, Q′을 생각하자. Q와 Q′의 중심은 서로 일치한다. 주어진 N개의 점은 Q의 내부 또는 경계에 있으며, 동시에 Q′의 외부 또는 경계에 있다. 즉, Q는 바깥쪽 정육면체이고 Q′은 안쪽 정육면체이다. Q와 Q′의 한 변 길이의 차이의 최솟값을 구하시오. 제약 조건: N≤15,000, −109≤xi,yi,zi≤109 실행 조건: 테스트 케이스 50개에 대한 실행시간 .. 더보기
SCPC 2017 본선 3번 풀이. Colony 문제 설명www.codeground.org 참조 부분문제 1 풀이만약 어떤 연도 Y에 캡슐이 도달 가능하다면, 캡슐은 Galaxy1이 어떤 연도 i에 건설한 Colony1[i]에서 출발하여 Galaxy2이 어떤 연도 j에 건설한 Colony2[j]에 도달했을 것이다. Colony1[i]에서 출발한 캡슐이 방문 가능한 지점은 택시거리가 Y-i 이하인 모든 지점이다. 따라서 Colony1[i]와 Colony2[j]의 택시거리가 Y-i 이하인지 확인하면 된다. 전체 시간복잡도는 O(N3)으로 N 더보기
SCPC 2016 본선 4번 풀이. 반물질 문제 설명www.codeground.org 참조 제약 조건: 1 더보기

티스토리툴바