Hatena::Grouptopcoder

tsubosakaの日記

2011-03-25

GCJ Africa and Arabia 2011

| 00:14

GCJJの練習に同様のRegionalのコンテストであるGCJ Africa and Arabia 2011の問題を解いてみた。

http://code.google.com/codejam/contest/dashboard?c=842485#

問題のレベルとしてはSRMの500ぐらいの難易度かなと思った。

A. Vanishing Numbers

数字の消え方がカントール集合の構成方法そのままなので、あたえられた小数を三進小数に変換したときに1が初めに出現する桁の順で並べればよいことがわかる。

実数で計算すると精度の問題が出てくるので有理数クラスを使って計算する。

あと1が出現せず循環する場合だけど、100桁目までみて1がでてこなかったら出てこないと決め打ちで書いたら通ったw

import java.math.BigInteger;
import java.util.*;


public class A {
  static class Frac{
    BigInteger nume;
    BigInteger deno;
    Frac(BigInteger a , BigInteger b){
      nume = a;
      deno = b;
    }
    Frac sub(Frac o){
      return new Frac(nume.multiply(o.deno).subtract(deno.multiply(o.nume)) , deno.multiply(o.deno));
    }
    int comp(Frac o){
      return nume.multiply(o.deno).compareTo(deno.multiply(o.nume));
    }
  }
  //与えられた十進小数を三進小数に変換したときに1が初めに出現する位置を返す
  static int highestOneBit(String val){
    String vnume = val.substring(2);
    while(vnume.length() <= 10){
      vnume = vnume + "0";
    }
    Frac vf = new Frac(new BigInteger(vnume), BigInteger.TEN.pow(11));
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    for(int i = 1 ; i <= 100 ; ++i){
      Frac divpow3 = new Frac(BigInteger.ONE , three.pow(i));
      Frac divpow32 = new Frac(two , three.pow(i));
      if(vf.comp(divpow3) >= 0){
        if(vf.comp(divpow32) > 0){
          vf = vf.sub(divpow32);          
        }else{
          return i;
        }
      }
    }
    return 101;
  }
  static class Pair implements Comparable<Pair>{
    int oneBitPos;
    double val;
    public Pair(int o , double v) {
      oneBitPos = o;
      val = v;
    }
    @Override
    public int compareTo(Pair o) {
      if(oneBitPos == o.oneBitPos){
        return Double.compare(val, o.val);
      }
      return oneBitPos - o.oneBitPos;
    }    
  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      System.out.printf("Case #%d:\n" , cn);
      int N = sc.nextInt();
      Pair ps[] = new Pair[N];
      for(int i = 0 ; i < N ; ++i){
        String s = sc.next();
        ps[i] = new Pair(highestOneBit(s), Double.parseDouble(s));
      }
      Arrays.sort(ps);
      for(int i = 0 ; i < ps.length ; ++i){
        System.out.println(ps[i].val);
      }
    }
  }
}

B. Battlefield

オイラーの定理より、エッジを付け加えたあとの頂点の次数はすべて偶数である必要がある。

グラフが連結であれば、奇点の数/2が答えとなる。

連結でないときは奇点の数が多い連結成分同士をつなぎあわせるという処理を連結成分がひとつになるまで繰り返す。

import java.util.*;

public class B {
  static int dfs(int cp , boolean vis[] , int degree[] , boolean adj[][]){
    if(vis[cp])return 0;
    vis[cp] = true;
    int ret = degree[cp] % 2 == 0 ? 0 : 1;
    for(int i = 0 ; i < vis.length ; ++i){
      if(!adj[cp][i])continue;
      ret += dfs(i , vis , degree , adj);
    }
    return ret;
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      int N = sc.nextInt();
      int R = sc.nextInt();
      int degree[] = new int[N];
      boolean adj[][] = new boolean[N][N];              
      for(int i = 0 ; i < R ; ++i){
        int s = sc.nextInt();
        int t = sc.nextInt();
        degree[s]++;
        degree[t]++;
        adj[s][t] = adj[t][s] = true;
      }
      PriorityQueue<Integer> odds = new PriorityQueue<Integer>(10 , new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
          return o2 - o1;
        }
      });
      boolean vis[] = new boolean[N];
      for(int i = 0 ; i < N ; ++i){
        if(degree[i] == 0 || vis[i])continue;
        odds.add(dfs(i, vis, degree, adj));
      }
      int ret = 0;
      while(odds.size() > 1){
        int o0 = odds.poll();
        int o1 = odds.poll();
        if(o0 > 0 && o1 > 0){
          odds.add(o0 + o1 - 2);
        }else if(o0 == 0){
          odds.add(2);
        }else if(o1 == 0){
          odds.add(o0);
        }
        ++ret;
      }
      ret += odds.poll() / 2;
      System.out.printf("Case #%d: %d\n" , cn , ret);
    }
  }
}

C. Radio Receiver

ラジオの受信距離Dに関して二分探索.

Dを固定して、イベントを起きる時刻が早い順に処理していく。一つ前のイベントまでをすべて受信できる数直線上の位置の範囲を(left,right)とすると現在のイベントeを処理可能な範囲は(left - t , right + t)と(e.pos - D , e.pos + D)のintersectionとなる。(ここでtは現在のイベントと一つ前のイベントの間の時間)

import java.util.*;
public class C {
  static class Event implements Comparable<Event> {
    int pos;
    int time;
    Event(int p, int t) {
      pos = p;
      time = t;
    }
    @Override
    public int compareTo(Event o) {
      return time - o.time;
    }
  }

  static boolean can(double D, Event es[]) {
    double left = es[0].pos - D;
    double right = es[0].pos + D;
    for (int i = 1; i < es.length; ++i) {
      Event e = es[i];
      double t = e.time - es[i - 1].time;
      // intersect (left - t , right + t) and (e.pos - D , e.pos + D)
      left = Math.max(left - t, e.pos - D);
      right = Math.min(right + t, e.pos + D);
      if (left > right)
        return false;
    }
    return true;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int C = sc.nextInt();
    for (int cn = 1; cn <= C; ++cn) {
      int N = sc.nextInt();
      Event es[] = new Event[N];
      for (int n = 0; n < N; ++n) {
        int p = sc.nextInt();
        int t = sc.nextInt();
        es[n] = new Event(p, t);
      }
      Arrays.sort(es);
      double low = 0.0;
      double high = 1.0E9;
      for (int rep = 0; rep < 100; ++rep) {
        double D = (low + high) * 0.5;
        if (can(D, es)) {
          high = D;
        } else {
          low = D;
        }
      }
      System.out.printf("Case #%d: %.9f\n", cn, low);
    }
  }
}