Hatena::Grouptopcoder

gnarl,TopCoder

2010-02-20

Topcoder SRM 462 Div2

00:14

http://www.topcoder.com/stat?c=coder_room_stats&rd=14147&cr=22717385

250: Archery

問題

In archery, you shoot an arrow at a target and you get some number of points depending on where the arrow hits the target. In this problem, the target is a circle divided into N concentric rings and a central circle. The width of each ring and the radius of the central circle are equal. The point values assigned to each section of the target are given in the int[] ringPoints. The values are given in order, from innermost to outermost section, so ringPoints[0] is the number of points you get for hitting the central circle, and ringPoints[N] is the number of points you get for hitting the outermost ring.

You are a beginning archer. Whenever you take a shot, the arrow always lands somewhere on the target, but it hits a random point, and all points on the target have an equal probability of being hit. Return the expected point value of your shot.

同じ幅の同心円で区切られた的に矢を射る。矢は的の上のランダムな位置に刺さる。それぞれの領域の点数が与えられたとき、得点の期待値を求めよ。


回答

各領域の点数*領域が全体に占める割合、の和。passed system test。

public class Archery {

  public double expectedPoints(int N, int[] ringPoints) {
    final double o = c(N);
    double p = 0.0;
    for (int n = 0; n <= N; n++) {
      p += f(n) / o * ringPoints[n];
    }
    return p;
  }

  private double f(int n) {
    if (n == 0)
      return c(0);
    return c(n) - c(n - 1);
  }

  private double c(int n) {
    return 2.0 * Math.PI * Math.pow(1 + n, 2);
  }

}

500: AgeEncoding

問題

Your friend's birthday is approaching, and he wants his age to be written in candles on his cake. In fact, he has already placed several candles on the cake. The candles are arranged in a single row, and there are two different colors of candles. One color represents the digit '0' and the other color represents the digit '1'. You don't want to relayout the candles from scratch, so you have to determine if there's a base for which the existing candles spell out your friend's age. To simplify the task, you can choose any strictly positive base, not necessarily an integer one.

For example, if the candles are "00010" and your friend's age is 10, then the candles spell out 10 in base 10 (decimal). If the candles are "10101" and your friend's age is 21, then you can say that "10101" is 21 in base 2 (binary). If the candles are "10100" and your friend's age is 6, then the candles spell out 6 in base sqrt(2)=1.41421356237.... Note that you are not allowed to rotate the cake, so "10" cannot be read as "01".

You are given a String candlesLine, where the i-th character is the digit ('0' or '1') represented by the i-th candle in the row of candles on the cake. You are also given an int age, which is your friend's age. Return the positive base for which the candles represent your friend's age. If there is no such base, return -1, and if there are multiple such bases, return -2.

0/1の列と1から100までの数字が与えられる。列をn進数で解釈すれば数字と一致するならそのnを(整数でなくていい)、該当がなければ-1を、複数の正解があるなら-2を返せ。

回答

複数の正解がありうるのはage=1 && candlesLine="0*1"のときだけ。

解が存在しないのはcandlesLine="0+" && age!=0のときだけ

その他の場合は基数をバイナリサーチ。

public class AgeEncoding {
 
  public double getRadix(int age, String candlesLine) {
	// この条件まちがってますね!!!!!! 先頭の0を除去してない
    if (age == 1 && candlesLine.length() == 1
        && candlesLine.charAt(0) == '1')
      return -2.0;
    final boolean[] digits = parse(candlesLine);
    if (digits.length == 0)
      return age == 1 ? 0.0 : -1.0; // you can choose STRICTLY POSITIVE baseってあるからこれおかしいですね
    if (digits.length == 1 && age != 1)
      return -1;
 
    System.out.println(age + " " + candlesLine);
    return find(age, digits, 0.0, 100, 0);
  }
 
  private final double EPS = 1e-9;
 
  private double find(int age, boolean[] digits, double low, double high,
      int n) {
    if (n > 100)
      return -1;
    final double cur = low + (high - low) / 2.0;
    double val = 0.0;
    double b = 1.0;
    for (boolean d : digits) {
      if (d)
        val += b;
      b *= cur;
    }
    System.out.println("(" + low + ", " + high + ") " + val);
    if (Math.abs(age - val) < EPS)
      return cur;
    else if (val < age)
      return find(age, digits, cur, high, n + 1);
    else
      return find(age, digits, low, cur, n + 1);
  }
 
