AtCoder Beginner Contest 032

Submission #959296

Source codeソースコード

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.IntStream;

public class Main {
  int n, W;
  int[] v;
  int[] w;

  void run() {
    n = ni();
    W = ni();
    v = new int[n];
    w = new int[n];
    int maxv = 0;
    int maxw = 0;
    for (int i = 0; i < n; ++i) {
      v[i] = ni();
      w[i] = ni();

      maxv = Math.max(maxv, v[i]);
      maxw = Math.max(maxw, w[i]);
    }
    if (n <= 30) {
      solve1();
    } else if (maxv <= 1000) {
      solve2();
    } else if (maxw <= 1000) {
      solve3();
    } else {
      int d = 0 / 0;
    }
  }

  long dfs(int i, long sumv, long sumw) {
    if (sumw > W) {
      return 0;
    }
    if (i == n) {
      return sumv;
    }
    return Math.max(
        dfs(i + 1, sumv + v[i], sumw + w[i]),
        dfs(i + 1, sumv, sumw)
    );
  }

  void solve1() {
    long sumv = IntStream.of(v).mapToLong(Long::valueOf).sum();
    long sumw = IntStream.of(w).mapToLong(Long::valueOf).sum();
    if (sumw <= W) {
      System.out.println(sumv);
      return;
    }
    System.out.println(dfs(0, 0, 0));
  }

