https://www.acmicpc.net/problem/17071
#17071: 숨바꼭질 5
수빈은 남동생과 숨바꼭질을 하고 있다.
수빈은 현재 포인트 N(0 ≤ N ≤ 500,000)에 있고 남동생은 포인트 K(0 ≤ K ≤ 500,000)에 있다.
수빈은 걷거나 텔레포트할 수 있다.
수빈의 위치가 X라면
www.acmicpc.net
문제에서 -1, +1, *2,
*2의 경우는 제쳐두고 +-1만 생각하면
t초에 위치 X에 있었다면 여전히 t+2n초에 위치 X로 이동할 수 있습니다.
*2가 있어서 헷갈리지만 *2가 있다고 해서 위의 문장이 틀린 것은 아닙니다.
*2의 추가 규칙은 없습니다.
따라서 일반 BFS와 달리
“t초에 X 위치에 있었다면 t+2n초에 X 위치로 이동할 수 있습니다.
” 그것을 사용해야합니다
애초에 BFS를 사용하는 이유는 이 문제에서 더 많이 움직일수록 목표에 더 가까워지기 때문입니다.
목표는 중복을 제거하는 것입니다.
문제는 내 위치에서 중복 항목을 제거할 수 없다는 것입니다.
(답변은 내 위치가 아닌 누나 위치 영향을 받기 때문에)
물론 중복을 제거하지 않으면 시간이 초과됩니다.
그래서 아이디어가 번뜩이는 중복 사례를 찾는 게 관건이다.
사례는 “t초에 위치 X에 있었다면 여전히 t+2n초에 위치 X로 이동할 수 있습니다.
”입니다.
규칙에서 나온다
그러나 아이디어를 내기가 어렵다.
어떻게든 문제에 접근할 방법을 고민하고 있다면
3^(무한) 경우의 수 -> 중복 제거 필수 -> 위치만으로는 중복 제거 불가 -> 어떻게?
생각해보면.. 그에게 다가갈 수 있을지도 몰라
근데 그걸 깨달아도 해결하기가 좀 어려워
주의해야 할 몇 가지 사항이 있습니다.
이 예에서 내가 17 -> 16 -> 15 -> 14 -> 15를 움직이면 4초 안에 동생을 칠 수 있습니다(다른 움직임도 가능).
보면 2초에 15, 4초에 15가 들립니다.
그래서 2초에 15에서 멈췄으니 2초 + 2 * 1초인 4초에 안듣는게 맞다.
그렇게 하면 답장을 할 수 없습니다.
먼저, 원칙적으로 “t초 안에 X의 위치에 있었다면 t+2n초 안에 X의 위치로 갈 수 있다”,
t초 내에 X로 이동하면 t+2n초 내에 이동하면 안 됩니다.
그것은 단지 최적화 일 뿐이며 문제를 해결할 생각조차하지 않았습니다.
아래와 같이 방문이 완료되면
내 현재 위치와 내 동생의 위치가 같은지 확인만 하는 것이 아니라 형제여
내가 이전에 기록했던 방문에서,
형님도 오셨는지 확인이 필요한데, 이 룰에서 찾을 수 있는 핵심 부분입니다.
내 위치가 줄어들고 늘어날 수 있지만 중복될 수 있음
형의 지위는 올라갈 뿐 중복은 절대 없기 때문에
이 문제는 내 입장보다 동생 입장에서 생각하기가 더 쉽다.
그래도
while (!
q.empty()) {
int cur = q.front().first;
int cnt = q.front().second;
q.pop();
int brother = K + (cnt * (cnt + 1) / 2);
if (cur == brother) return cnt;
if (cnt & 1 && hol_visit(brother)) return cnt;
if (!
(cnt & 1) && jjak_visit(brother)) return cnt;
...
}위와 같이 cur==brother가 아래에 있는지 확인하십시오.
내가 전에 왔는지 확인하기 위해 동생의 행방을 확인하는 것이 절대적으로 필요합니다.
그 외에도 고려해야 할 두 가지 다른 사항이 있습니다.
처음에는
while (!
q.empty()) {
int cur = q.front().first;
int cnt = q.front().second;
q.pop();
int brother = K + (cnt * (cnt + 1) / 2);
if (brother > 500000) return -1;//이거 조심
//50만 넘어서도 만나는걸 체크함..
if (cur == brother) {
return cnt;
}
if (cnt & 1 && hol_visit(brother)) return cnt;
if (!
(cnt & 1) && jjak_visit(brother)) return cnt;
...
}Brother가 500,000건이 넘는 사건을 처리하지 않으면
Cur 자신은 500,000을 넘지 못하기 때문에
if(cur==형제) return cnt; 지속되지는 않지만
아래 두 개의 return 문에 갇힌 것 같습니다(방문이 500,000까지만 0으로 초기화되었기 때문입니다).
그리고 첫째, 형제가 500,000을 초과하는지 볼 필요가 없습니다 (형제는 성장할뿐입니다)
또한 최적화를 위해 -1을 반환합니다.
하기 좋은
두 번째는
while (!
q.empty()) {
...
int nxt = cur * 2;//next니까 홀수일때 짝수 visit 체크해주는거 조심
if (nxt <= 500000 && (cnt & 1 ? !
jjak_visit(nxt) : !
hol_visit(nxt))) {
cnt & 1 ? jjak_visit(nxt) = true : hol_visit(nxt) = true;
q.push({ nxt , cnt + 1 });
}
nxt = cur + 1;
if (nxt <= 500000 && (cnt & 1 ? !
jjak_visit(nxt) : !
hol_visit(nxt))) {
cnt & 1 ? jjak_visit(nxt) = true : hol_visit(nxt) = true;
q.push({ nxt , cnt + 1 });
}
nxt = cur - 1;
if (nxt >= 0 && (cnt & 1 ? !
jjak_visit(nxt) : !
hol_visit(nxt))) {
cnt & 1 ? jjak_visit(nxt) = true : hol_visit(nxt) = true;
q.push({ nxt , cnt + 1 });
}
}즉, cnt가 홀수이면 hol_visit를 확인하지 않습니다.
방문을 확인하는 것은 cnt + 1 상태에 있는 다음을 확인하는 것입니다.
cnt가 홀수이면 짝수 방문으로 확인 / cnt가 짝수이면 홀수 방문으로 확인
당신은 할 수 있습니다
조심해야 할 것들
모든 것이 반례로 여기에 있습니다.
https://www.acmicpc.net/board/view/99122
기사 읽기 – 최적화 정크 반례 던지기
댓글을 달려면 로그인이 필요합니다.
www.acmicpc.net
제목이 너무 아프다~
제 기억으로는 500,000이 넘는 형제를 확인하지 않으면 첫 번째 경우에 문제가 있었던 것 같습니다.
두 번째 짝과 헷갈린다면 후자의 경우 문제가 발생한 것으로 보인다.
전체 코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N, K;
bool hol_visit(500001);
bool jjak_visit(500001);
int bfs() {
queue<pair<int, int>> q;
q.push({ N, 0 });
jjak_visit(N) = true;
while (!
q.empty()) {
int cur = q.front().first;
int cnt = q.front().second;
q.pop();
int brother = K + (cnt * (cnt + 1) / 2);
if (brother > 500000) return -1;//이거 조심
//50만 넘어서도 만나는걸 체크함..
if (cur == brother) {
return cnt;
}
//이것도 조심 ( 핵심임 )
if (cnt & 1 && hol_visit(brother)) return cnt;
if (!
(cnt & 1) && jjak_visit(brother)) return cnt;
int nxt = cur * 2;//next니까 홀수일때 짝수 visit 체크해주는거 조심
if (nxt <= 500000 && (cnt & 1 ? !
jjak_visit(nxt) : !
hol_visit(nxt))) {
cnt & 1 ? jjak_visit(nxt) = true : hol_visit(nxt) = true;
q.push({ nxt , cnt + 1 });
}
nxt = cur + 1;
if (nxt <= 500000 && (cnt & 1 ? !
jjak_visit(nxt) : !
hol_visit(nxt))) {
cnt & 1 ? jjak_visit(nxt) = true : hol_visit(nxt) = true;
q.push({ nxt , cnt + 1 });
}
nxt = cur - 1;
if (nxt >= 0 && (cnt & 1 ? !
jjak_visit(nxt) : !
hol_visit(nxt))) {
cnt & 1 ? jjak_visit(nxt) = true : hol_visit(nxt) = true;
q.push({ nxt , cnt + 1 });
}
}
return -1;
}
int main() {
scanf("%d%d", &N, &K);
printf("%d", bfs());
}