cafelier@SRM

SRM481

あとで | 17:17 |

不参加。Practice でやってみたら (×, 300点くらい, 480点くらい) でした。参加者さんのスコアだけは見てたので500は十分解ける問題とわかっていたので解けたけど、本番だと500は多分テンパって解けてない気がする。

250

• lieCountとliarCountの重なりをうまく合わせて、「ちょうどピッタリeggCount人が真実を言っている」という状態にできるならeggである可能性がある。同様に「ピッタリn-eggCount人が真実を言っている」ならchickenの可能性がある、というのを計算。

class ChickenOracle { public:
  string theTruth(int n, int eggCount, int lieCount, int liarCount) 
  {
    bool egg = canTruthTellerBe(   eggCount, n, lieCount, liarCount );
    bool chk = canTruthTellerBe( n-eggCount, n, lieCount, liarCount );
    if( egg && chk ) return "Ambiguous";
    if( egg ) return "The egg";
    if( chk ) return "The chicken";
    return "The oracle is a lie";
  }
  bool canTruthTellerBe( int A, int n, int B, int  C )
  {
    int two_x = A+B+C - n;
    if( (two_x&1) == 1 )
      return false;
    int x = two_x/2;
    return 0<=x && x<=C && x<=B && (C-x)<=(n-B);
  }
};

• B人の嘘を教えられた人のうちx人が嘘つきで、n-B人の真実を教えられた人のうち(C-x)人が嘘つき
• とすると
• x + ( (n-B)-(C-x) ) 人が真実を喋るので、うんぬん
• 最後の条件の && x<=B && (C-x)<=(n-B) を忘れててもサンプルが通ってしまい死亡

500

• 各user毎にjobはまとめてやるのがベスト
  • [Aさんのjob1][Bさんのjob2][Aさんのjob2]
  • みたいなスケジュールがベストなことはない
  • なんでかというと [Bさんのjob2][Aさんのjob1][Aさんのjob2] としてもAさんの待ち時間は変わらないけどBさんは早まるから。
• 平均をさげるためには、総時間が長い人を最後に回すのがよいに決まっている
• とかなんとか

class BatchSystemRoulette { public:
  vector <double> expectedFinishTimes(vector <int> duration, vector <string> user) 
  {
    vector<double> answer(duration.begin(), duration.end());

    map<string, LL> userSum;
    for(int i=0; i<user.size(); ++i)
      userSum[user[i]] += duration[i];
    map<LL, vector<string> > usInv;
    for(map<string,LL>::iterator it=userSum.begin(); it!=userSum.end(); ++it)
      usInv[it->second].push_back(it->first);

    double base = 0;
    for(map<LL, vector<string> >::iterator it=usInv.begin(); it!=usInv.end(); ++it)
    {
      LL t = it->first;
      vector<string>& us = it->second;
      int n = us.size();

      double baseAve = base + t*(n-1)/2.0;
      for(int u=0; u<n; ++u)
      {
        vector<int> idxs;
        for(int i=0; i<answer.size(); ++i)
          if( user[i] == us[u] ) {
            answer[i] += baseAve;
            idxs.push_back(i);
          }
        for(int k=0; k<idxs.size(); ++k) {
          int i = idxs[k];
          for(int m=0; m<idxs.size(); ++m) if(m!=k) {
            int j = idxs[m];
            answer[i] += duration[j]/2.0;
          }
        }
      }

      base += t*n;
    }

    return answer;
  }
};

• というわけで、ジョブ時間の総和でuserをソート
• 短い順にわりあてていく
• 時間総和が同じユーザーが複数人いる場合は、ランダムに順番が決まるので開始時間はその平均で

• 問題は、一人のユーザーの抱える複数のジョブ（n個としよう）をどの順序で実行するかは n! 通りあって
• どの順でやるかによって各ジョブの終了時刻がかわるので…
• 重み付き平均が…
• ぬぬぬぬぬぬぬぬぬぬぬぬぬぬ

• すごい考えた結果
• ジョブ A とジョブ B のどっちが先に始まるかは確率1/2なので、
• Bが始まる時間は A で遅れるか遅れないかを考えると期待値的に time[A]/2 くらい遅まる
• を全部足せば期待値の線形性から求まる
• 全然自信ないけどサンプル通ったしいいや。

900

• 初期位置から左にあるきつつ通りすがりの全プリンタを起動し、右に歩きつつ通りすがりの全プリンタを起動し、…
• みたいな左右ウォークを繰り返すパターンしかありえんので
• (起動済みプリンタの一番左のヤツ, wantedのうちプリンタ投入済みの番号の集合, いま左右ウォークの結果左端にいるか右端にいるか)
• の N * (2^N) * 2 状態の DP でできる。

template<typename T>
struct DP3
{
  int N1, N2, N3;
  vector<T> data;
  DP3(int N1, int N2, int N3, const T& t = T())
    : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
  T& operator()(int i1, int i2, int i3)
    { return data[ ((i1*N2)+i2)*N3+i3 ]; }
  void swap(DP3& rhs)
    { data.swap(rhs.data); }
};

int bitcnt(int U)
{
  int c = 0;
  for(; U; U>>=1)
    c += (U&1);
  return c;
}

class TicketPrinters { public:
  int minTime(int currentPrinter, vector <int> printerDistance, vector <int> startingValues, vector <int> wantedValues) 
  {
    int N = startingValues.size();

    vector<int> d(N);
    partial_sum( printerDistance.begin(), printerDistance.end(), d.begin()+1 );

    // left, used, LeftOrRight
    DP3<int> dp(N,1<<N,2);
    for(int D=(1<<N)-1; D>=0; --D)
    {
      int bc = bitcnt(D);
      for(int L=0; L<N && L+bc<=N; ++L)
        for(int C=0; C<=1; ++C)
        {
          if( bc == N )
            dp(L,D,C) = 0;
          else {
            int cur = (C==0 ? L : L+bc-1);
            int mn = 0x7fffffff;
            for(int nextW=0; nextW<N; ++nextW)
              if( ((1<<nextW) & D) == 0 ) {
                int caseLeft = 0x7fffffff;
                if( L>0 ) {
                  caseLeft = d[cur] - d[L-1] + max(dp(L-1, D|1<<nextW, 0),
                    1+abs(startingValues[L-1]-wantedValues[nextW]));
                }
                int caseRight = 0x7fffffff;
                if( L+bc < N ) {
                  caseRight = d[L+bc] - d[cur] + max(dp(L, D|1<<nextW, 1),
                    1+abs(startingValues[L+bc]-wantedValues[nextW]));
                }
                mn = min(mn, min(caseLeft, caseRight));
              }
            dp(L,D,C) = mn;
          }
        }
    }
    return dp(currentPrinter,0,0);
  }
};

• DPの各状態からは、左に行くか右に行くかの2択と、次にどのwantedをプリンタに投入するかN通りしか選択肢がないので
• 全部で O(N^2 2^N) 時間