AOJ 0201 Wrought Gold Masterを解く

Wrought Gold Master | Aizu Online Judge

はいはいDFSDFS　ご注文はDFSですか〜wwwwww

→RE

は？なんでとおらねえのこれ

returnの値0にしとこwwwwたぶんそこらへんだwwwww

→AC

通ったwwwwwwwww

import java.util.*;
public class Main {
  public static int[][] typeitem;
  public static int[] itemval;
  public static int[] val;
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    while (true) {
      int n = stdIn.nextInt();
      if(n == 0) {
        break;
      }
      String[] AT = new String[n]; //アイテム名とIDの対応の格納
      val = new int[n]; //各IDの価格
      typeitem = new int[n][0];
      for(int i = 0; i < n; i++) {
        String tmp22 = stdIn.next();
        AT[i] = tmp22;
        val[search(AT,tmp22)] = stdIn.nextInt(); 
      }
      
      int suma = stdIn.nextInt();
      
      for(int i = 0; i < suma; i++) {
        int idx0 = search(AT,stdIn.next());
        int nums = stdIn.nextInt();
        typeitem[idx0] = new int[nums];
        for(int j = 0; j < nums; j++) {
          typeitem[idx0][j] = search(AT,stdIn.next());
        }
      }
      int seaID = search(AT,stdIn.next());
      
      int ans = dfs(seaID);
      
      System.out.println(ans);
    }
    
    
    
    
  }
  
  public static int search(String[] id, String tmp) {
    for(int i = 0; i < id.length; i++) {
      if(id[i].equals(tmp)) {
        return i;
      }
    }
    return 0; //-1だと何故か通らない　よくわからない。
  }
  
  public static int dfs(int id) {
    int ALc = 0;
    if(typeitem[id].length == 0) {
      return val[id]; 
    }
    for(int i = 0; i < typeitem[id].length; i++) {
      ALc += dfs(typeitem[id][i]);
    }
    
    if(val[id] > ALc) {
      return ALc;
    }
    return val[id];
  }
}

AOJ 0200 Traveling Alone: One-way Ticket of Youthを解く

Traveling Alone: One-way Ticket of Youth | Aizu Online Judge

はいはいワーシャルフロイドワーシャルフロイド（覚えたばっかりのアルゴリズムを言いたくなる症候群）

→WA

は？

あ　ループがなんかおかしい

→AC

んんwwwwwww

経由地　出発地　目的地　の順のループですな

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    while(true) {
      int n = stdIn.nextInt();
      int m = stdIn.nextInt();
      
      if(n == 0 && m == 0) {
        break;
      }
    
      int[][] cost = new int[m+1][m+1];
      int[][] time = new int[m+1][m+1];
    
      for(int i = 0; i < m+1; i++) {
        for(int j = 0; j < m+1; j++) {
          cost[i][j] = 1000000000;
          time[i][j] = 1000000000;
          if(i == j) {
            cost[i][j] = 0;
            time[i][j] = 0;
          }
        }
      }
    
      for(int i = 0; i < n; i++) {
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();
        int costA = stdIn.nextInt();
        int timeA = stdIn.nextInt();
      
        cost[a][b] = costA;
        cost[b][a] = costA;
      
        time[a][b] = timeA;
        time[b][a] = timeA;
      }
    
      for(int k = 0; k < m+1; k++) {
        for(int i = 0; i < m+1; i++) {
          for(int j = 0; j < m+1; j++) {
            cost[i][j] = Math.min(cost[i][j], cost[i][k]+cost[k][j]);
            time[i][j] = Math.min(time[i][j], time[i][k] + time[k][j]);
          }
        }
      }
    
      int k = stdIn.nextInt();
    
      for(int i = 0; i < k; i++) {
        int p = stdIn.nextInt();
        int q = stdIn.nextInt();
        int r = stdIn.nextInt();
      
        if(r == 0) {
          System.out.println(cost[p][q]);
        }
        else {
          System.out.println(time[p][q]);
        }
      
      }
    
    }
    
  }
}

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];
  }


}