AOJ 0269 East Windを解く

East Wind | Aizu Online Judge

数週間前　なにこれワカンネ　爆発　幾何ってなんですか

今　あっ　これ長さ測って角度の中か調べるだけやん　やるだけやるだけ

→なんか角度の中かどうかでバグってる
→ラジアンラジアン... degree degree...
→これてきとうに360度プラス　マイナス調べればいいんじゃね
→AC

んんwwwwwww

import java.util.*;
public class Main {
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    while(true) {
      int H = stdIn.nextInt();
      int R = stdIn.nextInt();
      
      if(H == 0 && R == 0) {
        break;
      }
      
      int[] hx = new int[H];
      int[] hy = new int[H];
      for(int i = 0; i < H; i++) {
        hx[i] = stdIn.nextInt();
        hy[i] = stdIn.nextInt();
      }
      
      int U = stdIn.nextInt();
      int M = stdIn.nextInt();
      int S = stdIn.nextInt();
      int du = stdIn.nextInt();
      int dm = stdIn.nextInt();
      int ds = stdIn.nextInt();
      
      int[] ux = new int[U];
      int[] uy = new int[U];
      for(int i = 0; i < U; i++) {
        ux[i] = stdIn.nextInt();
        uy[i] = stdIn.nextInt();
      }
      
      int[] mx = new int[M];
      int[] my = new int[M];
      for(int i = 0; i < M; i++) {
        mx[i] = stdIn.nextInt();
        my[i] = stdIn.nextInt();
      }
      
      int[] sx = new int[S];
      int[] sy = new int[S];
      
      for(int i = 0; i < S; i++) {
        sx[i] = stdIn.nextInt();
        sy[i] = stdIn.nextInt();
      }
      
      int[] w = new int[R];
      int[] a = new int[R];
      for(int i = 0; i < R; i++) {
        w[i] = stdIn.nextInt();
        a[i] = stdIn.nextInt();
      }
      
      //---処理ここから---//
      int[] day = new int[H];
      for(int i = 0; i < R; i++) { //風
        IN:for(int j = 0; j < H; j++) { //家
          //---私の桜が届くか---//
          if(!ReachWind(0,0,hx[j],hy[j],w[i],du,a[i])) {
            continue;
          }
          //---梅---//
          for(int k = 0; k < U; k++) {
            if(ReachWind(ux[k],uy[k],hx[j],hy[j],w[i],du,a[i])) {
              continue IN;
            }
          }
          //---桃---//
          for(int k = 0; k < M; k++) {
            if(ReachWind(mx[k],my[k],hx[j],hy[j],w[i],dm,a[i])) {
              continue IN;
            }
          }
          //---桜---//
          for(int k = 0; k < S; k++) {
            if(ReachWind(sx[k],sy[k],hx[j],hy[j],w[i],ds,a[i])) {
              continue IN;
            }
          }
          day[j]++;
          
          
          
          
        }
      }
      int max = 0;
      for(int i = 0; i < H; i++) {
        if(max < day[i]) {
          max = day[i];
        }
      }
      if(max != 0) {
        boolean tmp = false;
        for(int i = 0; i < H; i++) {
          if(!tmp && max == day[i]) {
            System.out.print((i + 1));
            tmp = true;
          }
          else if(max == day[i]) {
            System.out.print(" " + (i+1));
          }
        }
        System.out.println();
      }
      else {
        System.out.println("NA");
      }
    }
  }
  
  public static boolean ReachWind(int x0, int y0, int x1, int y1, int w, int d, int a) {
    //---長さ---//
    if(Math.sqrt((x0 - x1) * (x0 - x1) + (y0 - y1)*(y0 - y1)) > a) {
      return false;
    }
    
    //---角度(x軸から何度か)---//
    int xlen = x1 - x0;
    int ylen = y1 - y0;
    double angle = Math.atan2(ylen, xlen);
    angle = Math.toDegrees(angle);
    double ue = w + d/2.0;
    double shita = w - d/2.0;
    if(angle >= shita && angle <= ue) {
      return true;
    }
    angle += 360;
    if(angle >= shita && angle <= ue) {
      return true;
    }
    angle -= 1080;
    if(angle >= shita && angle <= ue) {
      return true;
    }
    return false;
    
  }
}

