結果
問題 | No.200 カードファイト! |
ユーザー | kenkoooo |
提出日時 | 2015-05-01 10:21:19 |
言語 | Java21 (openjdk 21) |
結果 |
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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 107 ms
40,948 KB |
testcase_03 | AC | 107 ms
41,296 KB |
testcase_04 | AC | 107 ms
40,904 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 | 111 ms
40,956 KB |
testcase_14 | AC | 110 ms
41,072 KB |
testcase_15 | AC | 109 ms
41,204 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 118 ms
41,580 KB |
testcase_23 | AC | 106 ms
40,628 KB |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | AC | 113 ms
41,612 KB |
testcase_27 | AC | 109 ms
40,464 KB |
testcase_28 | WA | - |
ソースコード
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; } } } }