  void solve2() {
    int sumv = IntStream.of(v).sum();
    long[] dp = new long[sumv + 1];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = sumv; 0 <= j; --j) {
        if (dp[j] == Long.MAX_VALUE) {
          continue;
        }
        dp[j + v[i]] = Math.min(dp[j + v[i]], dp[j] + w[i]);
      }
    }
    for (int i = sumv; 0 <= i; --i) {
      if (dp[i] <= W) {
        System.out.println(i);
        return;
      }
    }
  }

  void solve3() {
    int sumw = IntStream.of(w).sum();
    long[] dp = new long[sumw + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = sumw; 0 <= j; --j) {
        if (dp[j] == -1) {
          continue;
        }
        dp[j + w[i]] = Math.max(dp[j + w[i]], dp[j] + v[i]);
      }
    }
    long max = 0;
    for (int i = sumw; 0 <= i; --i) {
      if (i > W) {
        continue;
      }
      max = Math.max(max, dp[i]);
    }
    System.out.println(max);
  }

  Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    new Main().run();
  }

  int ni() {
    return Integer.parseInt(sc.next());
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }

  class BIT<T> {
    int n;
    ArrayList<T> bit;
    BiFunction<T, T, T> bif;

    /**
     * 1-indexed なBinary Indexed Treeを構築する
     *
     * @param n   容量
     * @param bif 適用させる関数
     * @param sup 初期値
     */
    BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
      this.n = n;
      bit = new ArrayList<>(n + 1);
      for (int i = 0; i < n + 1; ++i) {
        bit.add(sup.get());
      }
      this.bif = bif;
    }

    /**
     * iの位置の値をvで更新する
     *
     * @param i index
     * @param v 新しい値
     */
    void update(int i, T v) {
      for (int x = i; x <= n; x += x & -x) {
        bit.set(x, bif.apply(bit.get(x), v));
      }
    }

    /**
     * クエリー
     *
     * @param defaultValue 初期値
     * @param i            index
     * @return [1, i]までfを適用した結果
     */
    T reduce(T defaultValue, int i) {
      T ret = defaultValue;
      for (int x = i; x > 0; x -= x & -x) {
        ret = bif.apply(ret, bit.get(x));
      }
      return ret;
    }
  }

  long MOD = 1_000_000_007;

  /**
   * 繰り返し2乗法を用いたべき乗の実装
   *
   * @return a^r (mod 1,000,000,007)
   */
  long pow(long a, long r) {
    long sum = 1;
    while (r > 0) {
      if ((r & 1) == 1) {
        sum *= a;
        sum %= MOD;
      }
      a *= a;
      a %= MOD;
      r >>= 1;
    }
    return sum;
  }

  /**
   * 組み合わせ
   * O(n)
   *
   * @return {}_nC_r
   */
  long C(int n, int r) {
    long sum = 1;
    for (int i = n; 0 < i; --i) {
      sum *= i;
      sum %= MOD;
    }
    long s = 1;
    for (int i = r; 0 < i; --i) {
      s *= i;
      s %= MOD;
    }
    sum *= pow(s, MOD - 2);
    sum %= MOD;

    long t = 1;
    for (int i = n - r; 0 < i; --i) {
      t *= i;
      t %= MOD;
    }
    sum *= pow(t, MOD - 2);
    sum %= MOD;

    return sum;
  }

  double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;

  /**
   * 黄金分割探索
   *
   * @param left  下限
   * @param right 上限
   * @param f     探索する関数
   * @param comp  上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)
   *              下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()
   * @return 極値の座標x
   */
  double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
    double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
    double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
    double d1 = f.apply(c1);
    double d2 = f.apply(c2);
    while (right - left > 1e-9) {
      if (comp.compare(d1, d2) > 0) {
        right = c2;
        c2 = c1;
        d2 = d1;
        c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
        d1 = f.apply(c1);
      } else {
        left = c1;
        c1 = c2;
        d1 = d2;
        c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
        d2 = f.apply(c2);
      }
    }
    return right;
  }

  /**
   * [a,b]をm:nに内分する点を返す
   */
  double divideInternally(double a, double b, double m, double n) {
    return (n * a + m * b) / (m + n);
  }

  long gcd(long a, long b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  int gcd(int a, int b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  long lcd(long a, long b) {
    return (a / gcd(a, b)) * b;
  }

  int lcd(int a, int b) {
    return (a / gcd(a, b)) * b;
  }

  /**
   * http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
   */
  static class FastScanner {
    private final InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(InputStream in) {
      this.in = in;
    }

    private boolean hasNextByte() {
      if (ptr < buflen) {
        return true;
      } else {
        ptr = 0;
        try {
          buflen = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (buflen <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    public boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    public long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }
  }
}

Submission

Task問題 D - ナップサック問題
User nameユーザ名 arukuka
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 8327 Byte
File nameファイル名
Exec time実行時間 490 ms
Memory usageメモリ使用量 30448 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask00_sample_1.txt,subtask00_sample_2.txt,subtask00_sample_3.txt,subtask00_sample_4.txt
Subtask1 34 / 34 subtask01_0.txt,subtask01_1.txt,subtask01_10.txt,subtask01_11.txt,subtask01_12.txt,subtask01_13.txt,subtask01_14.txt,subtask01_2.txt,subtask01_3.txt,subtask01_4.txt,subtask01_5.txt,subtask01_6.txt,subtask01_7.txt,subtask01_8.txt,subtask01_9.txt,subtask00_sample_1.txt,subtask00_sample_2.txt,subtask00_sample_3.txt,subtask00_sample_4.txt
Subtask2 33 / 33 subtask02_0.txt,subtask02_1.txt,subtask02_10.txt,subtask02_11.txt,subtask02_12.txt,subtask02_13.txt,subtask02_14.txt,subtask02_2.txt,subtask02_3.txt,subtask02_4.txt,subtask02_5.txt,subtask02_6.txt,subtask02_7.txt,subtask02_8.txt,subtask02_9.txt,subtask00_sample_1.txt,subtask00_sample_3.txt
Subtask3 33 / 33 subtask03_0.txt,subtask03_1.txt,subtask03_10.txt,subtask03_11.txt,subtask03_2.txt,subtask03_3.txt,subtask03_4.txt,subtask03_5.txt,subtask03_6.txt,subtask03_7.txt,subtask03_8.txt,subtask03_9.txt,subtask00_sample_1.txt,subtask00_sample_4.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask00_sample_1.txt AC 471 ms 29316 KB
subtask00_sample_2.txt AC 378 ms 29464 KB
subtask00_sample_3.txt AC 359 ms 29336 KB
subtask00_sample_4.txt AC 358 ms 29244 KB
subtask01_0.txt AC 363 ms 29500 KB
subtask01_1.txt AC 375 ms 29520 KB
subtask01_10.txt AC 357 ms 29328 KB
subtask01_11.txt AC 364 ms 29312 KB
subtask01_12.txt AC 363 ms 29476 KB
subtask01_13.txt AC 373 ms 29468 KB
subtask01_14.txt AC 376 ms 29408 KB
subtask01_2.txt AC 358 ms 29272 KB
subtask01_3.txt AC 360 ms 29328 KB
subtask01_4.txt AC 360 ms 29416 KB
subtask01_5.txt AC 368 ms 29396 KB
subtask01_6.txt AC 360 ms 29356 KB
subtask01_7.txt AC 361 ms 29428 KB
subtask01_8.txt AC 364 ms 29488 KB
subtask01_9.txt AC 362 ms 29380 KB
subtask02_0.txt AC 455 ms 30236 KB
subtask02_1.txt AC 460 ms 30340 KB
subtask02_10.txt AC 458 ms 30348 KB
subtask02_11.txt AC 447 ms 30232 KB
subtask02_12.txt AC 450 ms 30184 KB
subtask02_13.txt AC 363 ms 29152 KB
subtask02_14.txt AC 448 ms 30156 KB
subtask02_2.txt AC 457 ms 30416 KB
subtask02_3.txt AC 457 ms 30260 KB
subtask02_4.txt AC 447 ms 30252 KB
subtask02_5.txt AC 484 ms 30308 KB
subtask02_6.txt AC 490 ms 30040 KB
subtask02_7.txt AC 467 ms 30252 KB
subtask02_8.txt AC 467 ms 30448 KB
subtask02_9.txt AC 480 ms 30308 KB
subtask03_0.txt AC 471 ms 30316 KB
subtask03_1.txt AC 468 ms 30228 KB
subtask03_10.txt AC 457 ms 30296 KB
subtask03_11.txt AC 370 ms 29276 KB
subtask03_2.txt AC 465 ms 30284 KB
subtask03_3.txt AC 455 ms 30324 KB
subtask03_4.txt AC 467 ms 30188 KB
subtask03_5.txt AC 451 ms 30356 KB
subtask03_6.txt AC 449 ms 30348 KB
subtask03_7.txt AC 454 ms 30288 KB
subtask03_8.txt AC 460 ms 30304 KB
subtask03_9.txt AC 454 ms 30316 KB