[JOI Spring Camp 2018/2019] Two Transportations

문제 : https://oj.uz/problem/view/JOI19_transportations

---

N개의 도시로 이루어진 나라가 있다.

 

각 도시는 버스 노선과 지하철 노선으로 이루어져 있다.

Azer는 버스 노선만 알고 있고,

Baijan은 지하철 노선만 알고 있다.

Azer와 Baijan은 서로 비트를 주고 받을 수 있다.

 

비트를 이용하여 정보를 주고 받은 후,

버스 노선만 아는 Azer가 지하철 노선까지 이용하여, 0번 도시에서 각 도시로 가는 최소 비용을 구하는 문제

 

구현해야 할 함수(Azer.cpp)

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C)

A는 버스 노선의 개수

U와 V는 각각 버스 노선의 출발 도시와 도착 도시가 저장되어 있는 길이가 A인 배열이다.

C는 버스 노선의 비용이 된다.

즉, \(i\)번 버스 노선은 U[i]→V[i]이고, 이 때 비용은 C[i]이다.

 

void ReceiveA(bool x)

Baijan이 비트를 보낸 경우 해당 함수가 호출된다.

x는 Baijan이 송신한 비트다.

 

vector<int> Answer()

0번 도시에서 N개의 모든 도시까지의 최단거리를 반환해야하는 함수

 

구현해야 할 함수(Baijan.cpp)

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D)

B는 지하철 노선의 개수

S와 T는 각각 지하철 노선의 출발 도시와 도착 도시가 저장되어 있는 길이가 B인 배열이다.

D는 지하철 노선의 비용이 된다.

즉, \(i\)번 지하철 노선은 S[i]→T[i]이고, 이 때 비용은 D[i]이다.

 

void ReceiveB(bool y)

Azer가 비트를 보낸 경우 해당 함수가 호출된다.

y는 Azer가 송신한 비트다.

 

인터렉션

void SendA(bool y)

InitA()와 ReceiveA()에서 호출 가능

해당 함수를 호출한 만큼 ReceiveB()가 호출된다.

 

void SendB(bool x)

InitB()와 ReceiveB()에서 호출 가능

해당 함수를 호출한 만큼 ReceiveA()가 호출된다.

 

제약

• N은 최대 2000
• 지하철 노선과 버스 노선의 개수는 각각 최대 50만개
• 각 노선의 비용은 최소 1, 최대 500이하
• 버스와 지하철을 이용하여 어떤 도시로든 갈 수 있다.
• sendA()와 sendB()는 합쳐서 최대 58000번 호출할 수 있다.
• Subtask
  1. (6점) A=0
  2. (8점) B\(\le\) 1000
  3. (8점) A+B=N-1
  4. (38점) N\(\le\)900
  5. (14점) N\(\le\)1100
  6. (10점) N\(\le\)1400
  7. (16점) No additional constraints

 

main.cpp 로직

func SendA(y)
	queueA.push(y)
func SendB(x)
	queueB.push(x)
...
InitA() //SendA() 호출 가능
InitB() //SendB() 호출 가능
while(1)
	if queueA
		ReceiveA(queueA.front) //SeneA() 호출 가능
	else if queueB
		ReceiveB(queueB.front) //SendB() 호출 가능
	else
		break
Answer()
...

---

풀이

Subtask 1

A가 0이니, Baijan에서 다익스트라를 한 번 수행하고, 최종 비용을 송신하면 된다.

N은 최대 2000, 비용은 최대 500이기 때문에, \(2000 \times 500 < 2^{20} \)이므로, 

도시 하나당 20개의 비트로 나타낼 수 있다.

\(20 \times 2000 = 40000\) 이므로, 58000개 미만의 비트로 송신할 수 있다.

 

그러므로 구현시, Baijan에서는 SendB()만 호출하면 되고, Azer에서는 ReceiveA()가 호출될 때마다 비트를 기록한다.

이후 Answer()에서 20개씩 비트를 복원하면 정답 벡터를 구할 수 있다.

 

 

---

Subtask 2

B가 1000개 밖에 되지 않는다.

지하철 노선 정보 (S,T,D)를 나타내는데 필요한 비트 수는 11+11+9=31이다.

\(31\times 1000=31000\)개의 비트를 Azer에게 송신하면 된다.

 

---

Subtask 3

도시들이 트리로 이루어진 점을 이용한다.

