Hatena::Grouptopcoder

tsubosakaの日記

2009-03-08

TCO 09 Round 1 Medium

| 04:05

ネットで順序統計量とか調べると公式が載っているのでそれを実装しただけです。

public class KthProbableElement {
  double fact(int n){
    double res = 1.0;
    for(int i = 1 ; i <= n ; i++)
      res *= i;
    return res;
  }
  public double probability(int M, int lowerBound, int upperBound, int N, int K) {
    double res = 0.0;
    double pi = 1.0 * (N - lowerBound + 1) / (upperBound - lowerBound + 1);
    double pii = 1.0 * (N - lowerBound ) / (upperBound - lowerBound + 1);
    for(int k = K ; k <= M ; k++){
      double cmb = fact(M) / (fact(k) * fact(M - k)); 
      double r = Math.pow(pi , k) * Math.pow(1.0 - pi ,M - k);
      r -= Math.pow(pii , k) * Math.pow(1.0 - pii ,M - k);
      res += r * cmb;
    }
    return res;
  }
}

TCO 09 Round 1 Easy

| 04:01

数列の長さlを固定すると、数列の和は初項をaとしたときに(l * a + (l-1) * l / 2)となる.この値を=Nとおいたときにaが正の整数解となればよい。後はlをLから100まで動かしていけばよい。

  public int[] sequence(int N, int L) {
    for(int len = L ; len <= 100 ; len++){
      int s = (len - 1) * len / 2;
      int d = N - s;
      if(d >= 0){
        if(d % len == 0){
          int a = d / len;
          int res[] = new int[len];
          res[0] = a;
          for(int i = 1 ; i < res.length ; i++)
            res[i] = res[i - 1] + 1;
          return res;
        }        
      }
    }
    return new int[0];
  }

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 Easy

| 18:59

"12!"とか"3!!"などの形式で数字が二つ与えられるので大小比較しろという問題.

!の数が等しければ係数の比較をすればよく,そうでないときは!の数が大きい方を一段階計算して再帰的に比較する.ただ"10000!"とかを計算すると途中でオーバフローするので他方の係数よりも大きくなったときに打ち切る必要があるのと,"0!!"の扱いに気をつける必要がある.

public class ExtraordinarilyLarge {
  class Fact{
    long val;
    long fnum;
    Fact(String str){
      int i = str.indexOf('!');
      if(i < 0){
        val = Long.parseLong(str);
        fnum = 0;
      }else{
        val = Long.parseLong(str.substring(0, i));
        fnum = str.length() - i;
      }
      if(val == 0 && fnum > 0){
        val = 1;
        fnum = 0;
      }
    }
    Fact(long v  , long n){
      val = v; fnum = n;
    }
    long cmp(Fact f){
      if(fnum == f.fnum)
        return val - f.val;     
      if(fnum < f.fnum)return - f.cmp(this);
      long r = 1;
      for(long v = 1 ; v <= val ; v++){
        r *= v;
        if(r > f.val)return 1;
      }
      Fact a = new Fact(r , fnum - 1);
      return a.cmp(f);
    }
  }
  public String compare(String x, String y) {
    Fact fx = new Fact(x);
    Fact fy = new Fact(y);
    long c = fx.cmp(fy);
    System.err.println(c);
    if(c > 0)return "x>y";
    else if(c < 0)return "x<y";    
    return "x=y";
  }
}

2009-01-17

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