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;
  }
}

2009-01-17

SRM 310 Div1 Hard

| 18:20

すでに使った箱の集合といちばん上の箱の状態をキーとしてDPする.箱の状態はどこをz軸にするかの3通り考えれば十分なのでキーの数は2^n * 3n でn <= 15より実行時間内に解ける.

public class BoxTower {
  public int tallestTower(int[] x, int[] y, int[] z) {
    int n = x.length;
    int dp[][] = new int[1 << n][3 * n];
    int ws[][] = new int[3 * n][2];
    int hs[] = new int[3 * n];
    for(int i = 0 ; i < n ; i++){
      dp[1 << i][i] = hs[i] = z[i];
      ws[i][0] = Math.min(x[i], y[i]);
      ws[i][1] = Math.max(x[i], y[i]);
      dp[1 << i][i + n] = hs[i + n] = y[i];
      ws[i + n][0] = Math.min(x[i], z[i]);
      ws[i + n][1] = Math.max(x[i], z[i]);
      dp[1 << i][i + 2 * n] = hs[i + 2 * n] = x[i];
      ws[i + 2 * n][0] = Math.min(y[i], z[i]);
      ws[i + 2 * n][1] = Math.max(y[i], z[i]);
    }
    for(int S = 0 ; S < dp.length ; S++){
      for(int j = 0 ; j < 3 * n; j++){
        int tj = j % n;
        if((S & (1 << tj)) == 0)continue;
        for(int k = 0 ; k < 3 * n ; k++){
          int tk = k % n;
          if(((S & (1 << tk))) != 0)continue;
          int next = (S | (1 << tk));
          if(ws[k][0] <= ws[j][0] && ws[k][1] <= ws[j][1])
            dp[next][k] = Math.max(dp[next][k], dp[S][j] + hs[k]);          
        }
      }
    }
    int res = 0;
    for(int d[] : dp){
      for(int i : d)res = Math.max(i, res);
    }
    return res;
  }
}

2009-01-15

SRM 286 Div1 Medium

| 09:33

常にプレイヤー0から始めるとすれば各プレイヤーの勝利数は(green,red,black)の値で一意に定まる.残りの色の数を状態としてメモ付き探索.

public class BallGift {
  long memo[][][][];
  int players;
  long[] rec(int green , int red , int black, int pnum){
    if(memo[green][red][black] != null){
      return memo[green][red][black];
    }
    long res[] = new long[players];
    if(green == 0 && red == 0 && black == 0){
      //player 0 win
      res[0] = 1;
    }else{      
      if(green > 0){
        long next[] = rec(green - 1 , red , black , pnum);
        for(int i = 0 ; i < pnum ; i++){
          res[(i + 1) % pnum] += next[i];
        }
      }
      if(red > 0){
        long next[] = rec(green  , red - 1, black , pnum);
        for(int i = 0 ; i < pnum ; i++){
          res[pnum - 1 - i] += next[i];
        }
      }
      if(black > 0){
        long next[] = rec(green  , red , black - 1, pnum - 1);
        //remove player 0
        for(int i = 1 ; i < pnum ; i++){
          res[i] += next[i - 1];
        }
      }
    }
    return memo[green][red][black] = res;
  }
  public int bestPosition(int players, int green, int red, int black) {
    this.players = players;
    memo = new long[green + 1][red + 1][black + 1][];    
    long winnum[] = rec(green, red, black , players);
    int res = 0;
    for(int i = 1 ; i < winnum.length ; i++)
      if(winnum[res] < winnum[i])
        res = i;
    return res;
  }
}

2009-01-14

SRM 250 Div1 Medium

| 20:29

見る番組を一つ定めて,その番組の開始時間を基準とすると循環がなくなるのであとは時刻sからtまでの最大視聴時間dp(s,t)はdp(s , t) = min_{s <= m <= t} dp(s , m) + dp(m , t)と書けることを利用してDP.

import java.util.*;

