POH! Vol.1 Java模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。

【POH Vol.1結果発表】新人女子を最も助けたコードとは?

Java: paiza事務局作成コード Vol.4 O(DN)

通過テストケース数:3
実行時間(テストケース1):0.08秒
実行時間(テストケース2):0.10秒
実行時間(テストケース3):0.23秒

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  private static int search(final int n, final int[] p) {
    int price = 0;
    int max = 0;
    int i = 0, j = p.length - 1;
    while (true) {
      price = p[i] + p[j];

      if (price == n) {
        max = n;
        break;
      } else if (price < n && price > max) {
        max = price;
      }

      if (price < n) {
        i++;
      } else if (price > n) {
        j--;
      }

      if (i >= j) {
        break;
      }
    }
    return max;
  }

  public static void main(String[] args) {
    final int N;
    final int D;
    final int[] p;
    final int[] m;

    try (BufferedReader br = new BufferedReader(new InputStreamReader(
        System.in))) {
      String[] line_nd = br.readLine().split(" ");
      N = Integer.valueOf(line_nd[0]);
      D = Integer.valueOf(line_nd[1]);

      p = new int[N];
      for (int i = 0; i < N; i++) {
        p[i] = Integer.valueOf(br.readLine());
      }
      Arrays.sort(p);

      m = new int[D];
      for (int i = 0; i < D; i++) {
        m[i] = Integer.valueOf(br.readLine());
      }

      for (int v : m) {
        System.out.println(search(v, p));
      }
    } catch (Exception e) {
      e.printStackTrace();
    }

  }
}

Java: paiza事務局作成コード Vol.3 O(DNlogN)

通過テストケース数:3
実行時間(テストケース1):0.09秒
実行時間(テストケース2):0.26秒
実行時間(テストケース3):5.58秒

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  private static int search(final int n, final int[] p) {
    int max = 0;
    int mid = 0;
    int tmp = 0;
    for (int i = 0; i < p.length; i++) {
      int r = n - p[i];
      int lb = 0;
      int ub = p.length;
      while (ub - lb != 1) {
        mid = (ub + lb) / 2;
        if (p[mid] <= r) {
          lb = mid;
        } else {
          ub = mid;
        }
      }
      ub -= 1;
      if (i >= ub) continue;
      if (p[ub] > r) continue;
      tmp = p[i] + p[ub];
      if (tmp <= n && max < tmp) {
        max = tmp;
      }
    }
    return max;
  }

  public static void main(String[] args) {

    final int N;
    final int D;
    final int[] p;
    final int[] m;

    try (BufferedReader br = new BufferedReader(new InputStreamReader(
                                                                          System.in))) {
      String[] line_nd = br.readLine().split(" ");
      N = Integer.valueOf(line_nd[0]);
      D = Integer.valueOf(line_nd[1]);

      p = new int[N];
      for (int i = 0; i < N; i++) {
        p[i] = Integer.parseInt(br.readLine());
      }

      Arrays.sort(p);

      m = new int[D];
      for (int i = 0; i < D; i++) {
        m[i] = Integer.parseInt(br.readLine());
      }

      for (int v : m) {
        System.out.println(search(v, p));
      }

    } catch (Exception e) {
      e.printStackTrace();
    }

  }
}

Java: paiza事務局作成コード Vol.2 O(DN^2)

通過テストケース数:2
実行時間(テストケース1):0.10秒
実行時間(テストケース2):3.41秒
実行時間(テストケース3):--

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  private static int search(final int n, final int[] p) {
    int max = 0;

    for (int i = 0; i < p.length; i++) {
      for (int j = i + 1; j < p.length; j++) {
        final int price = p[i] + p[j];
        if (price > n) {
          break;
        } else if (price > max) {
          max = price;
        }
      }
    }

    return max;
  }

  public static void main(String[] args) {

    final int N;
    final int D;
    final int[] p;
    final int[] m;

    try (BufferedReader br = new BufferedReader(new InputStreamReader(
        System.in))) {
      String[] line_nd = br.readLine().split(" ");
      N = Integer.valueOf(line_nd[0]);
      D = Integer.valueOf(line_nd[1]);

      p = new int[N];
      for (int i = 0; i < N; i++) {
        p[i] = Integer.parseInt(br.readLine());
      }

      Arrays.sort(p);

      m = new int[D];
      for (int i = 0; i < D; i++) {
        m[i] = Integer.parseInt(br.readLine());
      }

      for (int v : m) {
        System.out.println(search(v, p));
      }

    } catch (Exception e) {
      e.printStackTrace();
    }

  }
}

Java: paiza事務局作成コード Vol.1 O(DN^2)

通過テストケース数:1
実行時間(テストケース1):0.15秒
実行時間(テストケース2):--
実行時間(テストケース3):--

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

  private static int search(final int n, final int[] p) {
    int max = 0;

    for (int i = 0; i < p.length; i++) {
      for (int j = i + 1; j < p.length; j++) {
        final int price = p[i] + p[j];
        if (price > max && price <= n) {
          max = price;
        }
      }
    }

    return max;
  }

  public static void main(String[] args) {
    final int N;
    final int D;
    final int[] p;
    final int[] m;

    try (BufferedReader br = new BufferedReader(new InputStreamReader(
        System.in))) {
      String[] line_ND = br.readLine().split(" ");
      N = Integer.valueOf(line_ND[0]);
      D = Integer.valueOf(line_ND[1]);

      p = new int[N];
      for (int i = 0; i < N; i++) {
        p[i] = Integer.parseInt(br.readLine());
      }

      m = new int[D];
      for (int i = 0; i < D; i++) {
        m[i] = Integer.parseInt(br.readLine());
      }

      for (int v : m) {
        System.out.println(search(v, p));
      }

    } catch (Exception e) {
      e.printStackTrace();
    }

  }
}
ページの先頭へ戻る