#1176453 (Java) No.200 カードファイト！

• 問題: No.200 カードファイト！
• ユーザー: 37zigen
• 提出日時: 2026-08-12 20:54:41
• 言語: Java (openjdk 25.0.2)
• 結果: WA
• 実行時間: -
• コード長: 15,572 bytes
• コンパイル時間: 1,936 ms
• コンパイル使用メモリ: 99,784 KB
• 実行使用メモリ: 41,148 KB
• 最終ジャッジ日時: 2026-08-12 20:54:49
• 合計ジャッジ時間: 4,858 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_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.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PrimitiveIterator.OfInt;
import java.util.PrimitiveIterator;

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);
        BipartiteMatching matching = new BipartiteMatching(N, N);
        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]) {
                    matching.addEdge(i, (C * q) + j);
                }
            }
        }
        int ans = matching.calc();
        pw.println(ans);
    }
}

/**
 * 二部グラフの最大マッチングを求めるクラス。
 * Hopcroft-Karp 法を利用する。
 *
 * 計算量: O(E√V)
 * V = L + R, E = 辺数
 */
class BipartiteMatching {
    int L;

    int R;

    /**
     * adj[l] = 左側頂点 l から辺がある右側頂点のリスト
     */
    IntArrayList[] adj;

    int[] fromLtoR;

    int[] fromRtoL;

    /**
     * Hopcroft-Karp の BFS 距離。左側頂点だけに持つ。
     */
    int[] dist;

    int[] it;

    /**
     * 最短増加路の長さを、左側レイヤー数で持つ。実際の辺数は 2 * shortest - 1。
     */
    int shortest;

    static final int INF = 1 << 28;

    /**
     * DM 分解用に、追加された辺を保存しておく。
     */
    IntArrayList edgesL = new IntArrayList();

    IntArrayList edgesR = new IntArrayList();

    boolean calculated = false;

    /**
     * 左側頂点数 L、右側頂点数 R の二部グラフを作成する。
     *
     * @param L
     * 		左側の頂点数
     * @param R
     * 		右側の頂点数
     */
    @SuppressWarnings("unchecked")
    public BipartiteMatching(int L, int R) {
        this.L = L;
        this.R = R;
        adj = new IntArrayList[L];
        for (int i = 0; i < L; i++) {
            adj[i] = new IntArrayList();
        }
        fromLtoR = new int[L];
        fromRtoL = new int[R];
        dist = new int[L];
        it = new int[L];
        Arrays.fill(fromLtoR, -1);
        Arrays.fill(fromRtoL, -1);
    }

    /**
     * 左側の頂点 from と右側の頂点 to の間に辺を追加する。
     *
     * @param from
     * 		左側の頂点番号 (0 ～ L-1)
     * @param to
     * 		右側の頂点番号 (0 ～ R-1)
     */
    public void addEdge(int from, int to) {
        if ((from < 0) || (from >= L)) {
            throw new IndexOutOfBoundsException("left vertex out of range: " + from);
        }
        if ((to < 0) || (to >= R)) {
            throw new IndexOutOfBoundsException("right vertex out of range: " + to);
        }
        adj[from].add(to);
        edgesL.add(from);
        edgesR.add(to);
        calculated = false;
    }

    /**
     * 最大マッチングを計算し、マッチングのサイズを返す。
     *
     * 計算量: O(E√V)
     *
     * @return 最大マッチングのサイズ
     */
    public int calc() {
        // https://judge.yosupo.jp/submission/381131
        Arrays.fill(fromLtoR, -1);
        Arrays.fill(fromRtoL, -1);
        int matching = 0;
        while (bfs()) {
            Arrays.fill(it, 0);
            for (int l = 0; l < L; l++) {
                if ((fromLtoR[l] == (-1)) && dfs(l)) {
                    matching++;
                }
            }
        } 
        calculated = true;
        return matching;
    }

