Hatena::Grouptopcoder

tsubosakaの日記

2011-08-21

SRM 515

07:37

前に出たSRM 513と同様500が確率+メモ化で割と得意な問題だったので解けた。

250

愚直に0:00-23:59までを全通り試す。

public class RotatedClock {
  boolean eq(int h , int m , int h2 , int m2){
    for(int i = 0 ; i <= 12 ; ++i){
      if(h == h2 && m == m2)return true;
      h = (h + 30) % 360;
      m = (m + 30) % 360;
    }
    return false;
  }
  public String getEarliest(int hourHand, int minuteHand) {
    for(int h = 0 ; h < 12 ; ++h){
      for(int m = 0 ; m < 60 ; m += 2){
        int hd = (h * 60 + m) / 2;
        int md = m * 6;
        if(eq(hd , md , hourHand , minuteHand)){
          String ret = String.format("%02d:%02d", h , m);
          return ret;
        }
      }
    }
    return "";
  }
}

550

訪れたユーザの集合+残りの剣の数+現在時刻をキーにしたメモ化再帰。単純にユーザの集合を考えると2^24通りあるけど、一回しか訪れないユーザは訪れたというフラグを使う必要がないので2^12まで落ちる。あと再帰の手順のところで確率がその時点での条件付き確率になっているように前もって確率値を補正してやる。

import java.util.*;

public class NewItemShop {
  class Event implements Comparable<Event>{
    int u , t, c;
    double p;
    Event(int u , int t , int c , double p){
      this.u = u; this.t = t; this.c = c; this.p = p;
    }
    public int compareTo(Event o) {
      return t - o.t;
    }
  }
  
  long hashcode(long pat ,int s , int p){
    return (pat << 20L) | s * 32 | p;
  }
  Map<Long, Double> memo;
  double rec(int pattern , int sword , int p , Event[] es){
    if(sword == 0.0)return 0;
    if(p == es.length)return 0;
    long key = hashcode(pattern, sword, p);
    if(memo.containsKey(key)){
      return memo.get(key);
    }
    Event e = es[p];
    if((pattern & (1 << e.u)) != 0){
      double exp = rec(pattern , sword , p + 1 , es);
      memo.put(key, exp);
      return exp;
    }
    double prob = e.p;
    double exp = rec(pattern, sword, p + 1, es) * (1 - prob);
    if(freqs[e.u] == 1){
      double p1 = rec(pattern , sword - 1 , p + 1 , es) + e.c;
      double p2 = rec(pattern , sword , p + 1 , es);
      exp += Math.max(p1, p2) * prob;            
    }else{
      double p1 = rec(pattern | (1 << e.u) , sword - 1 , p + 1 , es) + e.c;
      double p2 = rec(pattern | (1 << e.u) , sword , p + 1 , es);
      exp += Math.max(p1, p2) * prob;      
    }
    memo.put(key, exp);
    return exp;
  }
  
  int freqs[];
  public double getMaximum(int swords, String[] customers) {
    List<Event> elist = new ArrayList<Event>();
    freqs = new int[customers.length];
    for(int i = 0 ; i < customers.length ; ++i){
      double T = 1.0;
      int cnt = 0;
      for(String e : customers[i].split("\\s+")){
        String[] sep = e.split(",");
        Event ev = new Event(i, Integer.parseInt(sep[0]), Integer.parseInt(sep[1]), Integer.parseInt(sep[2]));
        double p = ev.p * 0.01;
        ev.p = p / T;
        T -= p;
        elist.add(ev);
        ++cnt;
      }
      freqs[i] = cnt;
    }
    memo = new HashMap<Long, Double>();
    Collections.sort(elist);
    Event[] es = elist.toArray(new Event[0]);
    double res = rec(0, swords, 0, es);
    return res;
  }
}