Hatena::Grouptopcoder

tsubosakaの日記

2009-02-25

TCO 09 Qualification Round 1 Medium

| 00:19

1 <= min <= 10^12, min <= max <= min + 10^6のときに自乗数(4,9,16...)で割り切れない数が[min,max]にいくつあるか答えよという問題.

素因数の候補としてはsqrt(min) <= 10^6までの数の自乗した値に関して調べればよい。調べ方としては[min,max]の中で自乗数を素因数としてもつ最小の値から素因数おきにふるっていけばよい。

import java.util.*;

public class SquareFreeNumbers {
  public int getCount(long min, long max) {
    int N =(int)(max - min + 1);
    boolean memo[] = new boolean[N];
    Arrays.fill(memo, true);
    for(long p = 2 ; p * p <= max ; p++){
      long p2 = p * p;
      long s = ((min + p2 - 1)/ p2) * p2;
      for(; s <= max ; s += p2)
        memo[(int)(s - min)] = false;      
    }
    int res = 0;
    for(int i = 0 ; i < memo.length ; i++)
      if(memo[i])res++;    
    return res;
  }
}

2009-02-08

SRM 434 Div1 Medium

| 04:07

変換する文字の種類は総和が最も大きくなるように上からk個選べばよい。

javaだとnew BigInteger(String s , int radix)で指定した基数でのString表現をBigIntegerにできて、そのBigIntegerをtoString(int radix)で指定した基数のString表現に変換できるので非常に簡単。

最初、k種類の文字が全部Zに変わるのではなくて、k個の文字をZに変えると勘違いしていてはまった。

public class HexatridecimalSum {
  BigInteger sum(char carr[][]){
    BigInteger sum = BigInteger.ZERO;
    for(char[] a : carr){
      sum = sum.add(new BigInteger(new String(a) , 36));
    }
    return sum;
  }
  void replaceToZ(char carr[][] , char c){
    for(int i = 0 ; i < carr.length ; i++)
      for(int j = 0 ; j < carr[i].length ; j++)
        if(carr[i][j] == c)
          carr[i][j] = 'Z';
  }
  public String maximizeSum(String[] numbers, int k) {
    char carr[][] = new char[numbers.length][];
    for(int i = 0 ; i < numbers.length ; i++){
      carr[i] = numbers[i].toCharArray();
    }
    for(int i = 0 ; i < k ; i++){
      BigInteger max = BigInteger.ZERO;
      char mc = ' ';
      for(int d = 0 ; d < 36 ; d++){
        char c = '0';
        if(d < 10)c = (char)('0' + d);
        else c = (char)('A' + d - 10);
        char tmp[][] = new char[numbers.length][];
        for(int j = 0 ; j < numbers.length ; j++){
          tmp[j] = carr[j].clone();
        }
        replaceToZ(tmp, c);
        BigInteger s = sum(tmp);
        if(s.compareTo(max) > 0){
          max = s;
          mc = c;
        }
      }
      replaceToZ(carr, mc);
    }
    return sum(carr).toString(36).toUpperCase();
  }
}

2009-01-19

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

WilliamTagWilliamTag2019/02/02 11:26cialis 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

WilliamTagWilliamTag2019/02/02 11:26cialis 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

ArnoldNizArnoldNiz2019/02/05 20:50canada 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>

2009-01-17

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

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