Hatena::Grouptopcoder

tsubosakaの日記

2009-01-14

SRM 250 Div1 Hard

| 20:32

2つの多角形の共通部分の面積を求める問題.O(n + m)の解法もあるけれど,ここでは線分の交差点と一方の多角形に含まれる点をすべて列挙してそれらの点で凸包を構成する.

import java.util.*;

public class ConvexPolygons {
  class Point {
    double x, y;

    Point(double a, double b) {
      this.x = a;
      this.y = b;
    }

    @Override
    public String toString() {
      return x + " : " + y;
    }

    double norm() {
      return x * x + y * y;
    }
  }


  double cross(Point a, Point b, Point c) {
    double res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return res;
  }
  double cmp(Point a , Point b){
    if(a.x != b.x)return a.x - b.x;
    return a.y - b.y;
  }
  List<Point> convexHull(List<Point> ps) {
    List<Point> res = new ArrayList<Point>();
    if(ps.size() < 3)return res;
    int N = ps.size();
    int p = 0;
    for(int i = 1 ; i < N ; i++)
      if(cmp(ps.get(i) , ps.get(p)) < 0)
        p = i;
    int st = p;
    do{
      int n = -1;
      for(int i = 0 ; i < N ; i++){
        if(i == p)continue;
        if(n == -1)n = i;
        double cross = cross(ps.get(p) , ps.get(i) , ps.get(n));
        if(cross < 0)
          n = i;
      }
      res.add(ps.get(p));
      p = n;
    }while(st != p);
    return res;
  }

  double area(List<Point> lst) {
    if(lst.size() < 3)return 0.0;
    double res = 0.0;
    for (int i = 0; i < lst.size(); i++) {
      Point p1 = lst.get(i);
      Point p2 = lst.get((i + 1) % lst.size());
      res += (p1.x - p2.x) * (p1.y + p2.y);
    }
    return Math.abs(res * 0.5);
  }

  boolean include(Point point , Point[] polygon){
    for(int i = 0 ; i < polygon.length ; i++){
      Point a = polygon[i];
      Point b = polygon[(i + 1) % polygon.length];      
      double ccw = cross(point , a , b);
      if(ccw < 0)return false;
    }
    return true;
  }
  Point intersect(Point p1 , Point p2 , Point q1 , Point q2){
    double a1 = p2.y - p1.y;
    double b1 = p1.x - p2.x;
    double c1 = a1 * p1.x + b1 * p1.y;
    double a2 = q2.y - q1.y;
    double b2 = q1.x - q2.x;
    double c2 = a2 * q1.x + b2 * q1.y;
    double det = a1 * b2 - a2 * b1;
    if(det == 0.0){
      return null;
    }else{
      double x = (b2 * c1 - b1 * c2) / det;
      double y = (a1 * c2 - a2 * c1) / det;
      if(inRange(x , p1.x , p2.x) && inRange(x , q1.x , q2.x) &&
         inRange(y , p1.y , p2.y) && inRange(y , q1.y , q2.y)    
          ){
        return new Point(x , y);
      }
      return null;
    }
  }
  boolean inRange(double x , double low , double up){
    if(low > up)return inRange(x , up , low);
    return low <= x && x <= up;
  }
  List<Point> hullPoint(Point[] polygon1 , Point[] polygon2){
    List<Point> res = new ArrayList<Point>();
    for(Point p1 : polygon1){
      if(include(p1, polygon2))
        res.add(p1);
    }
    for(Point p2 : polygon2){
      if(include(p2, polygon1))
        res.add(p2);      
    }
    for(int i = 0 ; i < polygon1.length ; i++){
      for(int j = 0 ; j < polygon2.length ; j++){
        Point a = polygon1[i];
        Point b = polygon1[(i+1) % polygon1.length];
        Point c = polygon2[j];
        Point d = polygon2[(j+1) % polygon2.length];
        Point ip = intersect(a, b, c, d);
        if(ip != null)
          res.add(ip);
      }
    }
    return res;
  }
  double overlap(Point[] polygon1 , Point[] polygon2){
    return area(convexHull(hullPoint(polygon1, polygon2)));
  }
  public double overlap(String[] polygon1, String[] polygon2) {    
    return overlap(toPolygon(polygon1), toPolygon(polygon2));
  }
  Point[] toPolygon(String[] poly){
    Point ps[] = new Point[poly.length];
    for(int i = 0 ; i < ps.length ; i++){
      String p = poly[i];
      String a[] = p.split("\\s+");
      Point pt = new Point(Integer.parseInt(a[0]) , Integer.parseInt(a[1]));
      ps[i] = pt;
    }
    return ps;
  }
}

