結果
| 問題 | No.200 カードファイト！ |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-08-12 21:57:30 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 495 ms / 2,000 ms |
| + 20µs | |
| コード長 | 16,029 bytes |
| 記録 | |
| コンパイル時間 | 2,029 ms |
| コンパイル使用メモリ | 108,988 KB |
| 実行使用メモリ | 52,652 KB |
| 最終ジャッジ日時 | 2026-08-12 21:57:37 |
| 合計ジャッジ時間 | 6,446 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
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.BiFunction;
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);
int qA = 1 + (N / A);
int qC = 1 + (N / C);
int leftSize = qA * A;
MinimumCostFlow mf = new MinimumCostFlow(((qA * A) + (qC * C)) + 4);
for (int i = 0; i < (qA * A); i++) {
for (int j = 0; j < (qC * C); j++) {
if (Intervals.hasOverlap((i / A) * A, ((i / A) + 1) * A, (j / C) * C, ((j / C) + 1) * C)) {
if (B[i % A] > D[j % C]) {
mf.addEdge(i, leftSize + j, -1, 1);
} else {
mf.addEdge(i, leftSize + j, 0, 1);
}
}
}
}
int s = (qA * A) + (qC * C);
int t = ((qA * A) + (qC * C)) + 1;
int s2 = t + 1;
int t2 = t + 2;
mf.addEdge(s, s2, 0, N % A);
mf.addEdge(t2, t, 0, N % C);
for (int i = 0; i < (qA * A); i++) {
if ((i / A) == (qA - 1)) {
mf.addEdge(s2, i, 0, 1);
} else {
mf.addEdge(s, i, 0, 1);
}
}
for (int i = 0; i < (qC * C); i++) {
if ((i / C) == (qC - 1)) {
mf.addEdge(i + leftSize, t2, 0, 1);
} else {
mf.addEdge(i + leftSize, t, 0, 1);
}
}
var ans = mf.minCostFlowSlope(s, t);
// mf.draw();
pw.println(-ans.getLast()[1]);
}
}
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;
}
}
class Intervals {
/**
* [l0, r0), [l1, r1) が共通部分を持つか
*
* @param l0
* @param r0
* @param l1
* @param r1
* @return */
public static boolean hasOverlap(long l0, long r0, long l1, long r1) {
return !((r0 <= l1) || (r1 <= l0));
}
}
/**
* 流量を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にフローを流したとき、コストは流量の関数として区分線形になる。
* そこで、その線分の端点を {@code [flow, cost]} として並べた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.Intervals;
// 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);
// int qA = 1 + N / A;
// int qC = 1 + N / C;
// int leftSize = qA * A;
// MinimumCostFlow mf=new MinimumCostFlow(qA * A + qC * C + 4);
// for (int i = 0; i < qA * A; i++) {
// for (int j = 0; j < qC * C; j++) {
// if (Intervals.hasOverlap(i / A * A, (i / A + 1) * A, j / C * C, (j / C + 1) * C)) {
// if (B[i % A] > D[j % C]) {
// mf.addEdge(i, leftSize + j, -1, 1);
// } else {
// mf.addEdge(i, leftSize + j, 0, 1);
// }
// }
// }
// }
// int s = qA * A + qC * C;
// int t = qA * A + qC * C + 1;
// int s2 = t + 1;
// int t2 = t + 2;
// mf.addEdge(s, s2, 0, N % A);
// mf.addEdge(t2, t, 0, N % C);
// for (int i = 0; i < qA * A; i++) {
// if (i / A == qA - 1) {
// mf.addEdge(s2, i, 0, 1);
// } else {
// mf.addEdge(s, i, 0, 1);
// }
// }
// for (int i = 0; i < qC * C; i++) {
// if (i / C == qC - 1) {
// mf.addEdge(i + leftSize, t2, 0, 1);
// } else {
// mf.addEdge(i + leftSize, t, 0, 1);
// }
// }
//
// var ans = mf.minCostFlowSlope(s, t);
// // mf.draw();
// pw.println(-ans.getLast()[1]);
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//