結果
| 問題 | No.200 カードファイト！ |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-08-12 21:00:25 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,445 bytes |
| 記録 | |
| コンパイル時間 | 2,098 ms |
| コンパイル使用メモリ | 96,708 KB |
| 実行使用メモリ | 50,628 KB |
| 最終ジャッジ日時 | 2026-08-12 21:00:31 |
| 合計ジャッジ時間 | 5,657 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 3 WA * 23 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.Serializable;
import java.lang.constant.Constable;
import java.lang.constant.ConstantDesc;
import java.lang.reflect.Array;
import java.util.AbstractCollection;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.Predicate;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Main {
static MyPrintWriter pw = MyPrintWriter.getInstance();
static FastScanner sc = FastScanner.getInstance();
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
new Main().run();
pw.flush();
}
void run() {
int N = sc.nextInt();
int A = sc.nextInt();
int[] B = sc.nextInts(A);
int C = sc.nextInt();
int[] D = sc.nextInts(C);
MinimumCostFlow mf = new MinimumCostFlow((N + N) + 2);
for (int i = 0; i < N; i++) {
int aVal = B[i % A];
int q = i / C;
for (int j = 0; j < C; j++) {
if (((C * q) + j) >= N) {
continue;
}
if (aVal > D[j]) {
mf.addEdge(i, (N + (C * q)) + j, -1, 1);
} else {
mf.addEdge(i, (N + (C * q)) + j, 0, 1);
}
}
}
int source = N + N;
int sink = (N + N) + 1;
for (int i = 0; i < N; i++) {
mf.addEdge(source, i, 0, 1);
mf.addEdge(N + i, sink, 0, 1);
}
var res = mf.minCostFlowSlope(source, sink);
long ans = res.getLast()[1];
ans *= -1;
pw.println(ans);
}
}
class ArrayUtils {
/**
* *
* a[i] = max a となる最小のiを返す。
*
* @param a
* @return */
public static int argMax(long[] a) {
int ret = 0;
for (int i = 0; i < a.length; ++i) {
if (a[i] > a[ret]) {
ret = i;
}
}
return ret;
}
public static long max(long[] a) {
long ret = Long.MIN_VALUE;
for (int i = 0; i < a.length; ++i) {
ret = Math.max(ret, a[i]);
}
return ret;
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
public int[] nextInts(int n) {
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = nextInt();
}
return a;
}
}
/**
* 流量をFとしてO(F(N+M)log(N+M))。負辺は最初に全て流しきるため、負辺の流量F'が、答えに必要なくてもFに加算される。F'を計算量から消したい場合は、最初から簡約費用にする。
*/
class MinimumCostFlow {
int N;
public ArrayList<Edge>[] g;
public ArrayList<Edge>[] ig;
public long[] excess;
public long[] potential;
long INF = Long.MAX_VALUE / 3;
Edge[] incommingShortestPathEdge;
long[] d;
long base = 0;
@SuppressWarnings("unchecked")
public MinimumCostFlow(int N) {
this.N = N;
g = new ArrayList[this.N];
ig = new ArrayList[this.N];
excess = new long[this.N];
potential = new long[this.N];
d = new long[this.N];
incommingShortestPathEdge = new Edge[this.N];
for (int i = 0; i < this.N; ++i) {
g[i] = new ArrayList<>();
ig[i] = new ArrayList<>();
}
}
public class Edge {
public int from;
public int to;
public long cost;
public long cap;
public long flow = 0;
Edge reverseEdge;
public Edge(int from, int to, long cost, long cap) {
this.from = from;
this.to = to;
this.cost = cost;
this.cap = cap;
}
public long res() {
return cap - flow;
}
long reducedCost() {
// 残余ネットワークで、常に簡約費用非負を保つ。
// 初期状態ではポテンシャル0だが、負辺を流しきっているのでok。
// cost - potential[to] + potential[from] >= 0
// potential[to] + cost >= potential[to]
// なのである固定した頂点からの距離をpotentialとすると非負になる。
return cost - (potential[to] - potential[from]);
}
void addFlow(long add) {
flow += add;
reverseEdge.flow -= add;
if (flow > cap) {
throw new AssertionError();
}
if (reverseEdge.flow > reverseEdge.cap) {
throw new AssertionError();
}
excess[from] -= add;
excess[to] += add;
}
@Override
public String toString() {
return (((((((("from " + from) + " to ") + to) + " : flow=") + flow) + ", cap=") + cap) + ", cost=") + cost;
}
}
public void addEdge(int from, int to, long cost, long cap) {
Edge e = new Edge(from, to, cost, cap);
Edge ie = new Edge(to, from, -cost, 0);
e.reverseEdge = ie;
ie.reverseEdge = e;
g[from].add(e);
ig[to].add(ie);
}
/**
* sからtにフローを流したとき、コストは流量の関数として区分線形になる。
* そこで、その線分の端点を{cost, flow}として並べたarraylistを返す。
* 未テスト
*
* @param s
* @param t
* @return */
public ArrayList<long[]> minCostFlowSlope(int s, int t) {
return minCostFlowSlopeInitialized(s, t, minCostCirculation());
}
private ArrayList<long[]> minCostFlowSlopeInitialized(int s, int t, long cost) {
ArrayList<long[]> ret = new ArrayList<>();
long flow = 0;
ret.add(new long[]{ flow, cost });
if (s == t) {
return ret;
}
while (true) {
updateDistance(s);
if (d[t] == INF) {
break;
}
long addFlow = Long.MAX_VALUE;
{
int cur = t;
while (cur != s) {
addFlow = Math.min(addFlow, incommingShortestPathEdge[cur].res());
cur = incommingShortestPathEdge[cur].from;
}
}
if (addFlow == 0) {
break;
}
flow += addFlow;
{
int cur = t;
while (cur != s) {
incommingShortestPathEdge[cur].addFlow(addFlow);
cost += incommingShortestPathEdge[cur].cost * addFlow;
cur = incommingShortestPathEdge[cur].from;
}
}
ret.add(new long[]{ flow, cost });
}
return ret;
}
/**
* 最小費用循環流を求める。
* 存在しなければnullを返す。
* 流量をFとしてO(F(N+M)log(N+M))
*
* @param flow
*/
public Long minCostCirculation() {
// https://atcoder.jp/contests/abc407/submissions/71000667
// https://atcoder.jp/contests/practice2/submissions/71006911
for (var edges : g) {
for (var edge : edges) {
if (edge.reducedCost() < 0) {
edge.addFlow(edge.cap);
}
}
}
while (ArrayUtils.max(excess) > 0) {
int src = ArrayUtils.argMax(excess);
updateDistance(src);
int dst = 0;
while ((dst < N) && ((d[dst] == INF) || (excess[dst] >= 0))) {
++dst;
}
if (dst == N) {
return null;
}
long addFlow = Math.min(excess[src], -excess[dst]);
{
int cur = dst;
while (cur != src) {
addFlow = Math.min(addFlow, incommingShortestPathEdge[cur].res());
cur = incommingShortestPathEdge[cur].from;
}
}
{
int cur = dst;
while (cur != src) {
incommingShortestPathEdge[cur].addFlow(addFlow);
cur = incommingShortestPathEdge[cur].from;
}
}
}
long ret = 0;
for (var edges : g) {
for (var edge : edges) {
ret += edge.flow * edge.cost;
}
}
return ret + base;
}
void updateDistance(int src) {
Arrays.fill(d, INF);
Arrays.fill(incommingShortestPathEdge, null);
d[src] = 0;
record State(int v, long d) implements Comparable<State> {
@Override
public int compareTo(State o) {
return Long.compare(this.d, o.d);
}
}
PriorityQueue<State> pq = new PriorityQueue<>();
pq.add(new State(src, 0));
while (!pq.isEmpty()) {
State state = pq.poll();
if (state.d > d[state.v]) {
continue;
}
for (Edge e : g[state.v]) {
if (e.res() == 0) {
continue;
}
if (d[e.to] > (state.d + e.reducedCost())) {
d[e.to] = state.d + e.reducedCost();
pq.add(new State(e.to, d[e.to]));
incommingShortestPathEdge[e.to] = e;
}
}
for (Edge e : ig[state.v]) {
if (e.res() == 0) {
continue;
}
if (d[e.to] > (state.d + e.reducedCost())) {
d[e.to] = state.d + e.reducedCost();
pq.add(new State(e.to, d[e.to]));
incommingShortestPathEdge[e.to] = e;
}
}
}
for (int i = 0; i < N; ++i) {
if (d[i] != INF) {
potential[i] += d[i];
}
}
}
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
}
// --- Original Code ---
//
//
// import java.io.IOException;
// import java.util.Arrays;
//
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.collections.LongArrayList;
// import library.util.graph.BipartiteMatching;
// import library.util.graph.MaxFlow;
// import library.util.graph.MaxFlowWithLowerBound;
// import library.util.graph.MinimumCostFlow;
// import library.util.seq.SortedArrays;
//
// public class Main {
// static MyPrintWriter pw = MyPrintWriter.getInstance();
// static FastScanner sc = FastScanner.getInstance();
//
// public static void main(String[] args) throws IOException {
// new Main().run();
// pw.flush();
// MergeFiles.export();
// }
//
//
// void run() {
// int N=sc.nextInt();
// int A=sc.nextInt();
// int[]B=sc.nextInts(A);
// int C=sc.nextInt();
// int[]D=sc.nextInts(C);
// MinimumCostFlow mf=new MinimumCostFlow(N + N + 2);
// for (int i = 0; i < N; i++) {
// int aVal = B[i % A];
// int q = i / C;
// for (int j = 0; j < C; j++) {
// if (C * q + j >= N) continue;
// if (aVal > D[j]) {
// mf.addEdge(i, N + C * q + j, -1, 1);
// } else {
// mf.addEdge(i, N + C * q + j, 0, 1);
// }
// }
// }
// int source = N + N;
// int sink = N + N + 1;
// for (int i = 0; i < N; i++) {
// mf.addEdge(source, i, 0, 1);
// mf.addEdge(N + i, sink, 0, 1);
// }
// var res=mf.minCostFlowSlope(source, sink);
// long ans=res.getLast()[1];
// ans *= -1;
// pw.println(ans);
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//