結果

問題 No.200 カードファイト!
ユーザー kenkooookenkoooo
提出日時 2015-05-01 10:21:19
言語 Java19
(openjdk 21)
結果
WA  
実行時間 -
コード長 4,329 bytes
コンパイル時間 3,071 ms
コンパイル使用メモリ 76,764 KB
実行使用メモリ 60,804 KB
最終ジャッジ日時 2023-09-19 04:49:27
合計ジャッジ時間 9,327 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 131 ms
55,764 KB
testcase_03 AC 132 ms
56,388 KB
testcase_04 AC 131 ms
55,908 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 132 ms
56,084 KB
testcase_14 AC 132 ms
55,808 KB
testcase_15 AC 132 ms
56,192 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 143 ms
55,976 KB
testcase_23 AC 137 ms
55,600 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 138 ms
55,660 KB
testcase_27 AC 145 ms
55,992 KB
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int[] cardA = new int[A];
		for (int i = 0; i < cardA.length; i++) {
			cardA[i] = sc.nextInt();
		}
		int C = sc.nextInt();
		int[] cardC = new int[C];
		for (int i = 0; i < cardC.length; i++) {
			cardC[i] = sc.nextInt();
		}
		sc.close();

		Arrays.sort(cardA);
		Arrays.sort(cardC);

		ArrayList<Integer> cardAList = new ArrayList<>();
		ArrayList<Integer> cardCList = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			cardAList.add(cardA[(N - 1 - i) % A]);
			cardCList.add(cardC[i % C]);
		}

		PrimalDual primalDual = new PrimalDual(2 + 2 * N);
		for (int i = 0; i < N; i++) {
			primalDual.addEdge(0, i + 1, 1, 0);
			int cardANum = cardAList.get(i);
			int deckAStart = i / A * A;
			int deckCStart = deckAStart / C * C;
			int deckAEnd = deckAStart + A;
			int deckCEnd = (deckAEnd + C - 1) / C * C;
			for (int j = deckCStart; j < Math.min(deckCEnd, N); j++) {
				if (cardCList.get(j) >= cardANum) {
					primalDual.addEdge(i + 1, 1 + N + j, 1, 1);
				} else {
					primalDual.addEdge(i + 1, 1 + N + j, 1, 0);
				}
			}
		}
		for (int i = 0; i < N; i++) {
			primalDual.addEdge(1 + N + i, 1 + 2 * N, 1, 0);
		}

		int minCost = primalDual.minCostFlow(0, 1 + N * 2, N);
		System.out.println(N - minCost);

	}

	static class PrimalDual {
		final int INF = 1 << 29;
		int N;// 頂点数
		ArrayList<Edge>[] graph;

		@SuppressWarnings("unchecked")
		public PrimalDual(int N) {
			this.N = N;
			this.graph = new ArrayList[N];
			for (int i = 0; i < N; i++) {
				graph[i] = new ArrayList<Edge>();
			}
		}

		public void addEdge(int from, int to, int cap, int cost) {
			graph[from].add(new Edge(to, cap, cost, graph[to].size()));
			graph[to].add(new Edge(from, 0, -cost, graph[from].size() - 1));
		}

		public int minCostFlow(int start, int goal, int flow) {
			int[] prevNode = new int[N];
			int[] prevEdge = new int[N];
			int[] potential = new int[N];// ポテンシャル(既にかかったコスト)
			int totalCost = 0;
			while (flow > 0) {
				int[] dist = new int[N];
				Arrays.fill(dist, INF);
				dist[start] = 0;

				PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
				priorityQueue.offer(new Node(0, start));
				while (!priorityQueue.isEmpty()) {
					// キューから1番距離の近いノードを取り出す
					Node node = priorityQueue.poll();
					int v = node.id;
					if (dist[v] < node.dist) {
						// 暫定の最短距離よりも遠かったらスルー
						continue;
					}

					for (int i = 0; i < graph[v].size(); i++) {
						Edge e = graph[v].get(i);

						if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + potential[v] - potential[e.to]) {
							dist[e.to] = dist[v] + e.cost + potential[v] - potential[e.to];
							priorityQueue.add(new Node(dist[e.to], e.to));

							// 直前の経路を記憶しておく
							prevNode[e.to] = v;
							prevEdge[e.to] = i;
						}
					}
				}

				// そもそもゴールまで辿りつけない場合はどうしようもない
				if (dist[goal] == INF) {
					return -1;
				}

				// 今回かかったコストをメモしておく
				for (int v = 0; v < N; v++) {
					potential[v] += dist[v];
				}

				// startからgoalまで流せるだけ流す
				int minFlow = flow;
				for (int now = goal; now != start; now = prevNode[now]) {
					minFlow = Math.min(minFlow, graph[prevNode[now]].get(prevEdge[now]).cap);
				}
				flow -= minFlow;
				totalCost += minFlow * potential[goal];

				for (int now = goal; now != start; now = prevNode[now]) {
					Edge edge = graph[prevNode[now]].get(prevEdge[now]);
					edge.cap -= minFlow;
					graph[now].get(edge.rev).cap += minFlow;
				}
			}
			return totalCost;
		}

		class Node implements Comparable<Node> {
			int dist;
			int id;

			public Node(int dist, int i) {
				this.dist = dist;
				this.id = i;
			}

			public int compareTo(Node o) {
				return this.dist - o.dist;
			}
		}

		class Edge {
			int to, cap, cost, rev;

			public Edge(int to, int cap, int cost, int rev) {
				this.to = to;
				this.cap = cap;
				this.cost = cost;
				this.rev = rev;
			}
		}
	}

}
0