cafelier@SRM

TCO10 R3 500

あとで | 17:06 |

• むずかしい

class TheChroniclesOfAmber { public:
   double minimumTime(vector <int> princeX, vector <int> princeY, vector <int> destinationX, vector <int> destinationY) 
   {
      int N = princeX.size();

      // d[s][g] := the distance from prince[s] to dest[g]
      vector< vector<double> > d(N, vector<double>(N));
      for(int s=0; s<N; ++s)
         for(int g=0; g<N; ++g)
            d[s][g] = hypot(princeX[s]-destinationX[g], princeY[s]-destinationY[g]);

      // no teleportation
      double noTelepo = 0;
      for(int i=0; i<N; ++i)
         noTelepo = max(noTelepo, d[i][i]);

      // with teleportation: at least one position must be empty
      double answer = noTelepo;
      for(int unused_s=0; unused_s<N; ++unused_s) {
         double withTelepo = 0;
         for(int g=0; g<N; ++g) { // for each goal
            double t = 1e+300;
            for(int s=0; s<N; ++s) if( s != unused_s )
               t = min(t, d[s][g]); // find the nearest starting point
            withTelepo = max(withTelepo, t);
         }
         answer = min(answer, withTelepo); // take the minimum
      }
      return answer;
   }
};

• 瞬間移動は、やるとしたら最初の一瞬のみ
  • (直感的には自明な気がするんだけど証明できてない)

• まったく瞬間移動を使わない場合
  • 距離の最大値が答え
    • (ok)

• 瞬間移動を使う場合
  • 元々王子様がいた場所N箇所のうち、どこか一カ所には誰もいない状態になる
    • (ok)
  • 逆に、「どこか一カ所には誰もいない状態」は全てどの状態であっても作れる
    • (証明できてない)
    • この仮定の下で、「誰もいない初期位置」をどこにするかN通り全探索して、あとは全員目的地に一番近いところに飛んでいくとすれば最小の答えが出る

• 『「どこか一カ所には誰もいない状態」は全てどの状態であっても作れる』
  • 作りにくい状態というのは [A] [B] [C] を [C] [A] [B] のようにサイクル状にぐるっと回すときだけなので
  • ひとり犠牲者のDさんを連れてくれば
    • [A][B][CD]
    • [CA][B][D]
    • [C][AB][D]
    • [C][A][BD]
  • のように所望の移動ができるので、
  • あとは、こういうサイクルが何個あってもこのDさんを市中引きずり回しの系にして他全員動かしてから、最後にDさんが行きたいところに飛べばいい

• 誰をDさんにするかは
• 一カ所は初期位置を空けるので、鳩ノ巣原理により全テレポート完了後はどっかに二人重なる
• その重なるところに行く人を犠牲者にすれば「最後に行きたいところに飛べばいい」が可能になるので、
• このプランは可能

• とかそんな感じかな。厳密ではないけど。