AOJ 0260 Salary for a Plumberを解く

Salary for a Plumber | Aizu Online Judge

これ一ヶ月前の俺だと解けない問題やな
問題文読む
→やるだけやんこれ
繋ぎ手の大きい順にパイプの総和に足していって
それにパイプの本数-足した回数かけるだけやん
→できた

import java.util.*;
class MyComp implements Comparator<Long> {

  public int compare(Long o1, Long o2) {
    if(o1 < o2) {
      return 1; 
    }
    else if(o1 > o2) {
      return -1;
    }
    return 0;
  }
  
}

public class Main {
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    Comparator<Long> c = new MyComp();
    PriorityQueue <Long> queJ= new PriorityQueue <Long> (11,c);
    while (true) {
      int n = stdIn.nextInt();
      if(n == 0) {
        break;
      }
      queJ.clear();
      Long sum = 0L;
      for(int i = 0; i < n; i++) {
        sum += stdIn.nextLong();
      }
      for(int i = 0; i < n-1; i++) {
        queJ.add(stdIn.nextLong());
      }
      Long max = 0L;
      for(int i = 0; i < n; i++) {
        if(max < sum *(n-i)) {
          max = sum * (n-i);
        }
        if(i < n - 1) {
          sum += queJ.poll();
        }
      }
      System.out.println(max);
      
      
    }
  }
}

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0260

AOJ 0594 Super Metropolisを解く

なんやこれ..幅探索か...?
いやそんなわけないやろ...

適当に脳みそでやってみるか...

あっ斜め道路通ってないところは差の絶対値の和で
通ってるところは差の絶対値のどっちか大きいほうやな

→実装

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
  
public class Main {

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    int w = stdIn.nextInt();
    int h = stdIn.nextInt();
    int n = stdIn.nextInt();
    
    int nowx = stdIn.nextInt();
    int nowy = stdIn.nextInt();
    int counter = 0;
    for(int i = 1; i < n; i++) {
      int tox = stdIn.nextInt();
      int toy = stdIn.nextInt();
      if((nowx > tox && nowy < toy) || (nowx < tox && nowy > toy)) {
        counter += Math.abs(nowx - tox) + Math.abs(nowy - toy);
      }
      else {
        counter += Math.max(Math.abs(nowx - tox), Math.abs(nowy - toy));
      }
      nowx = tox;
      nowy = toy;
    }
    System.out.println(counter);
  }

}

蟻本 P.60 01ナップサック問題その2

評価対象を変える...?
理解理解
→いきなり漸化式でやろうとする
できない
→メモ化再帰してかんがえる
できた。

import java.util.Scanner;
public class Main {
  static int n;
  static int[] w;
  static int[] v;
  static int W;
  static int[][] dp;
  static int INF = 999999999;
  static int V;
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    n = stdIn.nextInt();
    w = new int[n];
    v = new int[n];
    for(int i = 0; i < n; i++) {
      w[i] = stdIn.nextInt();
      v[i] = stdIn.nextInt();
    }
    W = stdIn.nextInt();
    V = 0;
    for(int i = 0; i < n; i++) {
      V += v[i];
    }
    
    
    dp = new int[n+1][V+1];
    for(int i = 0; i <= n; i++) {
      for(int j = 1; j <= V; j++) {
        dp[i][j] = INF;
      }
    }
    int ans = INF;
    sorv();
    for(int i = V; i >= 0; i--) {
      if(dp[0][i] <= W) {
        ans = i;

        break;
      }
      System.out.println(dp[0][i]);
    }
    System.out.println(ans);
  }

  static void sorv() {
    for(int i = n-1; i >= 0; i--) {
      for(int j = 0; j <= V; j++) {
        if(j < v[i]) {
          dp[i][j] = dp[i+1][j];
        }
        else {
          int c1 = dp[i+1][j];
          int c2 = dp[i+1][j-v[i]]+ w[i];
          dp[i][j] = (c1 < c2)?c1:c2;
        }
        
      }
    }
  }


}

