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

JospehmoilaJospehmoila2019/01/30 07:27buy cialis in mexico
cialis without a rx
buy cialis with dapoxetine online
cialis sin receta medica

best cialis online order
cialis original brand name sale
buy cialis online scams
cialis from canada with a prescription
https://stowe365.com/#Buy-Cialis-20-mg

JospehmoilaJospehmoila2019/01/30 16:30cialis thailand buy
typical cialis prescription
order cheap cialis
canadian pharmacy cialis 20mg

cialis super active 20mg pills
swiss medical cialis
cialis for women free sample
z 14 order cialis super active online
https://stowe365.com/#Buy-Cialis

JospehmoilaJospehmoila2019/01/31 01:32canadian brand label cialis
bay cialis fast shipping
cialis 20 mg effects
cialis for sale without prescription

buy cialis in nigeria
cialis purchace on line fast no rx
genuine brand name cialis
buy cialis soft tabs information
https://stowe365.com/#Buy-Cialis

JospehmoilaJospehmoila2019/01/31 11:59what is correct dosage for cialis
do broken cialis work
current price of cialis
cialis discount paris

cialis hearing loss
bootleg cialis
acquisto online cialis originale
rui products cialis review
https://stowe365.com/#Buy-Cialis

JospehmoilaJospehmoila2019/01/31 23:26real cialis canadian pharmacy
cialis tablets for sale
dove posso acquistare cialis online
best buy cialis online

cialis kanada
5mg daliy cialis reviews
high price of cialis
cialis experience
https://stowe365.com/#Buy-Cialis-20-mg

JospehmoilaJospehmoila2019/02/01 13:50cialis online.com
once a day cialis cheap
generic cialis 99cents
best place to buy cialis online reviews

get a prescription to buy brand cialis
cialis drug information
lloyds pharmacy cialis price
usa overnight pharmacy cialis
https://stowe365.com/#Buy-Cialis-20-mg

DavidtogDavidtog2019/02/02 23:43cialis online apotheke
cheap generic female cialis
<a href="http://kaivanrosendaal.com/">cialis vs viagra</a>
cialis 20 mg coupon
buy cialis chennai
<a href=http://kaivanrosendaal.com>cialis purchasing</a>
rite aid pharmacy cialis
online apotheke cialis kaufen
http://kaivanrosendaal.com/#Buy-Cheap-Cialis-Online

DavidtogDavidtog2019/02/03 08:52cialis tienda online
brand name cialis online
<a href="http://kaivanrosendaal.com">cialis from canada</a>
cialis_2.5_mg_online
selling cialis on craigslist
<a href=http://kaivanrosendaal.com/>cialis tadalafil</a>
cheap cialis extra strength
best place to buy cialis online yahoo
http://kaivanrosendaal.com/#cialis-canada

DavidtogDavidtog2019/02/03 23:29purchase cialis in south africa
men's health online cialis
<a href="http://kaivanrosendaal.com">cialis coupons printable</a>
cialis prescription dosage
cialis forums
<a href=http://kaivanrosendaal.com/>cialis generic availability</a>
is generic cialis legal
prescription cost for cialis
http://kaivanrosendaal.com/#Buy-Cheap-Cialis

DavidtogDavidtog2019/02/04 07:44cialis professional vs regular cialis
apotheke_cialis_schweiz
<a href="http://kaivanrosendaal.com/">Buy Cheap Cialis</a>
comprare il cialis online
cialis soft online kaufen
<a href=http://kaivanrosendaal.com/>what is cialis</a>
cialis effectiveness review
rayh health care cialis
http://kaivanrosendaal.com/#cialis-for-daily-use

DavidtogDavidtog2019/02/04 18:06import cialis
cialis no prescription montreal
<a href="http://kaivanrosendaal.com">cialis for daily use</a>
cialis commercial actor
buy cialis forum
<a href=http://kaivanrosendaal.com>cialis reviews</a>
cialis.60mg.sale
purchase cialis for daily use online
http://kaivanrosendaal.com/#200-cialis-coupon

DavidtogDavidtog2019/02/05 18:04costco price for cialis
cialis e-shops europe
<a href="http://kaivanrosendaal.com">Buy Cheap Cialis Online</a>
cialis von lilly
buy cialis with no perscription
<a href=http://kaivanrosendaal.com/>cialis manufacturer coupon</a>
cialis online singapore
canada law on cialis prescription
http://kaivanrosendaal.com/#cialis-prices

DavidtogDavidtog2019/02/06 03:19cialis black no prescription
buy cialis 10mg australia
<a href="http://kaivanrosendaal.com">discount cialis</a>
buy cialis online with discover card
cialis generico farmacia italiana
<a href=http://kaivanrosendaal.com>online cialis</a>
cialis no prescription needed canada
buy cialis in florida
http://kaivanrosendaal.com/#cialis-coupon

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

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