SRM 250 Div1 Medium

| 20:29

見る番組を一つ定めて,その番組の開始時間を基準とすると循環がなくなるのであとは時刻sからtまでの最大視聴時間dp(s,t)はdp(s , t) = min_{s <= m <= t} dp(s , m) + dp(m , t)と書けることを利用してDP.

import java.util.*;

public class TVWatching {
  int toInt(String time){
    int h = Integer.parseInt(time.substring(0,2));
    int m = Integer.parseInt(time.substring(3,5));
    int res = h * 60 + m;
    if(h == 12){
      if(time.endsWith("AM"))
        res += 720;      
    }else{
      if(time.endsWith("PM"))
        res += 720;
    }
    return res;
  }
  int[] toInts(String program){
    String start = program.substring(0 , 7);
    String end = program.substring(10);
    return new int[]{toInt(start) , toInt(end)};
  }
  int calc(int ps[][]){
    int n = ps.length;
    Set<Integer> set = new TreeSet<Integer>();
    for(int p[] : ps){
      for(int i : p){
        if(i < 0)continue;
        set.add(i);
      }
    }
    int times[] = new int[set.size()];
    int cnt = 0;
    for(int i : set)
      times[cnt++] = i;
    Arrays.sort(times);
    int dp[][] = new int[times.length][times.length];
    for(int i = 0 ; i < n ; i++){
      if(ps[i][0] < 0)continue;
      int s = Arrays.binarySearch(times, ps[i][0]);
      int e = Arrays.binarySearch(times, ps[i][1]);
      dp[s][e] = ps[i][1] - ps[i][0];
    }
    for(int len = 1 ; len < dp.length ; len++){
      for(int i = 0 ; i < dp.length ; i++){
        int j = i + len;
        if(j >= dp.length)continue;
        for(int m = i; m <= j ; m++){
          dp[i][j] = Math.max(dp[i][j], dp[i][m] + dp[m][j]);          
        }
      }
    }
    int max = 0;
    for(int d[] : dp)
      for(int i : d)
        max = Math.max(max, i);
    return max;
  }
  int mostMinutes(int[][] programs){
    int n = programs.length;
    int res = 0;
    for(int i = 0 ; i < n ; i++){
      int ps[][] = new int[n][2];
      int start = programs[i][0];
      int end = programs[i][1] - programs[i][0];
      if(end <= 0)end += 1440;
      for(int j = 0 ; j < n ; j++){
        int st = programs[j][0] - start;
        int ed = programs[j][1] - start;
        if(st <= 0)st += 1440;
        if(ed <= 0)ed += 1440;
        if(st < end || ed < st )
          st = ed = -1;
        ps[j][0] = st; ps[j][1] = ed;
      }
      int r = calc(ps);
      res = Math.max(res, end + r);
    }
    return res;
  }
  public int mostMinutes(String[] programs) {
    int n = programs.length;
    int ps[][] = new int[n][2];
    for(int i = 0 ; i < n ; i++){
      ps[i] = toInts(programs[i]);
      if(ps[i][0] == ps[i][1])
        return 1440;
    }
    return mostMinutes(ps);
  }
}

SRM 250 Div1 Easy

| 20:22

書いてある通りにやるだけ

public class LanguageRecognition {
  int freq(String s , char c){
    int cnt = 0;
    for(char ch : s.toCharArray())
      if(c == ch)
        cnt++;
    return cnt;
  }
  double diff(String a , String b){
    double sum = 0.0;
    for(char c = 'a' ; c <= 'z' ; c++){
      double fa = freq(a , c) * 1.0 / a.length();
      double fb = freq(b , c) * 1.0 / b.length();
      sum += (fa - fb) * (fa - fb);
    }
    return sum;
  }
  String normalize(String str){
    str = str.toLowerCase();
    str = str.replaceAll("[^a-z]", "");
    return str;
  }
  public int whichLanguage(String[] languages, String text) {
    text = normalize(text);
    for(int i = 0 ; i < languages.length ; i++)
      languages[i] = normalize(languages[i]);
    double ds[] = new double[languages.length];
    int res = 0;
    for(int i = 0 ; i < ds.length ; i++){
      ds[i] = diff(languages[i] , text);
      if(ds[i] + 1.0E-11 < ds[res]){
        res = i;
      }
    }
    return res;
  }
}

