Hatena::Grouptopcoder

tsubosakaの日記

2010-01-20SRM 459

250

X (<|<=|=|>|>=) Cの形で不等式制約がいくつか渡されたときに任意のXを選んでいいときに最大でいくつ制約を満たせるか答えよという問題。0<=C<=1000でCは整数なので-0.5から1000.5まで0.5刻みでXを選んで試せばよい

public class Inequalities {
  boolean satisfy(String ineq , double x){
    String arr[] = ineq.split("\\s+");
    int C = Integer.parseInt(arr[2]);
    String E = arr[1];
    if(E.equals("<")){
      return x < C;
    }else if(E.equals("<=")){
      return x <= C;
    }else if(E.equals("=")){
      return x == C;
    }else if(E.equals(">")){
      return x > C;
    }else if(E.equals(">=")){
      return x >= C;
    }else{
      return false;
    }
  }

  boolean satisfy(String ineq , int x){
    String arr[] = ineq.split("\\s+");
    int C = Integer.parseInt(arr[2]);
    String E = arr[1];
    if(E.equals("<")){
      return x < C;
    }else if(E.equals("<=")){
      return x <= C;
    }else if(E.equals("=")){
      return x == C;
    }else if(E.equals(">")){
      return x > C;
    }else if(E.equals(">=")){
      return x >= C;
    }else{
      return false;
    }
  }
  public int maximumSubset(String[] inequalities) {
    int res = 0;
    for(int x = -1 ; x <= 1001 ; ++x){
      int s = 0;
      for(String ineq : inequalities){
        if(satisfy(ineq , x)){
          s++;
        }
      }
      res = Math.max(res, s);
    }
    for(double x = -0.5 ; x <= 1001.5 ; x += 1.0){
      int s = 0;
      for(String ineq : inequalities){
        if(satisfy(ineq , x)){
          s++;
        }
      }
      res = Math.max(res, s);
    }
    return res;
  }
}

500

いろいろ変形すると \sum_{k=0}^{baselength-1} \binom{baselength-1}{k} a_k = top, a_k > 0を満たす{a_k}の個数を求めればよいことがわかる。また、問題を変形して\sum_{k=0}^{baselength-1} \binom{baselength-1}{k} a_k = top - 2^{baselength -1}, a_k >= 0としたほうが都合がよい。

今、a_kの係数をc_kとおき、dp_xを

\sum_k c_k a_k = x

を満たす{a_k}の個数と定義すると、各係数cにおける更新式は

 dp[x\] = \sum_{i >= 0 , x - c * i >= 0} prev[x - c * i\]

と書ける。ここでprevは更新前のdpの値である。これをナイーブに実装しようとするとbaselength * top * topぐらいの計算量がかかり、baselength <= 20 *1, top <= 1000000なのでTLEになる。しかし計算式を変形すると

 dp[x\] = prev[x\] + dp[x - c\]

となることが解る。この式を用いることによってbaselength * top程度の計算量で解が求まる。

public class NumberPyramids {
  final static int MOD = 1000000009;
  // \sum_k corr[k] a_k = x , a_k > 0 を満たす{a_i}の個数を求める
  int solve(int corr[], int x) {
    for (int c : corr){
      // 条件をa_k > 0 から a_k >= 0に変形 
      x -= c;    
    }
    int dp[] = new int[x + 1];
    dp[0] = 1;
    for(int c : corr){
      for (int curr = c; curr < dp.length; curr++) {
        dp[curr] = (dp[curr - c] + dp[curr]) % MOD;
      }
    }
    return dp[x];
  }

  public int count(int baseLength, int top) {
    if (baseLength > 20 || top < (1 << (baseLength - 1))) {
      return 0;
    }
    int n = baseLength;
    int comb[][] = new int[n][n];
    comb[0][0] = 1;
    for (int i = 1; i < n; ++i) {
      comb[i][0] = 1;
      for (int k = 1; k <= i; ++k) {
        comb[i][k] = comb[i - 1][k - 1] + comb[i - 1][k];
      }
    }
    return solve(comb[n - 1], top);
  }
}

*1:21を超えるときは無条件で0を返して良い

ゲスト



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