Hatena::Grouptopcoder

tsubosakaの日記

2010-04-20

SRM 468

23:20

250

実装が結構重たい問題。

  1. キーシーケンスから単語リストの対応表を作る
  2. 前から見ていってスペース(0)が来たら直前の単語を出力する
  3. 最後に余った文字列を出力
vaParen

500

本番は極大な区間を大きい順からとってけばいいとか考えてしまったけど、それだと上手くいかないのでDPで解くのが正解だった。

現在、飛んでるか歩いてるかという2状態 * 最大K回まで乗り換えているという表を更新していく。状態表をN * K * 2のテーブルで持つとMLEになるので、K*2の配列を2つ用意して使い回せばいい。

import java.util.*;

public class RoadOrFlightHard {
  private long[] gen(int N , long first , long prod , long add ,long mod){
    long arr[] = new long[N];
    arr[0] = first % mod;
    for(int i = 1 ; i < N ; ++i){
      arr[i] = (arr[i - 1] * prod + add) % mod;
    }
    return arr;
  }
  
  private long minTime(long roadTime[] , long flightTime[] , int K){
    int N = roadTime.length;
    long dp[][][] = new long[2][2][K + 1];
    final int ROAD = 0;
    final int FLY  = 1;
    final long INF = Long.MAX_VALUE / 2;
    Arrays.fill(dp[0][FLY], INF);
    for(int i = 0 ; i < N ; ++i){
      int cur  =  i & 1;
      int next = (i + 1) & 1;
      for(int k = 0 ; k <= K ; ++k){
        dp[next][ROAD][k] = Math.min(dp[cur][ROAD][k] + roadTime[i] , dp[cur][FLY][k] + flightTime[i]); 
        if(k > 0){
          dp[next][ROAD][k] = Math.min(dp[next][ROAD][k], dp[cur][ROAD][k - 1] + flightTime[i]);
        }
        dp[next][FLY][k]  = dp[cur][FLY][k] + flightTime[i];
        if(k > 0){
          dp[next][FLY][k] = Math.min(dp[next][FLY][k] , dp[cur][ROAD][k - 1] + flightTime[i]);
        }
      }
    }
    return dp[N & 1][ROAD][K];
  }
  
  public long minTime(int N, int roadFirst, int roadProd, int roadAdd,
      int roadMod, int flightFirst, int flightProd, int flightAdd,
      int flightMod, int K) {
    long roadTime[] = gen(N, roadFirst, roadProd, roadAdd, roadMod);
    long flightTime[] = gen(N, flightFirst, flightProd, flightAdd, flightMod);
    return minTime(roadTime, flightTime, K);
  }
}

2010-04-04

SRM 466

13:29

250の方が難しかった

250

約数の個数が奇数となる数 = 平方数になるので高々10億未満の平方数について書き換えにかかる手数を求めて最小手数を求めれば良い。けど本番では約数の個数が奇数となる数 = 平方数に気付かず死亡。

  public int minimalChange(String ID) {
    int n = ID.length();
    long up = (long)Math.pow(10, n);
    int res = n;
    for(long i = 0 ; i * i < up ; ++i){
      String cand = String.valueOf(i * i);
      while(cand.length() < n)
        cand = "0" + cand;
      int diff = 0;
      for(int j = 0 ; j < n ; ++j)
        if(cand.charAt(j) != ID.charAt(j))
          ++diff;
      res = Math.min(res, diff);
    }
    return res;
  }

500

当たりになる列の状態は(5),(4,1),(3,2),(3,1,1)の4通りなので、これらすべてに対して場合の数を求めてやれば良い。

  double comb(int N , int r){
    double ret = 1.0;
    for(int i = 0 ; i < r ; ++i)
      ret *= N - i;   
    for(int i = 1 ; i <= r ; ++i)
      ret /= i;    
    return ret;
  }
  public double chanceToWin(int N) {
    double total = comb(5 * N , 5);
    double n5    = N;
    double n4    = N * (N - 1) * comb(5 , 1) * comb(5 , 1);
    double n32   = N * (N - 1) * comb(5 , 3)  * comb(5 , 2);
    double n311  = N * (N - 1) * (N - 2) / 2 * comb(5, 3) * comb(5 , 1) * comb(5 , 1);
    return (n311 + n32 + n4 + n5) / total;
  }