Topcoder部はじめました

| 19:25

過去問の練習とかをこっちに書くことにする.

SRM 173 Div1 Easy

| 19:25

書いてある通りにやるだけ

public class WordForm {
  public String getSequence(String word) {
    int n = word.length();
    char arr[] = new char[n];
    String vs = "aiueo";
    for(int i = 0 ; i < n ; i++){
      char c = word.charAt(i);
      c = Character.toLowerCase(c);
      if(vs.indexOf(c) >= 0){
        arr[i] = 'V';
      }else if(c == 'y' && i > 0 && arr[i-1] != 'V'){
        arr[i] = 'V';
      }else{
        arr[i] = 'C';
      }
    }
    return shrink(arr);
  }
  String shrink(char arr[]){
    char prev = ' ';
    String res = "";
    for(int i = 0 ; i < arr.length ; i++){
      if(arr[i] != prev){
        res += arr[i];
      }
      prev = arr[i];
    }
    return res;
  }
}

SRM 173 Div1 Medium

| 19:25

すべての開始点の候補から命令列を実行してみて終点を求める.複数ある場合は条件に書いてある通りに選択する.

public class TreasureHunt {
  int[] findX(char map[][]){
    int res[] = new int[2];
    for(int i = 0 ; i < map.length ; i++){
      for(int j = 0 ; j < map[i].length ; j++){
        if(map[i][j] == 'X'){
          res[0] = j;
          res[1] = i;
        }
      }
    }
    return res;
  }
  int[] endPoint(char map[][] , String[] instructions , int sx , int sy){
    int H = map.length;
    int W = map[0].length;
    int x = sx;
    int y = sy;
    for(String instruction : instructions){
      char dir = instruction.charAt(0);
      int paces = instruction.charAt(2) - '0';
      int dx = 0 , dy = 0;
      if(dir == 'N')dy = -1;
      else if(dir == 'S')dy = 1;
      else if(dir == 'E')dx = 1;
      else dx = -1;
      for(int i = 0 ; i < paces ; i++){
        x += dx;
        y += dy;
        if(x < 0 || x >= W)return null;
        if(y < 0 || y >= H)return null;
        if(map[y][x] == '.')return null;        
      }
    }
    return new int[]{x,y};
  }
  boolean isBeach(char map[][] , int x , int y){
    if(map[y][x] == '.')return false;
    int dx[] = {0 , 0 , -1 , 1};
    int dy[] = {1 , -1 , 0 , 0};
    for(int i = 0 ; i < dx.length ; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || nx >= map[0].length)return true;
      if(ny < 0 || ny >= map.length)return true;
      if(map[ny][nx] == '.')return true;
    }
    return false;
  }
  public int[] findTreasure(String[] island, String[] instructions) {
    int H = island.length;
    int W = island[0].length();
    char map[][] = new char[H][W];
    for(int i = 0 ; i < H ; i++)
      map[i] = island[i].toCharArray();
    int X[] = findX(map);
    int[] res = new int[2];
    int mindist = Integer.MAX_VALUE;
    for(int y = 0 ; y < H ; y++){
      for(int x = 0 ; x < W ; x++){
        if(!isBeach(map, x, y))continue;
        int ep[] = endPoint(map, instructions, x, y);        
        if(ep == null)continue;
        int dist = (ep[0] - X[0]) * (ep[0] - X[0]) + (ep[1] - X[1]) * (ep[1] - X[1]);
        if(dist > mindist)continue;
        if(dist < mindist){
          res[0] = ep[0];
          res[1] = ep[1];          
        }else{
          if(ep[1] < res[1]){
            res[0] = ep[0];
            res[1] = ep[1];            
          }else if(ep[1] == res[1]){
            if(ep[0] < res[0]){
              res[0] = ep[0];
              res[1] = ep[1];                          
            }
          }
        }
        mindist = dist;
      }
    }
    if(mindist == Integer.MAX_VALUE)return new int[0];
    return res;
  }
}

