Hatena::Grouptopcoder

tsubosakaの日記

2010-09-09

SRM 481

22:58

久々のSRM

250

英語を読むのに苦労する。

本当のことを知っている人が何人liarになるかをループを回すと嘘を教えられた人が何人liarになるかはすぐにわかるので。観測値と整合性がとれているかをチェックすればよい。

public class ChickenOracle {
  boolean can(int n , int truthCount , int lieCount , int liarCount){
    int knownTruth = n - lieCount;
    int knownFalse = lieCount;
    for(int i = 0 ; i <= knownTruth ; ++i){
      int j = liarCount - i;
      if(j < 0 || j > knownFalse)continue;
      int sayTrue =  (knownTruth - i) + j;
      if(sayTrue == truthCount){
        return true;
      }
    }
    return false;
  }
  public String theTruth(int n, int eggCount, int lieCount, int liarCount) {
    int chickenCount = n - eggCount;
    boolean canEgg = can(n, eggCount, lieCount, liarCount);
    boolean canChicken = can(n , chickenCount , lieCount , liarCount);
    if(canEgg & canChicken){
      return "Ambiguous";
    }else if(canEgg){
      return "The egg";
    }else if(canChicken){
      return "The chicken";
    }else{
      return "The oracle is a lie";
    }
  }
}

500

平均待ち時間を短縮するためには早く終わるタスクから片づければよい。同順のタスク群に関しては各タスクに関してほかのタスクが前に来るかどうかの確率は1/2で、期待値の線形性を使うと同順のタスクにおける期待待ち時間は(ほかのタスク群の待ち時間) * 0.5となる。

import java.util.*;

public class BatchSystemRoulette {
  class Job{
    int index;
    long time;
    public Job(int i , long t) {
      index = i;
      time = t;
    }
  }
  class P{
    long total;
    List<Job> list;
    public P() {
      list = new ArrayList<Job>();
      total = 0;
    }
    void add(int i , long t){
      total += t;
      list.add(new Job(i , t));
    }
  }
  public double[] expectedFinishTimes(int[] duration, String[] user) {
    int N = duration.length;
    Map<String, P> map = new HashMap<String, P>();
    for(int i = 0 ; i < duration.length ; ++i){
      P p = map.get(user[i]);
      if(p == null){
        p = new P();
      }
      p.add(i, duration[i]);
      map.put(user[i], p);
    }
    double[] res = new double[N];
    for(String u : map.keySet()){
      P pu = map.get(u);
      long prev = 0;
      long same = 0;
      for(String other : map.keySet()){
        if(u.equals(other))continue;
        P po = map.get(other);
        if(po.total < pu.total){
          prev += po.total;
        }else if(po.total == pu.total){
          same += po.total;
        }
      }
      double expPre = prev + same * 0.5;
      for(Job j : pu.list){
        double other = pu.total - j.time;
        double pin = expPre + other * 0.5;
        res[j.index] = pin + duration[j.index];
      }
    }
    return res;
  }
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/tsubosaka/20100909