    /**
     * 未マッチ左頂点を始点として、最短増加路用の距離を作る。
     *
     * dist[l] は左側頂点だけで見た距離。
     * dist[l] = d の左頂点から未マッチ右頂点へ行けるとき、
     * 増加路の辺数は 2d + 1。
     *
     * @return 増加路が存在するなら true
     */
    private boolean bfs() {
        Arrays.fill(dist, -1);
        IntDeque que = new IntDeque();
        for (int l = 0; l < L; l++) {
            if (fromLtoR[l] == (-1)) {
                dist[l] = 0;
                que.addLast(l);
            }
        }
        shortest = INF;
        while (!que.isEmpty()) {
            int l = que.pollFirst();
            // これ以上深く進むと、最短増加路より長くなる。
            if ((dist[l] + 1) > shortest) {
                continue;
            }
            for (int r : adj[l]) {
                int nl = fromRtoL[r];
                if (nl == (-1)) {
                    // l -> r で未マッチ右頂点に到達。
                    shortest = dist[l] + 1;
                } else if (dist[nl] == (-1)) {
                    // l -> r は非マッチ辺、r -> nl はマッチ辺。
                    dist[nl] = dist[l] + 1;
                    que.addLast(nl);
                }
            }
        } 
        return shortest != INF;
    }

    /**
     * BFS で作った最短増加路レイヤーに沿って DFS し、
     * 増加路を 1 本見つけたら反転する。
     */
    private boolean dfs(int l) {
        for (; it[l] < adj[l].size(); it[l]++) {
            int r = adj[l].get(it[l]);
            int nl = fromRtoL[r];
            if (nl == (-1)) {
                if ((dist[l] + 1) == shortest) {
                    fromLtoR[l] = r;
                    fromRtoL[r] = l;
                    return true;
                }
            } else if ((dist[nl] == (dist[l] + 1)) && dfs(nl)) {
                fromLtoR[l] = r;
                fromRtoL[r] = l;
                return true;
            }
        }
        return false;
    }
}

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;
    }
}

/**
 * *
 * tailがa.lengthに比べて小さくなっても配列を取り直さない。
 *
 * @param <T>
 */
class IntArrayList implements Iterable<Integer> {
    @SuppressWarnings("unchecked")
    int defaultCapacity = 16;

    int[] a;

    public int tail = 0;

    public IntArrayList() {
        a = new int[defaultCapacity];
    }

    public void add(int v) {
        if (tail == a.length) {
            resize(2 * a.length);
        }
        a[tail] = v;
        tail++;
    }

    public int get(int id) {
        if ((id < 0) || (id >= tail)) {
            throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (tail - 1)) + "以下に違反");
        }
        return a[id];
    }

    void resize(int size) {
        a = Arrays.copyOf(a, size);
    }

    public int size() {
        return tail;
    }

    public int[] toArray() {
        return Arrays.copyOf(a, tail);
    }

    @Override
    public PrimitiveIterator.OfInt iterator() {
        return new PrimitiveIterator.OfInt() {
            int idx = 0;

            @Override
            public boolean hasNext() {
                return idx < tail;
            }

            @Override
            public int nextInt() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return get(idx++);
            }
        };
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof IntArrayList that)) {
            return false;
        }
        if (tail != that.tail) {
            return false;
        }
        for (int i = 0; i < tail; i++) {
            if (a[i] != that.a[i]) {
                return false;
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        int result = 1;
        for (int i = 0; i < tail; i++) {
            result = (31 * result) + a[i];
        }
        return result;
    }

    @Override
    public String toString() {
        return Arrays.toString(toArray());
    }
}

/**
 * *
 * 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 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.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);
// 		BipartiteMatching matching = new BipartiteMatching(N, N);
// 		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]) {
// 					matching.addEdge(i, C * q + j);
// 				}
// 			}
// 		}
// 		int ans=matching.calc();
// 		pw.println(ans);
// 	}
//     
// 	void tr(Object... objects) {
// 		System.out.println(Arrays.deepToString(objects));
// 	}
// }
//