ABC005の解答[Java]

はじめに

いつの間にかこのコンテストの問題が全部解けていたので載せようと思います。

では、見ていきましょう。

A - おいしいたこ焼きの作り方

問題文はこちら

xがyの何倍かを求めて上げれば良いですね。
単純に割り算をしてあげれば切り捨て除算になります。

A.java

import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    //x、yの受け取り
    int x = sc.nextInt();
    int y = sc.nextInt();

    //切り捨て除算
    System.out.println(y/x);
  }
}

B - おいしいたこ焼きの食べ方

問題文はこちら

問題文で問われていることを要約すると、$T$の最小値を出力すれば良いとわかるのでそれを求めました。

B.java

import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    //Nの受け取り
    int N = sc.nextInt();
    int min = 1000; //最小値を求める用(大きければ初期値は何でも良い)

    //最小値を探す
    for(int i=0;i<N;i++){
      int temp = sc.nextInt();
      if(min>temp)
        min = temp;
    }

    //答えの出力
    System.out.println(min);
  }
}

C - おいしいたこ焼きの売り方

問題文はこちら

考えたことは、
・あるお客さんに対して、提供するたこ焼きはT秒以内で一番前に作られたものを提供した方が有利そう
・上記の考えだと、一番最初に来たお客さんから順に考えていくと良さそう
といった感じで、A、BそれぞれをArrayDequeに入れて先頭のみ見ることで最適に処理できると考えて処理しました。

C.java

import java.util.Scanner;
import java.util.ArrayDeque;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    //T、Nの受け取り
    int T = sc.nextInt();
    int N = sc.nextInt();

    //AをArrayDequeに
    ArrayDeque<Integer> A = new ArrayDeque<>();
    for(int i=0;i<N;i++)
      A.add(sc.nextInt());

    //Mの受け取り
    int M = sc.nextInt();

    //BをArrayDequeに
    ArrayDeque<Integer> B = new ArrayDeque<>();
    for(int i=0;i<M;i++)
      B.add(sc.nextInt());

    //お客さんに配っていく
    while(B.size()>0){

      //今来たお客さん
      int order = B.pollFirst();

      //条件を満たすたこ焼きが見つかるまで取り出す
      int takoyaki = A.isEmpty()?order+1:A.pollFirst();
      while(takoyaki+T<order)
        takoyaki = A.isEmpty()?order+1:A.pollFirst();

      //条件を満たすものが無かったら終わり
      if(takoyaki>order){
        System.out.println("no");
        return;
      }
    }

    //全員に提供できたらyes
    System.out.println("yes");
  }
}

D - おいしいたこ焼きの焼き方

問題文はこちら

制約が小さいので、$D$に対する二次元累積和を求めておいて、各店員の焼けるたこ焼きの上限に応じた長方形の和の最大値を全探索することで解けました。

D.java

import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    //Nの受け取り
    int N = sc.nextInt();

    //二次元累積和の構築
    int[][] sumD = new int[N+1][N+1];
    for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
        sumD[i][j] = sumD[i-1][j]+sumD[i][j-1]-sumD[i-1][j-1]+sc.nextInt();
      }
    }

    //Qの受け取り
    int Q = sc.nextInt();
    while(Q-->0){

      //Pの受け取り
      int P = sc.nextInt();

      //最大値の全探索
      int max = 0;

      //縦方向の幅を決め打つ
      for(int x=1;x<=N;x++){

        //横幅が求まる
        int y = Math.min(N,P/x);

        //右下の縦方向の座標
        for(int i=x;i<=N;i++){

          //右下の横方向の座標
          for(int j=y;j<=N;j++){
            max = Math.max(max,sumD[i][j]-sumD[i-x][j]-sumD[i][j-y]+sumD[i-x][j-y]);
          }
        }
      }

      //最大値のしゅつりょく
      System.out.println(max);
    }
  }
}