Google Foobar, 최대 한 번의 고유 한 방문수, 그래프의 음수 가중치

Question

문제의 유형을 파악하는 데 문제가 있습니다. 저는 아직 학생이고 그래프 이론/선형 최적화 클래스를 아직 사용하지 않았습니다.

내가 알고있는 유일한 사실은 음수 사이클을 확인하는 것입니다. 이는 리소스 제한을 무한대로 늘릴 수 있음을 의미하므로 각 토끼를 선택할 수 있습니다. 나는 다음 경로를 선택하는 "이유"를 모른다. 또한 모든 종료점을 계속 사용하면서 리소스 제한을 영원히 0 이하로 떨어 뜨릴 수는 있지만 종료하지 말아야 할 시점을 알 수 없습니다.

저는 코드를 찾고 있지 않습니다 (코딩상의 문제이므로) 이것은 문제의 유형 (예 : 최대 흐름, 최장 경로, 최단 경로 등)입니다.이 알고리즘에 부합하면 이미 굉장한 것이 될 것입니다. 감사.

시작 지점에서 모든 토끼와 칸막이로 이동하는 데 걸리는 시간은 정사각형의 정수로 주어집니다. 각 행은 시작, 첫 번째 토끼, 두 번째 토끼, ..., 마지막 토끼 및 그 순서로 격납하는 데 걸리는 시간을 알려줍니다. 행의 순서는 동일한 패턴 (시작, 각 토끼, 칸막이)을 따릅니다. 토끼는 당신의 팔에 뛰어들 수 있습니다. 그래서 그것들을 집어내는 것은 즉각적이며, 물개와 동시에 격벽에 도착하는 것은 여전히 ​​극적인 경우 탈출에 성공할 수 있습니다. (당신이 데리러 가지 않은 토끼는 더 이상 당신이 데려온 토끼를 가지고 다닐 필요가 없기 때문에 당신과 함께 탈출 할 수 있습니다.) 원하는 경우 다른 지점을 다시 방문 할 수 있으며, 칸막이로 이사하십시오 즉시 떠나야한다는 의미는 아닙니다. 시간이 허락된다면 추가로 토끼를 데리러 갈 수 있습니다.

토끼 간 이동 시간 외에도 일부 경로는 우주 정거장의 보안 검사 점과 상호 작용하고 시간을 다시 시계에 추가합니다. 시계에 시간을 추가하면 칸막이 문이 닫히는 시간이 지연되고, 문이 이미 닫힌 후에 시간이 0 또는 양수로 되돌아 가면 벌크 헤드가 다시 열립니다. 따라서 원을 그리며 시간을 확보 할 수 있습니다. 즉, 경로를 통과 할 때마다 동일한 시간이 사용되거나 추가됩니다.

문을 닫기 전에 벌크 헤드를 벗어나면서 도망 갈 수있는 토끼와 토끼를 계산할 수있는 answer (times, time_limit) 형식의 함수를 작성하십시오. 같은 크기의 토끼가 여러 세트 인 경우 가장 낮은 수감자 ID (색인)를 가진 토끼 세트를 정렬 된 순서로 반환하십시오. 토끼가 많아야 5 개 토끼 거기 제 토끼가 0 인 상태, 포로 ID별로 정렬 된 목록으로 표시하고, TIME_LIMIT 많아야 999

Answer 1

그것은 planning problem이다 인 음이 아닌 정수이고되고 원래. 계획에 대한 일반적인 접근법은 세계의 가능한 상태, 초기 상태, 상태 간 전환 및 최종 상태를 식별하는 것입니다. 그런 다음이 데이터가 의미하는 그래프를 폭 - 우선 검색을 사용하여 가장 간단하게 검색하십시오.

이 문제의 관련 상태는 (1) 어느 정도의 시간이 남았는가 (2) 어느 토끼를 선택했는지 (3) 현재 상황입니다. 이것은 1,000 클럭 설정 (1 분 안에 추가 된 시간에 대해 말합니다)을 의미합니다. 2^5 = 32 하위 집합의 7 번 위치 = 224,000 개의 가능한 상태는 사람이 아니지만 컴퓨터는 많이 필요합니다.

Johnson's algorithm에서 트릭을 스 와이프하여 추가 시간을 처리 할 수 ​​있습니다. Tymur는 Bellman - Ford를 실행하여 부정적인주기 (부정적인주기를 충분히 돌아서 처음 실행하는 것으로 모든 토끼를 구할 수 있음) 또는 적용될 때 모든 시간을 음수가 아닌 잠재 성을 찾는 의견을 제시합니다. 시작 위치와 격벽 사이의 전위차로 시작 시간을 조정하는 것을 잊지 마십시오.