結果
| 問題 | No.200 カードファイト！ |
| コンテスト | |
| ユーザー |
 drken1215
|
| 提出日時 | 2026-08-12 23:53:37 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| + 511µs | |
| コード長 | 18,458 bytes |
| 記録 | |
| コンパイル時間 | 3,793 ms |
| コンパイル使用メモリ | 380,620 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-08-12 23:53:59 |
| 合計ジャッジ時間 | 5,615 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
// code template is in https://github.com/drken1215/algorithm/blob/master/template_minimum.cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
//------------------------------//
// Utility
//------------------------------//
using ll = long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tll = array<long long, 3>;
using fll = array<long long, 4>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }
#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PF push_front
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
// input
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
// output
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
void yes(bool a) { cout << (a ? "yes" : "no") << endl; }
void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }
void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }
const vector<int> DX = {1, 0, -1, 0, 1, -1, 1, -1};
const vector<int> DY = {0, 1, 0, -1, 1, -1, -1, 1};
// edge class (for min-cost flow)
template<class FLOW, class COST> struct FlowCostEdge {
// core members
int rev, from, to;
FLOW cap, icap, flow;
COST cost;
// constructor
constexpr FlowCostEdge() noexcept = default;
constexpr FlowCostEdge(int rev, int from, int to, FLOW cap, COST cost)
: rev(rev), from(from), to(to), cap(cap), icap(cap), flow(0), cost(cost) {
}
constexpr FlowCostEdge(int rev, int from, int to, FLOW cap, FLOW rcap, COST cost)
: rev(rev), from(from), to(to), cap(cap), icap(cap), flow(rcap), cost(cost) {
}
void reset() {
flow -= icap - cap;
cap = icap;
}
// debug
friend ostream& operator << (ostream& s, const FlowCostEdge& e) {
return s << e.from << " -> " << e.to << " (" << e.cap << ", " << e.flow << ", " << e.cost << ")";
}
};
// graph class (for min-cost flow)
template<class FLOW, class COST> struct FlowCostGraph {
// core members
vector<vector<FlowCostEdge<FLOW, COST>>> list;
vector<pair<int,int>> pos; // pos[i] := {vertex, order of list[vertex]} of i-th edge
vector<COST> pot; // pot[v] := potential (e.cost + pot[e.from] - pos[e.to] >= 0)
bool include_negative_edge = false;
// constructor
FlowCostGraph(int n = 0) : list(n), pot(n), include_negative_edge(false) { }
void init(int n = 0) {
list.clear(), list.resize(n);
pos.clear();
pot.assign(n, 0);
include_negative_edge = false;
}
// getter
vector<FlowCostEdge<FLOW, COST>> &operator [] (int i) {
assert(0 <= i && i < (int)list.size());
return list[i];
}
const vector<FlowCostEdge<FLOW, COST>> &operator [] (int i) const {
assert(0 <= i && i < (int)list.size());
return list[i];
}
size_t size() const noexcept {
return list.size();
}
FlowCostEdge<FLOW, COST> &get_rev_edge(const FlowCostEdge<FLOW, COST> &e) {
return list[e.to][e.rev];
}
const FlowCostEdge<FLOW, COST> &get_rev_edge(const FlowCostEdge<FLOW, COST> &e) const {
return list[e.to][e.rev];
}
FlowCostEdge<FLOW, COST> &get_edge(int i) {
return list[pos[i].first][pos[i].second];
}
const FlowCostEdge<FLOW, COST> &get_edge(int i) const {
return list[pos[i].first][pos[i].second];
}
vector<FlowCostEdge<FLOW, COST>> get_edges() const {
vector<FlowCostEdge<FLOW, COST>> edges;
for (int i = 0; i < (int)pos.size(); ++i) {
edges.push_back(get_edge(i));
}
return edges;
}
// change edges
void reset() {
for (int i = 0; i < (int)list.size(); ++i) {
for (FlowCostEdge<FLOW, COST> &e : list[i]) e.reset();
}
}
// add_edge
void add_edge(int from, int to, FLOW cap, COST cost) {
assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
assert(cap >= 0);
int from_id = (int)list[from].size(), to_id = (int)list[to].size();
if (from == to) to_id++;
pos.emplace_back(from, from_id);
list[from].push_back(FlowCostEdge<FLOW, COST>(to_id, from, to, cap, 0, cost));
list[to].push_back(FlowCostEdge<FLOW, COST>(from_id, to, from, 0, cap, -cost));
if (cost < 0) include_negative_edge = true;
}
void add_edge(int from, int to, FLOW cap, FLOW rcap, COST cost) {
assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
assert(cap >= 0);
int from_id = (int)list[from].size(), to_id = (int)list[to].size();
if (from == to) to_id++;
pos.emplace_back(from, from_id);
list[from].push_back(FlowCostEdge<FLOW, COST>(to_id, from, to, cap, rcap, cost));
list[to].push_back(FlowCostEdge<FLOW, COST>(from_id, to, from, rcap, cap, -cost));
if (cost < 0) include_negative_edge = true;
}
void add_bidirected_edge(int from, int to, FLOW cap, COST cost) {
assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
assert(cap >= 0);
add_edge(from, to, cap, cap, cost);
}
// find initial potential (to resolve initial negative-edge)
// pot[v] := potential (e.cost + pot[e.from] - pos[e.to] >= 0)
bool calc_potential_dag() {
pot.assign(size(), 0);
vector<int> deg(size(), 0), st;
for (int v = 0; v < (int)size(); v++) for (const auto &e : list[v]) deg[e.to] += (e.cap > 0);
st.reserve(size());
for (int v = 0; v < (int)size(); v++) if (!deg[v]) st.emplace_back(v);
for (int i = 0; i < (int)size(); i++) {
if ((int)st.size() == i) return false; // not DAG
int cur = st[i];
for (const auto &e : list[cur]) {
if (e.cap <= 0) continue;
deg[e.to]--;
if (deg[e.to] == 0) st.emplace_back(e.to);
if (pot[e.to] >= pot[cur] + e.cost) pot[e.to] = pot[cur] + e.cost;
}
}
return true;
}
bool calc_potential_spfa() {
pot.assign(size(), 0);
queue<int> que;
vector<bool> inque(size(), false);
vector<int> cnt(size(), 0);
for (int v = 0; v < (int)size(); v++) que.push(v), inque[v] = true;
while (!que.empty()) {
int cur = que.front();
que.pop();
inque[cur] = false;
if (cnt[cur] > (int)size()) return false; // include negative-cycle
cnt[cur]++;
for (const auto &e : list[cur]) {
if (e.cap <= 0) continue;
if (pot[e.to] > pot[cur] + e.cost) {
pot[e.to] = pot[cur] + e.cost;
if (!inque[e.to]) inque[e.to] = true, que.push(e.to);
}
}
}
return true;
}
bool calc_potential() {
return calc_potential_dag() || calc_potential_spfa();
}
bool init_potential() {
if (!include_negative_edge) return true;
return calc_potential();
}
// decompose flow into s-t simple paths and cycles
using Path = vector<FlowCostEdge<FLOW, COST>>;
pair<vector<Path>, vector<Path>> decompose(int s, int t) const {
struct Arc {
int to;
FLOW rem;
int eidx;
};
vector<vector<Arc>> fg(list.size());
for (int v = 0; v < (int)list.size(); v++) {
for (int j = 0; j < (int)list[v].size(); j++) {
FLOW f = list[v][j].icap - list[v][j].cap;
if (f > 0) fg[v].push_back({list[v][j].to, f, j});
}
}
vector<Path> paths, cycles;
auto build = [&](const vector<pair<int,int>> &route, bool is_cycle) {
FLOW mi = numeric_limits<FLOW>::max();
for (auto [v,i] : route) mi = min(mi, fg[v][i].rem);
vector<FlowCostEdge<FLOW,COST>> seq;
for (auto [v,i] : route) {
fg[v][i].rem -= mi;
FlowCostEdge<FLOW,COST> e = list[v][fg[v][i].eidx];
e.flow = mi;
seq.push_back(e);
}
if (is_cycle) cycles.push_back(std::move(seq));
else paths.push_back(std::move(seq));
};
// Phase 1: extract all cycles and make graph DAG
const int NOTSEEN = 0, INSTACK = 1, FINISH = 2;
vector<int> color(list.size(), NOTSEEN);
vector<int> pos_in_stack(list.size(), -1);
vector<pair<int, int>> stk;
auto dfs = [&](auto &&dfs, int v) -> bool {
color[v] = INSTACK;
pos_in_stack[v] = (int)stk.size();
for (int i = 0; i < (int)fg[v].size(); i++) {
if (fg[v][i].rem <= 0) continue;
int u = fg[v][i].to;
if (color[u] == INSTACK) {
vector<pair<int,int>> route;
for (int k = pos_in_stack[u]; k < (int)stk.size(); k++) {
route.push_back(stk[k]);
}
route.push_back({v, i});
build(route, true);
return true;
}
if (color[u] == NOTSEEN) {
stk.push_back({v, i});
if (dfs(dfs, u)) return true;
stk.pop_back();
}
}
color[v] = FINISH;
pos_in_stack[v] = -1;
return false;
};
while (true) {
fill(color.begin(), color.end(), NOTSEEN);
stk.clear();
bool found = false;
for (int v = 0; v < (int)list.size() && !found; v++) {
if (color[v] == NOTSEEN && dfs(dfs, v)) found = true;
}
if (!found) break;
}
// Phase 2: find all s-t paths
vector<int> ptr(list.size(), 0);
auto next_arc = [&](int v) -> int {
while (ptr[v] < (int)fg[v].size() && fg[v][ptr[v]].rem <= 0) ptr[v]++;
return ptr[v] < (int)fg[v].size() ? ptr[v] : -1;
};
while (next_arc(s) != -1) {
vector<pair<int,int>> route;
int v = s;
while (v != t) {
int i = next_arc(v);
route.push_back({v, i});
v = fg[v][i].to;
}
build(route, false);
}
return {paths, cycles};
}
// debug
friend ostream& operator << (ostream& s, const FlowCostGraph &G) {
const auto &edges = G.get_edges();
for (const auto &e : edges) s << e << endl;
return s;
}
};
// min-cost max-flow (<= limit_flow), slope ver.
template<class FLOW, class COST> vector<pair<FLOW, COST>>
MinCostFlowSlope(FlowCostGraph<FLOW, COST> &G, int S, int T, FLOW limit_flow)
{
// result values
FLOW cur_flow = 0;
COST cur_cost = 0, pre_cost = numeric_limits<COST>::max() / 2;
vector<pair<FLOW, COST>> res;
res.emplace_back(cur_flow, cur_cost);
// intermediate values
vector<COST> dist((int)G.size(), numeric_limits<COST>::max() / 2);
vector<int> prevv((int)G.size(), -1), preve((int)G.size(), -1);
// dual
auto dual_step = [&]() -> bool {
dist.assign((int)G.size(), numeric_limits<COST>::max() / 2);
dist[S] = 0;
priority_queue<pair<COST,int>, vector<pair<COST,int>>, greater<pair<COST,int>>> que;
que.emplace(0, S);
while (!que.empty()) {
auto [cur, v] = que.top();
que.pop();
if (cur > dist[v]) continue;
for (int i = 0; i < (int)G[v].size(); i++) {
const auto &e = G[v][i];
COST add = e.cost + G.pot[v] - G.pot[e.to];
if (e.cap > 0 && dist[e.to] > dist[v] + add) {
dist[e.to] = dist[v] + add;
prevv[e.to] = v;
preve[e.to] = i;
que.emplace(dist[e.to], e.to);
}
}
}
return dist[T] < numeric_limits<COST>::max() / 2;
};
// primal
auto primal_step = [&]() -> void {
for (int v = 0; v < (int)G.size(); v++) {
if (dist[v] < numeric_limits<COST>::max() / 2) G.pot[v] += dist[v];
else G.pot[v] = numeric_limits<COST>::max() / 2;
}
FLOW flow = limit_flow - cur_flow;
COST cost = G.pot[T] - G.pot[S];
for (int v = T; v != S; v = prevv[v]) {
flow = min(flow, G[prevv[v]][preve[v]].cap);
}
for (int v = T; v != S; v = prevv[v]) {
FlowCostEdge<FLOW, COST> &e = G[prevv[v]][preve[v]];
FlowCostEdge<FLOW, COST> &re = G.get_rev_edge(e);
e.cap -= flow, e.flow += flow;
re.cap += flow, re.flow -= flow;
}
cur_flow += flow;
cur_cost += flow * cost;
if (pre_cost == cost) res.pop_back();
res.emplace_back(cur_flow, cur_cost);
pre_cost = cost;
};
// initialize potential
assert(G.init_potential());
// primal-dual
while (cur_flow < limit_flow) {
if (!dual_step()) break;
primal_step();
}
return res;
}
// min-cost max-flow, slope ver.
template<class FLOW, class COST> vector<pair<FLOW, COST>>
MinCostFlowSlope(FlowCostGraph<FLOW, COST> &G, int S, int T)
{
return MinCostFlowSlope(G, S, T, numeric_limits<FLOW>::max());
}
// min-cost max-flow (<= limit_flow)
template<class FLOW, class COST> pair<FLOW, COST>
MinCostFlow(FlowCostGraph<FLOW, COST> &G, int S, int T, FLOW limit_flow)
{
return MinCostFlowSlope(G, S, T, limit_flow).back();
}
// min-cost max-flow (<= limit_flow)
template<class FLOW, class COST> pair<FLOW, COST>
MinCostFlow(FlowCostGraph<FLOW, COST> &G, int S, int T)
{
return MinCostFlow(G, S, T, numeric_limits<FLOW>::max());
}
//------------------------------//
// Solver
//------------------------------//
int main() {
ll N, A, C;
cin >> N >> A;
vll B(A); cin >> B;
cin >> C;
vll D(C); cin >> D;
sort(ALL(B), greater<ll>());
sort(ALL(D));
ll s = N * 2, t = s + 1;
FlowCostGraph<ll, ll> G(t + 1);
REP(i, N) G.add_edge(s, i, 1, 0), G.add_edge(i+N, t, 1, 0);
REP(i, N) REP(j, N) {
ll aq = i / A, ar = i % A, aleft = aq * A, aright = (aq + 1) * A;
ll cq = j / C, cr = j % C, cleft = cq * C, cright = (cq + 1) * C;
if (max(aleft, cleft) < min(aright, cright)) {
G.add_edge(i, j+N, 1, (B[ar] > D[cr] ? 0 : 1));
}
}
//COUT(G);
auto [maxflow, mincost] = MinCostFlow(G, s, t, N);
auto res = N - mincost;
//COUT(maxflow); COUT(mincost); COUT(G);
cout << res << endl;
}