Skip to Content
CTRL K

High Card Low Card

Análisis oficial (C++) 

Explicación

Primero, determinemos las cartas que Bessie jugará para cada modo. Intuitivamente, si juega xx turnos del “modo mayor”, entonces debe jugar las xx cartas más altas en algún orden. Su puntaje del “modo mayor” no puede mejorar si cambia alguna carta por una de número menor. Incluso si el puntaje del “modo mayor” se mantiene igual, hacer esto podría empeorar nuestro puntaje del “modo menor”. En cuanto a su estrategia, siempre quiere jugar la carta más pequeña disponible entre las xx cartas que sea mayor que la carta de Elsie. Por lo tanto, el siguiente algoritmo es siempre óptimo para el “modo mayor”:

Let E = An array of Elsie's first x cards
let B = An array of Bessie's highest x cards
score = 0
for d from 1 to 2n:
  for elsie_card in E:
    if bessie_card with number (elsie_card + d) exists in B:
      remove elsie_card from E
      remove bessie_card from B
      add 1 to score

Implementar directamente el algoritmo de arriba da tiempo cuadrático para cada xx, lo cual es demasiado lento. Podemos usar un Árbol de Segmentos para acelerarlo.

Esencialmente, el Árbol de Segmentos calcula el puntaje de cada dd dentro de un intervalo de longitud 2k2^k, donde kk es la profundidad del vértice desde sus hojas. Para cada vértice del Árbol de Segmentos, tenemos que llevar lo siguiente:

  • El puntaje máximo alcanzable después de emparejar todas las cartas de Bessie con las de Elsie en el intervalo.
  • El número de cartas de Elsie que no han sido emparejadas con una carta de Bessie.
  • El número de cartas de Bessie que no han sido emparejadas con una carta de Elsie.

Para fusionar dos intervalos en un intervalo más grande, podemos emparejar todas las cartas no emparejadas de Elsie en el intervalo izquierdo con las cartas no emparejadas de Bessie en el intervalo derecho. Por lo tanto, el mínimo de estos dos valores contribuirá al puntaje del intervalo más grande.

El algoritmo para el “modo menor” se puede determinar de forma similar.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <bits/stdc++.h>
using namespace std;
 
struct Segtree {
	bool higher_mode;
	int n;
 
	struct item {
		int ans, bessie, elsie;
	};
 
	item merge(item a, item b) {
		int take = higher_mode ? min(a.elsie, b.bessie) : min(a.bessie, b.elsie);
		return {a.ans + b.ans + take, a.bessie + b.bessie - take,
		        a.elsie + b.elsie - take};
	}
 
	item NEUTRAL = {0, 0, 0};
 
	vector<item> seg;
 
	Segtree(int n, bool higher_mode) {
		this->n = n;
		this->higher_mode = higher_mode;
		seg.resize(2 * n, NEUTRAL);
	}
 
	void update(int idx, item x) {
		idx += n;
		seg[idx] = x;
		while (idx /= 2) { seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]); }
	}
 
	int query() {
		item left_item = NEUTRAL, right_item = NEUTRAL;
		for (int l = n, r = 2 * n; l < r; l /= 2, r /= 2) {
			if (l % 2 == 1) { left_item = merge(left_item, seg[l++]); }
			if (r % 2 == 1) { right_item = merge(seg[--r], right_item); }
		}
		return merge(left_item, right_item).ans;
	}
};
 
int main() {
	ifstream cin("cardgame.in");
	ofstream cout("cardgame.out");
 
	int n;
	cin >> n;
	vector<bool> contain(2 * n);
	vector<int> elsie;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		contain[--x] = true;
		elsie.push_back(x);
	}
	vector<int> bessie;
	for (int i = 0; i < 2 * n; i++) {
		if (!contain[i]) { bessie.push_back(i); }
	}
 
	Segtree higher_st(2 * n, true), lower_st(2 * n, false);
	const Segtree::item BESSIE_CARD = {0, 1, 0}, ELSIE_CARD = {0, 0, 1},
	                    RESET = {0, 0, 0};
 
	for (int i = 0; i < n; i++) {
		higher_st.update(bessie[i], BESSIE_CARD);
		higher_st.update(elsie[i], ELSIE_CARD);
	}
 
	int ans = higher_st.query();
	// sort to allocate smallest cards first for "lower mode"
	reverse(bessie.begin(), bessie.end());
	for (int i = n - 1; i >= 0; i--) {
		higher_st.update(bessie[i], RESET);
		higher_st.update(elsie[i], RESET);
		lower_st.update(bessie[i], BESSIE_CARD);
		lower_st.update(elsie[i], ELSIE_CARD);
		ans = max(ans, higher_st.query() + lower_st.query());
	}
	cout << ans << "\n";
}
Fundamentos