SRM 173 Div1 Hard

| 19:25

与えられた点からn個選んだ時に選んだ点の凸包の面積を最大にせよという問題.

  • 候補点は凸包の中から選べばよい
  • 始点を固定した後に、一個前の点と残りの選べる点の個数を状態としてメモ付き探索を行う
  • 再帰式はf(start , p , n) = max_q ( f(start , q , n - 1) + |start-p-q|)と書ける
import java.util.*;

public class ElectronicScarecrows {
  class Point {
    double x, y;

    Point(double a, double b) {
      this.x = a;
      this.y = b;
    }

    @Override
    public String toString() {
      return x + " : " + y;
    }

    double norm() {
      return x * x + y * y;
    }
  }
  double cross(Point a, Point b, Point c) {
    double res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return res;
  }
  double cmp(Point a , Point b){
    if(a.x != b.x)return a.x - b.x;
    return a.y - b.y;
  }
  double dist(Point a , Point b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy;
  }
  List<Point> convexHull(List<Point> ps) {
    List<Point> res = new ArrayList<Point>();
    if(ps.size() < 3)return res;
    int N = ps.size();
    int p = 0;
    for(int i = 1 ; i < N ; i++)
      if(cmp(ps.get(i) , ps.get(p)) < 0)
        p = i;
    boolean used[] = new boolean[N];
    int st = p;
    do{
      int n = -1;
      double dist = 0.0;
      for(int i = 0 ; i < N ; i++){
        if(i == p)continue;
        if(used[i])continue;
        if(n == -1)n = i;
        double cross = cross(ps.get(p) , ps.get(i) , ps.get(n));
        double d  = dist(ps.get(i) , ps.get(p));
        if(cross < 0){
          n = i;
          dist = d;
        }else if(Math.abs(cross) < 1.0E-11){
          if(d > dist){
            dist = d;
            n = i;
          }
        }
      }
      res.add(ps.get(p));
      p = n;
      used[p] = true;
    }while(st != p);
    return res;
  }
  double triarea(Point p0 , Point p1 , Point p2){
    return Math.abs(cross(p0 , p1 , p2)) * 0.5;
  }
  double memo[][];
  Point ps[];
  double rec(int pstart , int prev , int n){
    if(n == 0)return 0.0;
    if(memo[prev][n] >= 0.0)
      return memo[prev][n];
    double res = 0.0;
    int p = (prev + 1) % ps.length;
    while(p != pstart){
      double t = triarea(ps[pstart] , ps[prev] , ps[p]);
      double r = rec(pstart , p , n - 1);
      res = Math.max(res, t + r);
      p = (p + 1) % ps.length;      
    }   
    return memo[prev][n] = res;
  }
  public double largestArea(int[] x, int[] y, int n) {
    List<Point> plist = new ArrayList<Point>();
    for(int i = 0 ; i < x.length ; i++){
      plist.add(new Point(x[i] , y[i]));
    }
    List<Point> hull = convexHull(plist);
    this.ps = hull.toArray(new Point[0]);
    int hs = hull.size();
    double res = 0.0;
    for(int pstart = 0 ; pstart < hull.size() ; pstart++){
      memo = new double[hs][n];
      for(int i = 0 ; i < hs ; i++)
          Arrays.fill(memo[i] , -1);
      for(int p0 = pstart + 1 ; p0 < hs ; p0++){
        double r = rec(pstart , p0  , n - 2);
        res = Math.max(res, r);
      }
    }
    return res;
  }
}

RoberGrotlyRoberGrotly2017/05/08 23:31Amoxicilina Internet Where To Buy Levitra Deezer <a href=http://byuvaigranonile.com>viagra</a> Malegra Amoxicillin Trihydrate 250 Dosage Propecia Zwanger Worden

KennnataKennnata2017/06/19 09:38Order Acticin With Overnight Delivery <a href=http://via100mg.com>Buy Viagra</a> Levitra In Hamburg Letrozole <a href=http://cial40mg.com/buy-cheap-cialis.php>Buy Cheap Cialis</a> Brand Name Propecia Generic Onlineerertiledysfunctionpillss <a href=http://buy-priligy-30mg.priliorder.com>Buy Priligy 30mg</a> Unisom In Singapore