Educational Codeforces Round 146 (Rated for Div. 2) - C. Search in Parallel (1500)

C. Search in Parallel

찍어봤는데 정답이였다.

뭔가 BOJ 17528같은 DP 같아 보이지만, 로봇의 동작을 잘 이해하여 그리디가 성립함을 관찰하는게 중요하다.

결국 최소화해야하는건 두 로봇이 동시에 움직일때가 아닌 한 로봇이 박스를 가져오는 동안 다른 로봇은 쓸모없기 때문에 모든 박스를 가져오는데 시간 합이란 것이다.

먼저 $r_i$ 가 클 수록 먼저 배치하는것이 이득이다.

더 많이 가져와야하면 더 빠른 순서에 배치시키는 것이 최적일 것이기 때문이다.

$r_i$를 내림차순 정렬하고 $A,B$ 에 하나하나 넣어준다.

새롭게 넣어줄 것까지 도달하는 시간은 각각 $s_1 \cdot \vert A \vert, \, s_2 \cdot \vert B \vert$ 이다.

그럼 현재것까지 조사하려면 $s_1\cdot(\vert A \vert+1), s_2 \cdot (\vert B \vert+1)$ 이므로 이 둘중 더 작은것에 넣는다.

에디토리얼 증명

에디토리얼에선 재배열 부등식 얘기를 꺼낸다.

$\text{Min} \sum_{i=1}^{m}a_ib_i$ 는 $a_i$의 가장 큰것과 $b_i$의 가장 작은것… 처럼 짝지어주는 것이 가장 작다는 것이다.

리스트에 $2n$의 위치가 있고 계수가 각각 있다.

$A$ 쪽의 계수는 앞에서부터 $s_1, 2s_1, 3s_1, \dots$ 같은 식이다.

$1 \to n$의 상자들 모두를 이 $2n$ 개의 위치에 배치해야한다.

그러나 우리는 $n$ 개의 상자들밖에 없으므로 일단 계수가 작은 앞쪽부터 배치를 하며, 둘 중 그냥 계수가 작은 위치를 골라나가면 된다는 것이다.

더 $r_i$가 클수록 $A,B$ 에 있는 모든 계수중 남은것들중에 가장 작은 계수에 배치하는것이 효율적이기 때문이다.

void solve() {  
   int n, s1, s2;  
   cin >> n >> s1 >> s2;  
   vi r(n);  
   fv(r);  
   vi idx(n);  
   iota(all(idx), 0);  
   sort(all(idx), [&](int i, int j) { return r[i] > r[j]; });  
   vi A, B;  
   for (int i = 0; i < n; i++) {  
      if (sz(A) * s1 + s1 < sz(B) * s2 + s2) A.pb(idx[i]);  
      else B.pb(idx[i]);  
   }  
   cout << sz(A) << ' ';  
   for (int i: A) cout << i + 1 << ' ';  
   cout << endl;  
   cout << sz(B) << ' ';  
   for (int i: B) cout << i + 1 << ' ';  
   cout << endl;  
}