結果

問題 No.200 カードファイト！
コンテスト
ユーザー kenkoooo
提出日時 2015-05-01 10:21:19
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 4,329 bytes
コンパイル時間 2,712 ms
コンパイル使用メモリ 81,832 KB
実行使用メモリ 43,936 KB
最終ジャッジ日時 2024-07-05 17:19:16
合計ジャッジ時間 6,640 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 19
権限があれば一括ダウンロードができます

ソースコード

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