Qualification Round

3問中3問解いて、すべて通った。1問解けば通過なので何事もなければRound 1に進める。スコアボードをみると7000人弱が通過している、つぎのRound 1からRound 2には2520人進める。

追記：各問題のプログラムを貼っておく

A

次にでてくるのが一番遅いクエリを常に選択するというgreedy algorithmで解ける。

import java.util.*;

public class A {
	static int[] next(int seq[] , int from , int S){
		int d[] = new int[S];
		Arrays.fill(d, -1);
		for(int i = from ; i < seq.length ; i++){
			int s = seq[i];
			if(d[s] < 0){
				d[s] = i;
			}
		}
		return d;
	}
	static int choice(int d[]){
		int max = d[0];
		int mp = 0;
		for(int i = 0 ; i < d.length ; i++){
			if(d[i] < 0)return -1;
			if(max < d[i]){
				max = d[i];
				mp = i;
			}
		}
		return mp;
	}
	static int solve(int seq[] , int S){
		int d[] = next(seq, 0 , S);
		int change = 0;
		int engine = choice(d);
		for(int i = 0 ; i < seq.length ; i++){
			int s = seq[i];
			if(s != engine)continue;
			change++;
			d = next(seq , i  , S);
			engine = choice(d);
		}
		return change;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		for(int i = 0 ; i < N ; i++){
			int S = sc.nextInt();
			sc.nextLine();
			Map<String , Integer> engines = new HashMap<String, Integer>();
			for(int j = 0 ; j < S ; j++){
				engines.put(sc.nextLine(), j);				
			}
			int Q = sc.nextInt();
			sc.nextLine();
			int seq[] = new int[Q];
			for(int j = 0 ; j < Q ; j++){
				seq[j] = engines.get(sc.nextLine());
			}
			System.out.printf("Case #%d: %d\n" , (i + 1) , solve(seq, S));
		}
	}
}

B

各駅ごとに電車の発車時刻と到着時刻を時刻順にソートした後、電車の発車時に余っている列車があればそれを使う、なければ新しい電車を増やすという方法で解いた。

import java.util.*;

class Event implements Comparable<Event>{
  final static int DEPART = 1;
  final static int ARRIVE = 0;
  int kind;  
  int time;
  Event(int k , int t){
    kind = k;
    time = t;
  }
  public int compareTo(Event o) {
    if(time == o.time){
      return kind - o.kind;
    }
    return time - o.time;
  }
}
public class B {
  static int toI(String str){
    return Integer.parseInt(str.substring(0, 2)) * 60 
      + Integer.parseInt(str.substring(3));
  }
  public static void main(String[] args) {
    Scanner sc = new  Scanner(System.in);
    int N = sc.nextInt();
    for(int i = 1 ; i<= N ; i++){
      int T = sc.nextInt();
      int na = sc.nextInt();
      int nb = sc.nextInt();
      List<Event> ea = new ArrayList<Event>();
      List<Event> eb = new ArrayList<Event>();
      for(int j = 0 ; j < na ; j++){
        int depart = toI(sc.next());
        int arrive = toI(sc.next());
        ea.add(new Event(Event.DEPART , depart));
        eb.add(new Event(Event.ARRIVE , arrive + T));
      }      
      for(int j = 0 ; j < nb ; j++){
        int depart = toI(sc.next());
        int arrive = toI(sc.next());
        eb.add(new Event(Event.DEPART , depart));
        ea.add(new Event(Event.ARRIVE , arrive + T));
      }
      Collections.sort(ea);
      Collections.sort(eb);
      System.out.printf("Case #%d: %d %d\n" , i , number(ea) , number(eb));
    }
  }
  static int number(List<Event> es){
    int count = 0;
    int stock = 0;
    for(Event e : es){
      if(e.kind == Event.ARRIVE){
        stock++;
      }else{
        if(stock > 0)stock--;
        else count++;
      }
    }
    return count;
  }
}

C

当たらない部分の面積を求めるという方針で解いた。内側の部分の面積は(g-2f)^2ですぐ出るのだけど、正方形と円が交わっている部分の面積の評価が場合分けが多くて煩雑だった。

import java.util.Scanner;

public class C {
  static boolean inCircle(double x , double y , double r){
    return x * x + y * y <= r * r;
  }
  
  static double areaArc(
      double R, 
      double x1, double y1, 
      double x2, double y2) {
    double theta = Math.abs(Math.atan2(y1, x1) - Math.atan2(y2, x2));
    double circle = 0.5 * R * R * theta;
    double tri = 0.5 * Math.abs(x1 * y2 - x2 * y1);
    return circle - tri;
  }
  
  static double areaGap(double x , double y , double g , double f , double r){
    double ux = x + g - f;
    double uy = y + g - f;
    if(!inCircle(x + f, y + f, r)){
      return 0.0;
    }
    if(inCircle(ux ,uy , r)){
      return (g - 2 * f) * (g - 2 * f);
    }
    double safe = 0.0;
    if(inCircle(x + f, uy, r)){
      if(inCircle(ux , y + f, r)){
        double a = Math.sqrt(r * r - uy * uy);
        double b = Math.sqrt(r * r - ux * ux);
        safe += (a - (x + f)) * (uy - (y + f));
        safe += 0.5 * (b + uy - 2 * (y + f)) * (ux - a);
        safe += areaArc(r, a, uy, ux, b);        
      }else{
        double a = Math.sqrt(r * r - uy * uy);
        double b = Math.sqrt(r * r - (y + f) * (y + f));
        safe += 0.5 * (a + b - 2 * (x + f)) * (uy - (y + f));
        safe += areaArc(r, a, uy, b, y + f);        
      }
    }else{
      if(inCircle(ux , y + f, r)){
        double a = Math.sqrt(r * r - (x + f) * (x + f));
        double b = Math.sqrt(r * r - ux * ux);
        safe += 0.5 * (a + b - 2 * (y + f)) * (ux - (x + f));
        safe += areaArc( r , x + f, a, ux, b);        
      }else{
        double a = Math.sqrt(r * r - (x + f) * (x + f));
        double b = Math.sqrt(r * r - (y + f) * (y + f));
        safe += 0.5 * (b - (x + f)) * (a - (y + f));
        safe += areaArc( r , x + f, a, b, y + f);        
      }
    }
    return safe;
  }


  static double solve(double f, double R, double t, double r, double g) {
    if (2 * f >= g) return 1.0;
    if (R - t - f <= 0) return 1.0;
    double safe = 0.0;
    double inRad = R - t;
    for (double x = r; x < inRad; x += (g + 2 * r)) {
      for (double y = r; y < inRad; y += (g + 2 * r)) {
        safe += areaGap(x , y , g , f , inRad - f);
      }
    }
    return 1.0 - 4.0 * safe / (Math.PI * R * R);
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for (int i = 1; i <= N; i++) {
      double f = sc.nextDouble();
      double R = sc.nextDouble();
      double t = sc.nextDouble();
      double r = sc.nextDouble();
      double g = sc.nextDouble();
      System.out.printf("Case #%d: %.6f\n", i, solve(f, R, t, r, g));
    }
  }
}