  private boolean[] parse(String line) {
    final int left = line.indexOf('1');
    if (left == -1)
      return new boolean[0];
    final int size = line.length() - left;
    final boolean[] result = new boolean[size];
    for (int i = 0; i < size; i++)
      result[i] = line.charAt(line.length() - 1 - i) == '1';
    return result;
  }
 
}

チャレンジに成功されて死亡(age=1,candlesLine="000000001")……

基本的な考え方はあってたとおもうけど条件チェックがひどかった。

lyslys2010/02/20 02:51candlesLine="11" && age=1みたいなときも解なしです
結構皆これでやられたみたいです

2008-12-05

SRM 428 div2

18:22

1000点問題(the dictionary)

n,m,kが与えられ、"a"がn個、"z"がm個で構成された文字を辞書順にソートしたk番目を返す関数find(n,m,k)を作る。

文字の組み合わせを返す関数count(n,m)があれば、find(n,m,k)はkの値によって"a"+find(n-1,m,k)か"z"+find(n,m-1,k-count(n,m))に縮小できるのでこうなる。

import java.util.*; 
public class TheDictionary { 
  private static final int memo[][]; 
  private static final int MAX=100+1; 
  static { 
    memo=new int[MAX][]; 
    for(int i=1;i<MAX;i++) memo[i]=new int[MAX]; 
    for(int i=1;i<MAX;i++) { 
      memo[i][1]=i+1; 
      memo[1][i]=i+1; 
    } 
  } 
  private int count(int n,int m) { 
    if(memo[n][m]==0) { 
      memo[n][m]=count(n-1,m)+count(n,m-1); 
    } 
    return memo[n][m]; 
  } 
  private String rep(String s,int n) { 
    if(n < 0) throw new RuntimeException("n<0:"+n); 
    String result=""; 
    for(int i=0;i<n;i++) result+=s; 
    return result; 
  } 
    public String find(int n, int m, int k) { 
      if(n==1) { 
        return rep("z",k-1)+"a"+rep("z",m-k+1); 
      } else if(m==1) { 
        return rep("a",n-k+1)+"z"+rep("a",k-1); 
      } else { 
        final int total=count(n,m); 
        if(total < k) return ""; 
        final int c=count(n-1,m); 
        if(k <= c) { 
          return "a"+find(n-1,m,k); 
        } else { 
          return "z"+find(n,m-1,k-c); 
        } 
      } 
    } 
}

……というのを1時間くらいかけて作ったらチャレンジで撃墜されて死亡。うーむ。

250点問題はOpenしたものの時間切れ。

スコアが順調に下がっていく……(涙)

2008-11-07

SRM 424、Div2

16:44

500点問題

Nが与えられたとき、すべての桁(10進表記)を掛けた値がNになるようなXを求める

    public int smallestNumber(int N) {
    	if(N==1) return 1;
    	int digits=0;
    	int n=N;
    	for(int i=9;i>1;i--) {
    		while(n%i==0) {
    			n/=i;
    			digits++;
    		}
    	}
    	if(n!=1) return -1;
    	else return digits;
    }

900点問題

都市間の接続情報を元に、プライオリティの高い道をM本選ぶ。

都市ごとの選択した道路が接続されている数の配列を返す。

途中で問題に補足が入った!びっくり!

結果の道路集合には任意の二都市をつなぐ経路がなくてはならないらしい。

    public int[] numberOfRoads(String[] roads, int M) {
    	final int cities=roads.length;
    	final int[] nor=new int[cities];
    	final char[][] r=new char[cities][];
    	for(int i=0;i<cities;i++)
    		r[i]=roads[i].toCharArray();
    	int selected=0;
    	loop: for(int i=0;i<cities;i++) {
    		for(int j=i+1;j<cities;j++) {
    			if(r[i][j]=='Y') {
    				nor[i]++;
    				nor[j]++;
    				selected++;
    				r[i][j]='S';
    				r[j][i]='S';
    			}
    			if(M <= selected) break loop;
    		}
    	}
    	for(int i=1;i<cities;i++) {
    		for(int j=0;j<cities;j++)
    			if(r[i][j]=='S') r[0][j]='S';
    	}
    	for(int i=0;i<cities;i++) if(r[0][i]!='S')
    		return new int[0];
    	if(selected < M) return new int[0];
    	else return nor;
    }

と書いては見たものの撃墜された!

まず結果に任意の二都市をつなぐ経路が存在するかどうか判定するロジックがおかしい、そして制約に違反した場合即エラーじゃなく別の組み合わせを調べるべきだった。

この問題は同室の全員が撃墜されてましたね

ratig: 1020→986(涙)