public class TVWatching {
  int toInt(String time){
    int h = Integer.parseInt(time.substring(0,2));
    int m = Integer.parseInt(time.substring(3,5));
    int res = h * 60 + m;
    if(h == 12){
      if(time.endsWith("AM"))
        res += 720;      
    }else{
      if(time.endsWith("PM"))
        res += 720;
    }
    return res;
  }
  int[] toInts(String program){
    String start = program.substring(0 , 7);
    String end = program.substring(10);
    return new int[]{toInt(start) , toInt(end)};
  }
  int calc(int ps[][]){
    int n = ps.length;
    Set<Integer> set = new TreeSet<Integer>();
    for(int p[] : ps){
      for(int i : p){
        if(i < 0)continue;
        set.add(i);
      }
    }
    int times[] = new int[set.size()];
    int cnt = 0;
    for(int i : set)
      times[cnt++] = i;
    Arrays.sort(times);
    int dp[][] = new int[times.length][times.length];
    for(int i = 0 ; i < n ; i++){
      if(ps[i][0] < 0)continue;
      int s = Arrays.binarySearch(times, ps[i][0]);
      int e = Arrays.binarySearch(times, ps[i][1]);
      dp[s][e] = ps[i][1] - ps[i][0];
    }
    for(int len = 1 ; len < dp.length ; len++){
      for(int i = 0 ; i < dp.length ; i++){
        int j = i + len;
        if(j >= dp.length)continue;
        for(int m = i; m <= j ; m++){
          dp[i][j] = Math.max(dp[i][j], dp[i][m] + dp[m][j]);          
        }
      }
    }
    int max = 0;
    for(int d[] : dp)
      for(int i : d)
        max = Math.max(max, i);
    return max;
  }
  int mostMinutes(int[][] programs){
    int n = programs.length;
    int res = 0;
    for(int i = 0 ; i < n ; i++){
      int ps[][] = new int[n][2];
      int start = programs[i][0];
      int end = programs[i][1] - programs[i][0];
      if(end <= 0)end += 1440;
      for(int j = 0 ; j < n ; j++){
        int st = programs[j][0] - start;
        int ed = programs[j][1] - start;
        if(st <= 0)st += 1440;
        if(ed <= 0)ed += 1440;
        if(st < end || ed < st )
          st = ed = -1;
        ps[j][0] = st; ps[j][1] = ed;
      }
      int r = calc(ps);
      res = Math.max(res, end + r);
    }
    return res;
  }
  public int mostMinutes(String[] programs) {
    int n = programs.length;
    int ps[][] = new int[n][2];
    for(int i = 0 ; i < n ; i++){
      ps[i] = toInts(programs[i]);
      if(ps[i][0] == ps[i][1])
        return 1440;
    }
    return mostMinutes(ps);
  }
}

SRM 173 Div1 Hard

| 19:25

与えられた点からn個選んだ時に選んだ点の凸包の面積を最大にせよという問題.

  • 候補点は凸包の中から選べばよい
  • 始点を固定した後に、一個前の点と残りの選べる点の個数を状態としてメモ付き探索を行う
  • 再帰式はf(start , p , n) = max_q ( f(start , q , n - 1) + |start-p-q|)と書ける
import java.util.*;

public class ElectronicScarecrows {
  class Point {
    double x, y;

    Point(double a, double b) {
      this.x = a;
      this.y = b;
    }

    @Override
    public String toString() {
      return x + " : " + y;
    }

    double norm() {
      return x * x + y * y;
    }
  }
  double cross(Point a, Point b, Point c) {
    double res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return res;
  }
  double cmp(Point a , Point b){
    if(a.x != b.x)return a.x - b.x;
    return a.y - b.y;
  }
  double dist(Point a , Point b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy;
  }
  List<Point> convexHull(List<Point> ps) {
    List<Point> res = new ArrayList<Point>();
    if(ps.size() < 3)return res;
    int N = ps.size();
    int p = 0;
    for(int i = 1 ; i < N ; i++)
      if(cmp(ps.get(i) , ps.get(p)) < 0)
        p = i;
    boolean used[] = new boolean[N];
    int st = p;
    do{
      int n = -1;
      double dist = 0.0;
      for(int i = 0 ; i < N ; i++){
        if(i == p)continue;
        if(used[i])continue;
        if(n == -1)n = i;
        double cross = cross(ps.get(p) , ps.get(i) , ps.get(n));
        double d  = dist(ps.get(i) , ps.get(p));
        if(cross < 0){
          n = i;
          dist = d;
        }else if(Math.abs(cross) < 1.0E-11){
          if(d > dist){
            dist = d;
            n = i;
          }
        }
      }
      res.add(ps.get(p));
      p = n;
      used[p] = true;
    }while(st != p);
    return res;
  }
  double triarea(Point p0 , Point p1 , Point p2){
    return Math.abs(cross(p0 , p1 , p2)) * 0.5;
  }
  double memo[][];
  Point ps[];
  double rec(int pstart , int prev , int n){
    if(n == 0)return 0.0;
    if(memo[prev][n] >= 0.0)
      return memo[prev][n];
    double res = 0.0;
    int p = (prev + 1) % ps.length;
    while(p != pstart){
      double t = triarea(ps[pstart] , ps[prev] , ps[p]);
      double r = rec(pstart , p , n - 1);
      res = Math.max(res, t + r);
      p = (p + 1) % ps.length;      
    }   
    return memo[prev][n] = res;
  }
  public double largestArea(int[] x, int[] y, int n) {
    List<Point> plist = new ArrayList<Point>();
    for(int i = 0 ; i < x.length ; i++){
      plist.add(new Point(x[i] , y[i]));
    }
    List<Point> hull = convexHull(plist);
    this.ps = hull.toArray(new Point[0]);
    int hs = hull.size();
    double res = 0.0;
    for(int pstart = 0 ; pstart < hull.size() ; pstart++){
      memo = new double[hs][n];
      for(int i = 0 ; i < hs ; i++)
          Arrays.fill(memo[i] , -1);
      for(int p0 = pstart + 1 ; p0 < hs ; p0++){
        double r = rec(pstart , p0  , n - 2);
        res = Math.max(res, r);
      }
    }
    return res;
  }
}

RoberGrotlyRoberGrotly2017/05/08 23:31Amoxicilina Internet Where To Buy Levitra Deezer <a href=http://byuvaigranonile.com>viagra</a> Malegra Amoxicillin Trihydrate 250 Dosage Propecia Zwanger Worden