Hatena::Grouptopcoder

tsubosakaの日記

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

SRM 310 Div1 Medium

| 18:17

幅Kの窓を配列の0からN-K+1までシフトさせるときに各場所での窓中の要素の中央値を求めよという問題.

配列の要素が65536までしか取りえないのでbinary indexed treeを使ってsum(0,i) >= K / 2となる場所を二分探索を使って求める.

public class FloatingMedian {
  class FenwickTree{
    long x[];
    public FenwickTree(int n) {
      x = new long[n];
    }
    long sum(int i , int j){
      if(i == 0){
        long s = 0;
        for( ; j >= 0 ; j = (j & (j + 1)) - 1){
          s += x[j];
        }
        return s;
      }else{
        return sum(0 , j) - sum(0 , i - 1);
      }
    }
    void add(int k , long a){
      for(; k < x.length ; k |= k + 1){
        x[k] += a;
      }
    }
    long ithpoint(int index){
      int low = 0;
      int high = x.length;
      while(low < high){
        int mid = low + (high - low) / 2;
        if(sum(0 , mid) >= index)
          high = mid;
        else
          low = mid + 1;
      }
      return low;
    }
  }
  final static int MOD = 65536;
  public long sumOfMedians(int seed, int mul, int add, int N, int K) {
    long[] t = generate(seed, mul, add, N);
    int mindex = (K + 1) / 2;
    FenwickTree ft = new FenwickTree(MOD);
    for(int i = 0 ; i < K ; i++)
      ft.add((int)t[i], 1);
    long res = 0;
    for(int i = 0 ; i < N - K + 1 ; i++){
      long median = ft.ithpoint(mindex);
      res += median;
      if(i + K < t.length){
        ft.add((int)t[i], -1);
        ft.add((int)t[i + K], 1);        
      }
    }
    return res;
  }

  private long[] generate(int seed, int mul, int add, int N) {
    long t[] = new long[N];
    t[0] = seed;
    for(int i = 1 ; i < N ; i++){
      t[i] = t[i - 1] * mul + add;
      t[i] %= MOD;
    }
    return t;
  }
}

SRM 310 Div1 Easy

| 18:08

上面と底面の面積の和は一番下のlevelだけで決まるのであとは側面の面積をレベルごとに足していけばよい.

public class PyramidOfCubes {
  public double surface(int K) {
    int level = 0;
    long size = 0;
    for(int i = 1 ; ; i++){
      level = i;
      size += i * i;
      if(size >= K)break;
    }
    double area = 2.0 * (Math.min(level * level, K));
    while(K >= level * level){
      area += 4.0 * level;        
      K -= level * level;
      level--;
    }
    if(K > 0){
      int w = ((K + level - 1) / level);
      if(w == 1)area += 2.0 * (1 + K);
      else area += 2.0 * (level + w);      
    }
    return area;
  }
}