루트 노드를 제외 하면, 엣지와 노드는 하나씩 대응이 된다.

지하철 노선 정보 (S,T,D)에서 S 순서대로 비트를 송신한다면 (T,D) 정보만 송신할 수 있다.

\(20\times 2000=40000\)개의 비트를 Azer에게 송신하면 된다.

 

---

코드 상에서 Subtask 조건 판별이 어려워 실제로 구현 시 복잡할 수 있다.

 

---

만점 풀이

버스 노선과 지하철 노선을 나누어서 생각해보자

 

그리고 각 다익스트라 스텝마다 최소 비용을 갱신해보자

 

최소 비용이 계산되면 각 도시의 최소 비용을 서로 공유한다.

Azer는 Baijan에게 현재 다익스트라 테이블 정보를 보내고, Baijan도 Azer에게 보낸다.

 

Azer와 Baijan 모두 비용이 6인 정점을 선택한다.

그리도 다시 갱신된 비용 정보를 보낸다.

Azer와 Baijan 모두 비용이 7인 정점을 선택한다.

이 방법은 \(N^2\)이기도 하고, 비트도 당연히 부족하다.

 

그런데 위에서 보여준 통신 방법에서 의미없는 정보가 있다.

바로 최소 비용 외 거리 정보다.

 

그러므로 보낼 때는 최소 비용과 그 최소 비용을 가지는 정점 인덱스를 보내자

Azer에서 비용이 6인 정점은 2번 정점이고, Baijan에서 비용이 7인 정점은 1번 정점이다. 

 

Azer는 자신의 테이블과 Baijan이 보낸 최소 비용 정점 정보를 비교한다.

자신의 테이블에 있는 비용 6이 가장 최소이므로 비용이 6인 정점을 선택한다.

 

Baijan도 자신의 테이블과 Azer가 보낸 최소 비용 정점 정보를 비교한다.

자신의 테이블에 있는 비용보다 Azer가 보낸 비용이 가장 최소 이므로, Azer가 보낸 정점을 선택한다.

 

이러면 한 번 전송시마다 필요한 비트 개수는 (20+11)\(\times\)2=62이다.

N\(\le {58000 \over 62} \risingdotseq 935\)까지 풀이할 수 있다.

 

---

 

비트 사용량을 더 줄이기 위해, 필요 없는 정보를 더 줄여보자

아래 그림의 경우, 하나의 정점 정보는 필요가 없다.

 

비트 정보를 서로 보내는 이유는 최소 비용을 가진 정점을 선택하기 위한 것이다.

그러므로 우선 비용 정보만을 보낸다.

Azer는 Baijan의 비용 7보다 자신의 비용 6이 더 낮다는 것을 알았다.

Azer는 비용이 6인 정점을 선택한다.

Baijan은 Azer의 비용 6이 자신의 비용 7보다 더 낮다는 것을 알았다.

그러나 비용 6인 정점의 인덱스는 아직 알 수 없다.

 

그러므로 Azer는 자신의 비용이 더 작다는 사실을 알았으니, 자신이 고른 정점 인덱스 정보를 Baijan에게 보내야 한다.

Baijan은 Azer의 정점 정보를 한번 더 받아서, 비용 6도 갱신하고 2번 정점도 선택할 수 있다.

정점 갱신마다 사용하는 비트는 20\(\times\)2+11=51이다.

N\(\le {58000 \over 51} \risingdotseq 1137\)까지 풀이할 수 있다.

 

---

아직 만점이 되지 않았다.

최적화가 필요한 부분을 더 찾아보자

 

위 방법 모두 비용의 최대값을 고려하여 20비트를 사용하였다.

하지만 엣지 비용의 최대값은 500으로 9비트만으로 충분하다.

 

즉, 다익스트라의 현재 정점에서 다음 정점을 선택할 때, d[nxt]-d[curr]의 값은 최대 500을 넘기지 않는다.

그러므로 비용의 상대값을 보낸다면 20비트가 아니라 9비트만으로 충분하게 된다.

 

정점 갱신마다 사용하는 비트는 9\(\times\)2+11=29이다.

N\(\le {58000 \over 29} \risingdotseq 2000\)으로 만점을 받을 수 있다.

 

 

 

---

참조

https://www.ioi-jp.org/camp/2019/2019-sp-tasks/day2/transportations-review.pdf