結果
| 問題 | No.200 カードファイト！ |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-08-12 21:40:03 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,099 bytes |
| 記録 | |
| コンパイル時間 | 1,810 ms |
| コンパイル使用メモリ | 99,012 KB |
| 実行使用メモリ | 40,960 KB |
| 最終ジャッジ日時 | 2026-08-12 21:40:08 |
| 合計ジャッジ時間 | 4,457 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 WA * 1 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PrimitiveIterator.OfInt;
import java.util.PrimitiveIterator;
import java.util.function.BiFunction;
import java.util.function.IntFunction;
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;
MaxFlow mf = new MaxFlow(((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);
}
}
}
}
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, N % A);
mf.addEdge(t2, t, N % C);
for (int i = 0; i < (qA * A); i++) {
if ((i / A) == (qA - 1)) {
mf.addEdge(s2, i, 1);
} else {
mf.addEdge(s, i, 1);
}
}
for (int i = 0; i < (qC * C); i++) {
if ((i / C) == (qC - 1)) {
mf.addEdge(i + leftSize, t2, 1);
} else {
mf.addEdge(i + leftSize, t, 1);
}
}
long ans = mf.maxFlowValue(s, t, N);
// mf.draw();
pw.println(ans);
}
}
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;
}
}
/**
* *
* lenがa.lengthに比べて小さくなっても配列を取り直さない。
*
* @param <T>
*/
class IntDeque implements Iterable<Integer> {
@SuppressWarnings("unchecked")
int[] a = new int[16];
int head = 0;
int tail = 0;
int len = 0;
// [head, tail)に値を持つ。
public IntDeque() {
}
public void addLast(int v) {
if (len == a.length) {
resize(2 * len);
}
a[tail] = v;
tail = (tail + 1) & (a.length - 1);
++len;
}
public int pollFirst() {
if (len == 0) {
throw new NoSuchElementException();
}
int ret = a[head];
head = (head + 1) & (a.length - 1);
len--;
return ret;
}
public boolean isEmpty() {
return len == 0;
}
public int get(int id) {
if ((id < 0) || (id >= len)) {
throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (len - 1)) + "以下に違反");
}
return a[(head + id) & (a.length - 1)];
}
void resize(int size) {
@SuppressWarnings("unchecked")
int[] na = new int[size];
for (int i = 0; i < len; i++) {
na[i] = a[(head + i) & (a.length - 1)];
}
head = 0;
tail = len;
a = na;
}
@Override
public PrimitiveIterator.OfInt iterator() {
return new PrimitiveIterator.OfInt() {
int idx = 0;
@Override
public boolean hasNext() {
return idx < len;
}
@Override
public int nextInt() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return get(idx++);
}
};
}
/**
* デックの内容を表す文字列を返す。
*
* @return デック内容の文字列
$O(N)$
// 未テスト
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < len; i++) {
sb.append(get(i));
if (i < (len - 1)) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
/**
* このデックと別のオブジェクトの同値性を判定します。
* 全ての要素が順序を含めて一致する場合に同値とみなします。
*
* <p>計算量: $O(N)$（$N$ はデックの要素数）</p>
*
* @param obj
* 比較対象のオブジェクト
* @return 同値であれば true, そうでなければ false
*/
// 未テスト
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof IntDeque)) {
return false;
}
IntDeque other = ((IntDeque) (obj));
if (this.len != other.len) {
return false;
}
for (int i = 0; i < len; i++) {
if (this.get(i) != other.get(i)) {
return false;
}
}
return true;
}
/**
* このデックのハッシュコードを計算します。
*
* <p>計算量: $O(N)$（$N$ はデックの要素数）</p>
*
* @return ハッシュコード
*/
// 未テスト
@Override
public int hashCode() {
int result = 1;
for (int i = 0; i < len; i++) {
result = (31 * result) + Integer.hashCode(get(i));
}
return result;
}
}
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));
}
}
class MaxFlow {
public class Edge {
public final int v;
public final long cap;
public long flow;// flowは非負。 flowとie.flowの高々一方のみが正。
final int invEdgeId;
public Edge(int v, long cap, int invEdgeId) {
this.v = v;
this.cap = cap;
this.invEdgeId = invEdgeId;
}
long res() {
return (cap - flow) + g[v].get(invEdgeId).flow;
}
}
int n;
public ArrayList<Edge>[] g;
@SuppressWarnings("unchecked")
public MaxFlow(int n) {
this.n = n;
g = new ArrayList[n];
Arrays.setAll(g, i -> new ArrayList<>());
}
public void addEdge(int u, int v, long cap) {
if (cap < 0) {
throw new AssertionError();
}
Edge e = new Edge(v, cap, g[v].size());
Edge ie = new Edge(u, 0, g[u].size());
g[u].add(e);
g[v].add(ie);
}
int[] d;
int[] itr;
int s;
int t;
/**
* 最大流量がcutoff以上になったら打ち切る。
*
* @param s
* @param t
* @param cutoff
* @return verified:https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=11030642#1
*/
public long maxFlowValue(int s, int t, long cutoff) {
if (s == t) {
return 0;
}
this.s = s;
this.t = t;
long ans = 0;
d = new int[n];
itr = new int[n];
while (ans < cutoff) {
IntDeque que = new IntDeque();
que.addLast(s);
Arrays.fill(itr, 0);
Arrays.fill(d, n + 1);
d[s] = 0;
// 残余ネットワークで最短路を求める
while (!que.isEmpty()) {
int v = que.pollFirst();
if (v == t) {
break;
}
for (Edge e : g[v]) {
if ((d[e.v] == (n + 1)) && (e.res() > 0)) {
d[e.v] = d[v] + 1;
que.addLast(e.v);
}
}
}
if (d[t] == (n + 1)) {
break;
}
// 最短路上でフローを流す
while (ans < cutoff) {
// 一回につき飽和辺が一つ以上増えるので、高々O(E)回周る。
long add = dfs(s, cutoff - ans);
ans += add;
if (add == 0) {
break;
}
}
}
return Math.min(ans, cutoff);
}
private long dfs(int v, long upper) {
if (v == t) {
return upper;
}
while (itr[v] < g[v].size()) {
Edge e = g[v].get(itr[v]);
if ((e.res() > 0) && (d[e.v] == (d[v] + 1))) {
long add = dfs(e.v, Math.min(upper, e.res()));
if (add != 0) {
var ie = g[e.v].get(e.invEdgeId);
long add0 = Math.min(ie.flow, add);
ie.flow -= add0;
e.flow += add - add0;
return add;
}
}
itr[v]++;// e.res()>0&&d[e.v]==d[v]+1はdfsでflowを一回流しただけで満たされなくなるとは限らないなので、ifの前ではなくifの後に呼ぶ。ifの前に置くと遅い。
}
return 0;
}
}
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;
// MaxFlow mf=new MaxFlow(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);
// }
// }
// }
// }
// 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, N % A);
// mf.addEdge(t2, t, N % C);
// for (int i = 0; i < qA * A; i++) {
// if (i / A == qA - 1) {
// mf.addEdge(s2, i, 1);
// } else {
// mf.addEdge(s, i, 1);
// }
// }
// for (int i = 0; i < qC * C; i++) {
// if (i / C == qC - 1) {
// mf.addEdge(i + leftSize, t2, 1);
// } else {
// mf.addEdge(i + leftSize, t, 1);
// }
// }
//
// long ans = mf.maxFlowValue(s, t, N);
// // mf.draw();
// pw.println(ans);
// }
//
// void tr(Object... objects) {
// System.out.println(Arrays.deepToString(objects));
// }
// }
//