アルゴリズム学習14週目

1.走り出す

質問する

に答える

ソース

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
	final static BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		StringTokenizer stringTokenizer = new StringTokenizer(READER.readLine());

		int n = Integer.parseInt(stringTokenizer.nextToken());
		int m = Integer.parseInt(stringTokenizer.nextToken());

		List<Integer> runs = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			int run = Integer.parseInt(READER.readLine());

			runs.add(run);
		}

		int[][] dp = IntStream.rangeClosed(0, n).mapToObj(i -> IntStream.rangeClosed(0, m).map(j -> -1).toArray()).toArray(int[][]::new);

		System.out.println(getMaxDist(dp, runs, 0, 0, m));
	}

	private static int getMaxDist(int[][] dp, List<Integer> runs, int pos, int jis, int m) {
		if (pos >= runs.size()) {
			return 0;
		}

		if (dp[pos][jis] != -1) {
			return dp[pos][jis];
		}

		dp[pos][jis] = -1000000000;

		if (jis == 0) {
			dp[pos][jis] = Math.max(dp[pos][jis], getMaxDist(dp, runs, pos + 1, jis, m));
		}

		if (jis > 0 && pos + jis <= runs.size()) {
			dp[pos][jis] = Math.max(dp[pos][jis], getMaxDist(dp, runs, pos + jis, 0, m));
		}

		if (jis + 1 <= m && (runs.size() - pos - 1 - (jis + 1) >= 0)) {
			dp[pos][jis] = Math.max(dp[pos][jis], getMaxDist(dp, runs, pos + 1, jis + 1, m) + runs.get(pos));
		}

		return dp[pos][jis];
	}
}

2.カラーボール

質問する

に答える

ソース

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
	final static BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));

	static class Ball {
		int c;
		int s;

		public Ball(int c, int s) {
			this.c = c;
			this.s = s;
		}
	}

	static class BallSize {
		int c;
		int sum;

		public BallSize(int c, int sum) {
			this.c = c;
			this.sum = sum;
		}
	}

	public static void main(String[] args) throws IOException {
		int n = Integer.parseInt(READER.readLine());

		int[] lSum = IntStream.rangeClosed(0, 2000).map(i -> 0).toArray();
		List<ArrayList<Integer>> sizeList = IntStream.rangeClosed(0, n).mapToObj(i -> new ArrayList<Integer>()).collect(Collectors.toList());
		Queue<Ball> queue = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			StringTokenizer stringTokenizer = new StringTokenizer(READER.readLine());
			int c = Integer.parseInt(stringTokenizer.nextToken());
			int s = Integer.parseInt(stringTokenizer.nextToken());

			queue.add(new Ball(c, s));
			sizeList.get(c).add(s);
			lSum[s] += s;
		}

		List<ArrayList<BallSize>> ballSizeList = IntStream.rangeClosed(0, n).mapToObj(i -> new ArrayList<BallSize>()).collect(Collectors.toList());

		for (int i = 1; i <= n; i++) {
			if (sizeList.get(i).isEmpty()) {
				continue;
			}

			sizeList.get(i).sort(null);
			ballSizeList.get(i).add(new BallSize(sizeList.get(i).get(0), sizeList.get(i).get(0)));
			int sum = sizeList.get(i).get(0);
			for (int j = 1; j < sizeList.get(i).size(); j++) {
				ballSizeList.get(i).add(new BallSize(sizeList.get(i).get(j), sum + sizeList.get(i).get(j)));
				sum += sizeList.get(i).get(j);
			}
		}

		for (int i = 1; i <= 2000; i++) {
			lSum[i] += lSum[i - 1];
		}

		while (!queue.isEmpty()) {
			Ball ball = queue.poll();

			int answer = lSum[ball.s - 1];

			if (ballSizeList.get(ball.c).size() > 0) {
				int idx = upper_bound(ballSizeList.get(ball.c), ball.s - 1);
				if (idx != -1) {
					answer -= ballSizeList.get(ball.c).get(idx).sum;
				}
			}

			System.out.println(answer);
		}
	}

	private static int upper_bound(List<BallSize> list, int target) {
		int l = 0;
		int r = list.size() - 1;

		while (l <= r) {
			int mid = (l + r) / 2;
			if (list.get(mid).c <= target) {
				l = mid + 1;
			} else
				r = mid - 1;
		}

		return r;
	}
}