POH! Vol.1 C#模範解答

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

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

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

通過テストケース数:3
実行時間(テストケース1):0.04秒
実行時間(テストケース2):0.05秒
実行時間(テストケース3):0.22秒

using System;

namespace Solution {
  class Solution {

    private static int search(int n, 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) {

        String[] line_nd = System.Console.ReadLine().Trim().Split(' ');
        int N = Int32.Parse(line_nd[0]);
        int D = Int32.Parse(line_nd[1]);

        int[] p = new int[N];
        for (int i = 0; i < N; i++) {
          p[i] = Int32.Parse(System.Console.ReadLine().Trim());
        }
        Array.Sort(p);

        int[] m = new int[D];
        for (int i = 0; i < D; i++) {
          m[i] = Int32.Parse(System.Console.ReadLine().Trim());
        }

        foreach (int v in m) {
          System.Console.WriteLine("{0}", search(v, p));
        }
      }
    }

}

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

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

using System;

namespace Solution {

  class Solution {

    private static int search(int n, 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) {

      String[] line_nd = System.Console.ReadLine().Trim().Split(' ');
      int N = Int32.Parse(line_nd[0]);
      int D = Int32.Parse(line_nd[1]);

      int[] p = new int[N];
      for (int i = 0; i < N; i++) {
        p[i] = Int32.Parse(System.Console.ReadLine().Trim());
      }
      Array.Sort(p);

      int[] m = new int[D];
      for (int i = 0; i < D; i++) {
        m[i] = Int32.Parse(System.Console.ReadLine().Trim());
      }

      foreach (int v in m) {
        System.Console.WriteLine("{0}", search(v, p));
      }
    }
  }

}

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

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

using System;

namespace Solution {

    class Solution {

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

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

        return max;
      }

      public static void Main(String[] args) {

        String[] line_nd = System.Console.ReadLine().Trim().Split(' ');
          int N = Int32.Parse(line_nd[0]);
        int D = Int32.Parse(line_nd[1]);

        int[] p = new int[N];
        for (int i = 0; i < N; i++) {
          p[i] = Int32.Parse(System.Console.ReadLine().Trim());
        }
        Array.Sort(p);

        int[] m = new int[D];
        for (int i = 0; i < D; i++) {
          m[i] = Int32.Parse(System.Console.ReadLine().Trim());
        }

        foreach (int v in m) {
                System.Console.WriteLine("{0}", search(v, p));
        }
      }
    }

}

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

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

using System;

namespace Solution {
    class Solution {

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

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

        return max;
      }

      public static void Main(String[] args) {

        String[] line_nd = System.Console.ReadLine().Trim().Split(' ');
          int N = Int32.Parse(line_nd[0]);
        int D = Int32.Parse(line_nd[1]);

        int[] p = new int[N];
        for (int i = 0; i < N; i++) {
          p[i] = Int32.Parse(System.Console.ReadLine().Trim());
        }

        int[] m = new int[D];
        for (int i = 0; i < D; i++) {
          m[i] = Int32.Parse(System.Console.ReadLine().Trim());
        }

        foreach (int v in m) {
                System.Console.WriteLine("{0}", search(v, p));
        }
      }
    }

}
ページの先頭へ戻る