Hatena::Grouptopcoder

tsubosakaの日記

2009-01-19

SRM 320 Div1 Hard

| 19:08

n*m <= 80なのでmin(n,m) <= 8で一般性を失うことなく短い方を列としてよい.あとは現在の列の状態と配置したcheaterの数を状態としてDP.

すべての場合の数は\binom{n * m}{k}で求まる.なお\binom{80}[20} < 2^63より計算結果はlongに収まる.

import java.math.BigInteger;
import java.util.*;

public class SeatingPlan {
  List<Integer> accept(int m){
    List<Integer> res = new ArrayList<Integer>();
    l: for(int i = 0 ; i < (1 << m) ; i++){
      for(int j = 0 ; j + 1 < m ; j++)
        if((i & (1 <<j)) != 0 && (i & (1 <<(j+1))) != 0)
          continue l;      
      res.add(i);
    }    
    return res;
  }
  public String expectedTrial(int m, int n, int k) {
    if(m > n)return expectedTrial(n, m, k);
    List<Integer> alist = accept(m);
    int accept[] = new int[alist.size()];
    for(int i = 0 ; i < accept.length ; i++)
      accept[i] = alist.get(i);
    long memo[][] = new long[1 << m][k + 1];
    memo[0][0] = 1;   
    for(int col = 0 ; col < n ; col++){
      long next[][] = new long[1 << m][k + 1];
      for(int S : accept){
        for(int T : accept){
          if((S & T) != 0)continue;
          int i = Integer.bitCount(S);
          for(int a = 0 ; a <= k ; a++){
            if(a + i > k)break;
            next[S][a + i] += memo[T][a];
          }
        }
      }
      memo = next;
    }
    long sum = 0;
    for(int i = 0 ; i < memo.length ; i++)
      sum += memo[i][k];
    if(sum == 0)return "Impossible!";
    long tot = comb(m * n , k);
    return toStr(tot , sum);
  }
  long comb(int n , int k){
    long c[][] = new long[n + 1][n + 1];
    c[0][0] = 1;
    for(int i = 1 ; i <= n ; i++){
      c[i][0] = 1;
      for(int j = 1 ; j <= n ; j++){
        c[i][j] = c[i-1][j-1] + c[i-1][j];
      }
    }
    return c[n][k];
  }
  String toStr(long t , long s){
    BigInteger a = BigInteger.valueOf(t);
    BigInteger b = BigInteger.valueOf(s);
    BigInteger g = a.gcd(b);
    a = a.divide(g);
    b = b.divide(g);
    return a.toString() +"/" + b.toString();
  }
}

SRM 320 Div1 Medium

| 19:01

典型的DP.時間sから時間eの間に得られる最大の勝利確率をボトムアップに求めればよい.

import java.util.*;

public class ContestSchedule {
  public double expectedWinnings(String[] contests) {
    TreeSet<Long> ts = new TreeSet<Long>();
    for(String contest : contests){
      Scanner sc = new Scanner(contest);
      long start = sc.nextLong();
      long end = sc.nextLong();
      ts.add(start);
      ts.add(end);
    }
    List<Long> time = new ArrayList<Long>(ts); 
    int n = time.size();
    long dp[][] = new long[n][n];
    for(String contest : contests){
      Scanner sc = new Scanner(contest);
      long start = sc.nextLong();
      int s = Collections.binarySearch(time, start);
      long end = sc.nextLong();
      int e = Collections.binarySearch(time, end);      
      long win = sc.nextLong();
      dp[s][e] = win;
    }
    for(int l = 0 ; l < n ; l++){
      for(int s = 0 ; s < n ; s++){
        int e = s + l;
        if(e >= n)break;
        for(int m = s ; m <= e ; m++){
          dp[s][e] = Math.max(dp[s][e], dp[s][m] + dp[m][e]);
        }
      }
    }
    double res = 0.0;
    for(long d[] : dp)
      for(long l : d)
        res = Math.max(res, l);
    return res * 0.01;
  }
}

SRM 320 Div1 Easy

| 18:59

"12!"とか"3!!"などの形式で数字が二つ与えられるので大小比較しろという問題.

!の数が等しければ係数の比較をすればよく,そうでないときは!の数が大きい方を一段階計算して再帰的に比較する.ただ"10000!"とかを計算すると途中でオーバフローするので他方の係数よりも大きくなったときに打ち切る必要があるのと,"0!!"の扱いに気をつける必要がある.

public class ExtraordinarilyLarge {
  class Fact{
    long val;
    long fnum;
    Fact(String str){
      int i = str.indexOf('!');
      if(i < 0){
        val = Long.parseLong(str);
        fnum = 0;
      }else{
        val = Long.parseLong(str.substring(0, i));
        fnum = str.length() - i;
      }
      if(val == 0 && fnum > 0){
        val = 1;
        fnum = 0;
      }
    }
    Fact(long v  , long n){
      val = v; fnum = n;
    }
    long cmp(Fact f){
      if(fnum == f.fnum)
        return val - f.val;     
      if(fnum < f.fnum)return - f.cmp(this);
      long r = 1;
      for(long v = 1 ; v <= val ; v++){
        r *= v;
        if(r > f.val)return 1;
      }
      Fact a = new Fact(r , fnum - 1);
      return a.cmp(f);
    }
  }
  public String compare(String x, String y) {
    Fact fx = new Fact(x);
    Fact fy = new Fact(y);
    long c = fx.cmp(fy);
    System.err.println(c);
    if(c > 0)return "x>y";
    else if(c < 0)return "x<y";    
    return "x=y";
  }
}

WilliamTagWilliamTag 2019/02/02 11:26 cialis over night
medicus group buy cialis
<a href=https://greatwinesgrandhouses.com>Cheap cialis buy online</a>
does cialis get you hard
cheapest cialis 20mg
https://kellyannehulme.com
buy cialis montreal
generic cialis in 2.5mg daily tablets
<a href=https://kellyannehulme.com>20 mg cialis</a>
lilly cialis without prescription
cialis brand name usa price
https://greatwinesgrandhouses.com

WilliamTagWilliamTag 2019/02/02 11:26 cialis ads
buying cialis in canada online
<a href=https://greatwinesgrandhouses.com>buy Cialis 20 mg</a>
liquid cialis does it work
cialis and avodart
https://kellyannehulme.com
what does cialis cost in mexico
cialis venezuela
<a href=https://greatwinesgrandhouses.com>Cheap cialis</a>
the cheapest cialis online
headache after cialis
https://greatwinesgrandhouses.com

ArnoldNizArnoldNiz 2019/02/05 20:50 canada drug generic cialis
buy generic cialis from canada
<a href="http://xcialisxx.com">Cheap Cialis</a>
snort cialis
cialis online con ricetta
<a href="http://cialistlm.com">Cheap Cialis buy</a>
brand cialis online mastercard
quick ship cialis
<a href="http://xcialisxx.com">Cheap Cialis</a>

ゲスト



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