#19927 Vision Program

https://www.acmicpc.net/problem/19927

 

H * W grid의 모든 배치에 대해서 두 black pixel의 거리가 K인지 확인할 수 있는 instruction을 만들어라

H,W, K <= 200 = N이라 하자

Instruction의 수 <= 1e4, 항의 수 <= 1e6

 

단상 1.

일단 단순히 모든 K거리 쌍을 확인해야한다면 대략 N^3로 많다.

당연하게도 여러 질문을 한 번에 묻는 것이 좋음.

맨 마지막에는 K거리 쌍에 대한 답을 모두 OR 시켜서 답으로 제출하면 된다.

 

다음과 같이 질문을 하면 어떨까

F(i, j) = add_or(어떤 점 (i, j)로 부터 K만큼 떨어진 모든 점)

-> 그러면 대충 F(i, j) & (i, j)를 확인해주면 답이 된다.

여기서 사용되는 instruction의 수는 2HW + 1, 항의 수는 2HWK 정도로 아직 조금 많다.

 

단상 2.

위에서 생각해낸 instruction의 방식은 점 하나와 주변의 사각형을 동시에 물어본다.

하지만, 사각형의 변 하나만 떼어낸다면, 완벽히 반대쪽에 존재하는 점에 대해서도 같이 물어봐도 됨을 알 수 있다.

근데 이렇게만 물어보면 질문의 개수가 2배가 된다 (4배가 되고, 두 점을 동시에 물어보니 /2)

 

길이 K + 1짜리인 변을 물어보지 말고, 양끝을 떼어낸 K - 1을 물어보자. 

이러면 한 번에 4개의 점을 물어볼 수 있고 질문의 개수가 동일해진다. 더 줄일 수 있을까?

 

단상 3.

또 해본 생각이 마치 격자판같은 아이디어.

예를 들어 격자판을 물어보면 거리는 무조건 홀수가 될 것이다. (2^0의 계수에 차이)

만약에 모든 2^i의 계수에 대해서 차이를 구할 수 있다면 답을 구할 수 있다.

-> K도 가진 항에서는 모두 1이고, K가 가지지 않은 항에서는 모두 0이면 되는 것

그러면 이진법으로 각각 dx, dy를 구하고 이 값의 합이 K랑 같은지 확인해주면 된다.

이때 단순히 다른지만 보면 dx의 이진법 각 항의 부호를 모르니까 안됨. (1, 2가 켜지면 1 + 2 = 3인지, 2 - 1 = 1인지 모름)

-> 이거는 +만되도록 설계하면 된다.

-> AND(1행, OR(2, 4, 6, 8...)), AND(2행, OR(3, 5, 7, 9...),.. 중 하나라도 1이면 행이 1 차이나는 것이고, dx[0] =1

-> AND(1행, OR(3, 4, 5, 7...)), AND(2행, OR(3, 4, 5, 7...),.. 중 하나라도 1이면 행이 2 차이나는 것이고, dx[1] =1

->...

-> 모든 항이 아니라, 모든 행에 대한 작업이라서, N이 하나 빠지기에 생각보다 횟수가 많지 않다.

 

위의 방법을 통해서 dx[0], dx[1], ... dx[7]와 dy[0], dy[1], ... dy[7]을 구할 수 있다.

그러면 가산기를 잘 떠올리고 (이 과정에서 나는 그동안 쓰지 않은 XOR을 사용하였다)

이 값이 K를 이진법으로 나타낸 것과 동일한지 확인해주면 된다.

 

다른 풀이.

위에서는 덧셈을 구현해야 했지만 덧셈을 쓰지 않는 방법이 있다.

well known) distance = max( abs((x1 + y1) - (x2 + y2), abs((x1 - y1) - (x2 - y2)) )

따라서 저 두 개의 abs 값이 모두 K 이하일 때만 답이 성립하게 된다.

그러면 우선 (x + y), (x - y) 값별로 모두 묶어둔 항들을 만들어두자.

만일 abs값이 K 이하라면, (x + y)의 연속한 K개 중에 pixel이 2개 있는 경우나 (x - y)의 연속한 K개 중에 2개 있어야 한다.

ex) x + y가 (1, 2, 3, 4)인 애들을 모두 확인했을 때, pixel이 2개 있다면, 차이는 3 이하이다.

    -> 계속해서 (2, 3, 4, 5), (3, 4, 5, 6) 등을 확인해주면 된다.

이러한 방식으로 두 pixel의 값이 K 이하인지 확인할 수 있다.

-> 여기서 K 이하는 성립하지만 같은 방식으로 K + 1이 성립하지 않는다면, 정확히 K인 것이다

 

내 풀이는 모든 비트에 대해서 차이를 보는, log개로 쪼개는 방식을 사용했고, 여기에 가산기 구현

정해는 K, K + 1을 관찰하는, 즉 2개로 쪼개는 방식을 사용했고, 단순히 (K) & !(K + 1)로 끝

비트로 계산횟수를 줄이는 것도 좋지만, 경계를 통해서 계산을 줄이는 방식도 고민해보아야 한다.

사실 결국 (x + y)와 (x - y)라는게 단상 1, 2에서 나온 사각형의 변들이기에 충분히 생각해낼만 했다.