蟻本 P.58 個数制限なしナップサック問題

わけがわからない
→解説読む
わけがわからない
→解説読む
わけがわからない
→お風呂入る
わかる

import java.util.Scanner;
public class Main {
  static int n;
  static int[] w;
  static int[] v;
  static int W;
  static int[][] dp;
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    n = stdIn.nextInt();
    w = new int[n];
    v = new int[n];
    for(int i = 0; i < n; i++) {
      w[i] = stdIn.nextInt();
      v[i] = stdIn.nextInt();
    }
    W = stdIn.nextInt();
    
    dp = new int[n+1][W+1];
    int ans = sorv();
    System.out.println(ans);
  }
  
  static int sorv() {
    for(int i = n-1; i >= 0; i--) {
      for(int j = 0; j <= W; j++) {
        if(j - w[i] < 0) {
          dp[i][j] = dp[i+1][j];
        }
        else {
          int c1 = dp[i+1][j];
          int c2 = dp[i][j-w[i]] + v[i];
          dp[i][j] = (c1 < c2)?c2:c1;
        }
      }
    }
    
    return dp[0][W];
  }


}

蟻本 P.56 最長共通部分列問題を解く

→とりあえずメモ化再帰してみよう。
できた。
→漸化式漸化式...
できた。

import java.util.Scanner;
public class Main {
  static int n;
  static int m;
  static String s;
  static String t;
  static int[][] dp;
  static int[][] dp0;
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    int K = stdIn.nextInt();
    for(int ii = 0; ii < K; ii++) {
      String sS = stdIn.next();
      String tS = stdIn.next();
    
      n = sS.length();
      m = tS.length();
      s = sS;
      t = tS;
      dp = new int[n+1][m+1];
      dp0 = new int[n+1][m+1];
    
      for(int i = 0; i < n+1; i++) {
        for(int j = 0; j < m+1; j++) {
          dp[i][j] = -1;
        }
      }
      
      int ans = sorv(0,0);
      System.out.println(ans); //メモ化再帰
      ans = sorv();
      System.out.println(ans); //動的計画法
    }
  }
  
  //--- メモ化再帰 ---//
  static int sorv(int i, int p) {
    if(dp[i][p] != -1) return dp[i][p];
    if(i == n || p == m) {
      return 0;
    }
    int tmp = t.indexOf(Character.toString(s.charAt(i)), p);
    int c0 = 0;
    int c1 = 0;
    if(tmp >= 0) {
      c0 = sorv(i+1,tmp+1)+1;
      c1 = sorv(i+1,p);
    }
    int c2 = sorv(i+1,p);
    
    int max = c0;
    if(max < c1) max = c1;
    if(max < c2) max = c2;
    
    dp[i][p] = max;
    return max;
    
  }
  //--- 動的計画法 ---//
  static int sorv() {
    for(int i = n-1; i >= 0; i--) {
      for(int j = 0; j < m; j++) {
        int tmp = t.indexOf(Character.toString(s.charAt(i)), j);
        if(tmp < 0) dp0[i][j] = dp0[i+1][j];
        else {
          int c0 = dp0[i+1][j];
          int c1 = dp0[i+1][tmp+1]+1;
          dp0[i][j] = (c0 < c1)?c1:c0;
        }
      }
    }
    return dp0[0][0];
  }

}

近況 パソコン甲子園まであと1ヶ月くらい

全く進歩がない。