yukicoder No.200 カードファイト!
この問題とは関係ないですがカードヒーローってゲーム僕はすごく好きです。
解法
貪欲で解く。
Aが勝てるときはAはなるべく小さい値で,Cはなるべく大きい値で勝つ。
Aが負けるときもAはなるべく小さい値で,Cはなるべく大きい値で負ける。
…あれ,同じなのか。
const int MAXN = 55; int B[MAXN], D[MAXN]; int A, C, N; bool done[2][MAXN]; int cnta = 0, cntc = 0; int ok(int a) { for (int j = C-1; j >= 0; j--) { if (done[1][j]) continue; if (D[j] < B[a]) return j; } return -1; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; cin >> A; for (int i = 0; i < A; i++) cin >> B[i]; cin >> C; for (int i = 0; i < C; i++) cin >> D[i]; sort(B, B+A); sort(D, D+C); int ans = 0; for (int t = 0; t < N; t++) { if (cnta >= A) { cnta = 0; memset(done[0], false, sizeof(done[0])); } if (cntc >= C) { cntc = 0; memset(done[1], false, sizeof(done[1])); } int a = -1, c = -1; for (int i = A-1; i >= 0; i--) { if (done[0][i]) continue; int tmp = ok(i); if (tmp == -1) break; a = i; c = tmp; } if (a != -1) { ans++; done[0][a] = true; done[1][c] = true; } else { for (int i = 0; i < A; i++) if (!done[0][i]) { a = i; break; } for (int i = C-1; i >= 0; i--) if (!done[1][i]) { c = i; break; } done[0][a] = true; done[1][c] = true; } cnta++; cntc++; } cout << ans << endl; return 0; }