868B : Race Against Time

868B Race Against Time

난이도 : 5/10

구현이지만 까다로운 문제이다. 원을 이용해 문제를 푸는건 익숙치 않다. 차라리 backtracking, dp, BFS 등 등 알고리즘 문제가 더 쉬울정도. 컨테스트에서는 풀지 못하였다. 아마도 블라인드 입사문제 (카카오)의 구현 급 난이도였다.

문제보기

http://codeforces.com/contest/868/problem/B

Race against time 이란 뜻은 굉장히 짧은 시간내에 무언가를 해내려고 한다는 뜻이다. 일분 일초를 앞다퉈... 라는 것과 비슷한 뜻

어쨌든 각설하고...

문제의 주인공이 misha는 space-time paradox라는 상황에 처해있는데, 이는 시공간이 서로 대체되는 특수한 상황이다. 이 상황속에서 misha는 경진대회 문제를 준비해야하는데 t1에서 시작해서 t2까지는 끝내야한다. 무사히 끝낼 수 있는 조건은 다음과같다.

현재 시간 h, m, s 가 주어지는데, 시계에서 t1시 와 t2시 사이에 현재 시간 h, m, s의 바늘침이 둘 사이를 가로막고 있으면안된다.

특이한 문제다.  

Input

다섯 정수 h, m, s, t1, t2가 주어진다.

Output

Misha 가 무사히 마칠수 있으면 YES 그렇지않으면 NO를 출력하라.

첫 째 예제는 t1 에서 t2까지 경로 사이에 바늘침이 모두 가로막고 있기 때문에 안된다.
둘 째 예제에서는 12 ~> 1 시까지 반시계방향으로 접근 가능하기 때문에 된다.
셋 째 예제에서는 명확하게 될수있다.

문제 해설

쉬운 문제일거같지만 다시 생각해보자. 두 번째 예제는 왜 되는걸까? 단 1초차이 때문에 약간의 h 침과 m침이 비켜났기 때문에 YES인 것이다. 진짜 그런가? 여기서 어렵다고 생각했다. 이 부분에서 문제가 왠지 모호하다는 느낌을 받앗다. 12 0 0 12 1이면 답은 어떨것인가? YES or NO?

그럼 다음과 같은 질문은? 3 1 13 12 3? YES or NO? (물론 12 0 1 12 1 이 YES 이므로 이건 NO가 되어야한다.)

여전히 구현상 질문을 머릿속에 남겨두고 나의 접근법은 아래와 같았다.

360 크기의 chk 배열을 만들고 바늘침이 가르키는 곳을 1로 만든다. 그다음 t1 지점에서 t2 까지의 or 연산을 주르륵 해서 해당 chk[t2] 가 0이면 갈수 잇음이다.

그러나 or 문제의 연산은 다음과 같다.

12 0 1 이고 12 1 일 때  chk[0], chk[0], chk[6] 이 1이다. (360도의 값을 보정해주기 위해 h는 30배, m과 s는 6배해준다. )

그렇담 답은 NO가 나온다. 하지만 문제 조건에서 해당 상태는 정답이 YES 가 나와야한다. 큰 차이점은 경계점 문제이다.

일단 배열의 문제를 서술한다.

1 배열을 쓴다고하면 -> 시계방향 또는 <- 반시계 방향 체크하기가 까다롭다.
2 미세한 경계점으로 인해 배열의 크기가 커진다. 

예로 12 0 1 를 표현하기위해 필요한 chk 배열의 사이즈를 생각해보라. 크기를 360으로 잡았을 때 12시를 표현하는 각도는 0도이다. (12*30%360==0) 그렇지만 0분 1초를 표현하려면 12 h는 0도가 아닌 미세한 각도로 움직여야한다. 그렇다면 chk배열의 360은 얼마만큼 커져야하는가?

아래와 같이 문제를 다음과 같이 간소화한다.

1 입력받는다.

2 출발지점이 크면 도착지점과 바꾼다.

3 h 가 출발지점과 도착지점 사이이면 ans ++;

4 m 가 출발지점과 도착지점 사이이면 ans++;

5 s 가 출발지점과 도착지점 사이이면 ans++;

6 if (ans==0 || ans==3) printf("YES") or printf("NO");

여기서 예술이라고 생각하는 부분은 3, 4, 5 의 경계점 처리 부분이다.

12 0 1 12 1,  3 1 13 12 3 과 같은 예를 생각해보자.

12 0 1의 바늘침은 반드시 12와 1사이에 존재한다. 답은 YES

3 1 13의 바늘침 중 3 은 3과 12사이에 존재하며 1과 13은 12와 3 사이에 존재한다 답은 NO.

이런 예외를 어떻게 처리해줄 것인가?

3번만 예로 들면 

if (dep<=h && h<arr ) ans++;

if (dep<h && h<arr ) ans++; 의 차이는 전자는 h는 반드시 바늘침이 시간보다 약간 앞서있다는 느낌이다. 후자는 h는 바늘침이 가끔은 정시 또는 그 시간보다 약간 뒤에 있다는 느낌이다.

근데 시계 동작상 전자가 옳은 표현이다. 이런점이 매우 까다로운 문제.... 

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/implementation/p868b.c