Notes de Solutions APIO 2018-2024

Ces problèmes sont vraiment difficiles. (Mise à jour en cours...)

Table des matières- Notes de Solutions APIO 2018-2024

• [APIO2018] Ironman
• [APIO2018] Sélection de cercles
• [APIO2023] Cyberland
• [APIO2024] Septembre

[APIO2018] Ironman

D'abord, nous contractons les points doubles. Nous devons déterminer combien de points peuvent être traversés directement entre deux points.

On peut facilement constater qu'il est possible de définir la taille des points doubles et d'attribuer -1 aux points originaux. Ainsi, la somme des poids du chemin entre deux points correspond au nombre de points qui peuvent être traversés.

Un simple parcours en profondeur (DP) sur l'arbre suffit.

Complexité temporelle : O(n).

Code de solution``` const int N = 2e5 + 5; int n, m, s, tot; vector adj[N]; int premierArc[N], suivantArc[N << 1], destination[N << 1], compteurArc; int dfn[N], low[N], compteur; int pile[N], sommet; int poids[N], taille[N]; long long reponse; void ajouterArete(int u, int v) { suivantArc[++compteurArc] = premierArc[u]; destination[compteurArc] = v; premierArc[u] = compteurArc; } void tarjan(int u) { dfn[u] = low[u] = ++compteur; pile[++sommet] = u; s++; for(int v : adj[u]) { if(!dfn[v]) { tarjan(v); minimiser(low[u], low[v]); if(low[v] == dfn[u]) { tot++; poids[tot] = 2; while(pile[sommet] != v) { ajouterArete(tot, pile[sommet]); ajouterArete(pile[sommet], tot); poids[tot]++; sommet--; } ajouterArete(tot, pile[sommet]); ajouterArete(pile[sommet], tot); sommet--; ajouterArete(u, tot); ajouterArete(tot, u); } } else { minimiser(low[u], dfn[v]); } } } void dfs(int u, int parent) { taille[u] = (u <= n); for(int i = premierArc[u]; i; i = suivantArc[i]) { int v = destination[i]; if(v == parent) continue; dfs(v, u); reponse += 2ll * taille[u] * taille[v] * poids[u]; taille[u] += taille[v]; } reponse += 2ll * taille[u] * (s - taille[u]) * poids[u]; } void resoudre() { cin >> n >> m; REP(_, m) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } FOR(i, 1, n) poids[i] = -1; tot = n; FOR(u, 1, n) if(!dfn[u]) { s = 0; tarjan(u); dfs(u, 0); } cout << reponse << endl; }

[APIO2018] Sélection de cercles
----------------

On observe que pour deux grands cercles A et petits cercles B qui se croisent, si on définit A_l comme l'abscisse la plus à gauche du cercle A (c'est-à-dire A_l = A_x - A_r), et A_r de manière similaire,

alors on a nécessairement B_l ∈ [A_l, A_r] ou B_r ∈ [A_l, A_r].

On peut parcourir cet intervalle de manière brute.

Cependant, pour éviter les cas limites, nous pouvons simplement faire tourner le système de coordonnées d'un certain angle.

Code de solution```
const int N = 1e6 + 5;
struct PointD {
	double x, y;
	PointD(double x = 0, double y = 0): x(x), y(y) {}
};
struct PointL {
	long long x, y;
	PointL(long long x = 0, long long y = 0): x(x), y(y) {}
};
int n;
PointL cercles[N]; 
PointD Cercles[N];
int rayon[N], id[N], resultat[N];
struct Noeud {
	double x; int i;
	bool operator < (const Noeud & A) const {
		if(x == A.x) return i < A.i;
		return x < A.x;
	}
} points[N];
long long carre(long long x) {
	return x * x;
}
bool verifier(int u, int v) {
	return carre(rayon[u] + rayon[v]) - carre(cercles[u].x - cercles[v].x) - carre(cercles[u].y - cercles[v].y) >= 0;
}
PointD Rotation(PointL A, double r) {
	return PointD(A.x * cos(r) - A.y * sin(r), A.y * cos(r) + A.x * sin(r));
}
void resoudre() {
	cin >> n;
	FOR(i, 1, n) cin >> cercles[i].x >> cercles[i].y >> rayon[i];
	mt19937 generateur(time(0));
	double angle = (generateur() % 1000) / 114.;
	FOR(i, 1, n) Cercles[i] = Rotation(cercles[i], angle);
	FOR(i, 1, n) id[i] = i;
	sort(id + 1, id + n + 1, [&] (int x, int y) {
		if(rayon[x] == rayon[y]) return x < y;
		return rayon[x] > rayon[y];
	});
	FOR(i, 1, n) points[i] = {Cercles[i].x - rayon[i], i};
	FOR(i, 1, n) points[i + n] = {Cercles[i].x + rayon[i], i};
	sort(points + 1, points + n * 2 + 1);
	FOR(i, 1, n) if(!resultat[id[i]]) {
		int u = id[i];
		int L = lower_bound(points + 1, points + n * 2 + 1, (Noeud){Cercles[u].x - rayon[u], 0}) - points - 2;
		maximiser(L, 1);
		FOR(j, L, n * 2) {
			int v = points[j].i;
			if(points[j].x > Cercles[u].x + rayon[u]) break;
			if(resultat[v]) continue;
			if(verifier(u, v)) resultat[v] = u;
		}
	}
	FOR(i, 1, n) cout << resultat[i] << " "; cout << endl;
}

[APIO2023] Cyberland

Considérons un transfert en sens inverse. Soit f_{u,j} le coût du point h au point u, ayant déjà utilisé j divisions par 2. Le coût suivant à travers une arête devient alors w/(2^j). On peut effectuer la transition directement avec Dijkstra.

On remarque que w/(2^j) devient négligeable lorsque j est grand, donc on peut se limiter à j ≤ 70.

Complexité temporelle : O(NK log NK).

Code de solution``` const int N = 1e5 + 5; const int K = 70; const long long LNF = 2e18; double puiss[K + 1], dist[N][K + 1]; bool visite[N][K + 1]; vector<PII> adj[N]; double resoudre( int n, int m, int k, int fin, vector x, vector y, vector c, vector a ) { minimiser(k, K); REP(i, n) adj[i].clear(); REP(i, m) { adj[x[i]].push_back({y[i], c[i]}); adj[y[i]].push_back({x[i], c[i]}); } puiss[0] = 1; FOR(i, 1, K) puiss[i] = puiss[i - 1] / 2; priority_queue<pair<double, PII>, vector<pair<double, PII>>, greater<pair<double, PII>>> pq; REP(i, n) FOR(j, 0, K) dist[i][j] = LNF; REP(i, n) FOR(j, 0, K) visite[i][j] = 0; dist[fin][0] = 0; pq.push({0, {fin, 0}}); while(!pq.empty()) { auto h = SE(pq.top()); pq.pop(); int u, j; tie(u, j) = h; if(visite[u][j]) continue; visite[u][j] = 1; for(auto E : adj[u]) { int v, w; tie(v, w) = E; if(v == fin) continue; if(j == K) { if(dist[v][K] > dist[u][K]) { dist[v][K] = dist[u][K]; pq.push({dist[v][K], {v, K}}); } continue; } if(a[v] == 0) { if(dist[v][K] > dist[u][j] + w * puiss[j]) { dist[v][K] = dist[u][j] + w * puiss[j]; pq.push({dist[v][K], {v, K}}); } continue; } if(a[v] == 2 && j < k) { if(dist[v][j + 1] > dist[u][j] + w * puiss[j]) { dist[v][j + 1] = dist[u][j] + w * puiss[j]; pq.push({dist[v][j + 1], {v, j + 1}}); } } if(dist[v][j] > dist[u][j] + w * puiss[j]) { dist[v][j] = dist[u][j] + w * puiss[j]; pq.push({dist[v][j], {v, j}}); } } } double reponse = LNF; FOR(i, 0, K) minimiser(reponse, dist[0][i]); if(reponse > LNF / 2) return -1; else return reponse; }

[APIO2024] Septembre
---------------

Considérons une séquence individuelle : si un fils apparaît après son ancêtre, nous pouvons la contracter.

Pour plusieurs séquences, chaque point appartient certainement à un bloc, nous pouvons continuer à contracter.

Complexité temporelle : O(NM log N).

Code de solution```
const int N = 1e5 + 5;
vector<int> adj[N];
int taille[N], dfn[N], compteur;
int dernier[N];
struct SgT {
	int gauche[N << 2], droite[N << 2];
	int F[N << 2];
	void remonter(int u) {
		F[u] = max(F[u << 1], F[u << 1 | 1]);
	}
void construire(int u, int l, int r) {
	gauche[u] = l, droite[u] = r;
	if(l == r) {
		F[u] = 0;
		return;
	}
	int mid = l + r >> 1;
	construire(u << 1, l, mid);
	construire(u << 1 | 1, mid + 1, r);
	remonter(u);
}
void modifier(int u, int p, int x) {
	if(gauche[u] == droite[u]) {
		F[u] = x;
		return;
	}
	int mid = gauche[u] + droite[u] >> 1;
	if(p <= mid) modifier(u << 1, p, x);
	else modifier(u << 1 | 1, p, x);
	remonter(u);
}
int interroger(int u, int l, int r) {
	if(l <= gauche[u] && droite[u] <= r) {
		return F[u];
	}
	int mid = gauche[u] + droite[u] >> 1;
	int res = 0;
	if(l <= mid) maximiser(res, interroger(u << 1, l, r));
	if(mid < r) maximiser(res, interroger(u << 1 | 1, l, r));
	return res;
}
} t;
void dfs(int u) {
	dfn[u] = ++compteur;
	taille[u] = 1;
	for(int v : adj[u]) {
		dfs(v);
		taille[u] += taille[v];
	}
}
int resoudre(int n, int m, vector<int> p, vector<vector<int>> S) {
	compteur = 0;
	REP(i, n) adj[i].clear();
	FOR(i, 1, n - 1) adj[p[i]].push_back(i);
	dfs(0);
	vector<PII> f;
	REP(i, n - 1) f.push_back({i, i});
	for(auto A : S) {
		t.construire(1, 1, n);
		ROF(i, n - 2, 0) {
			int u = A[i];
			int val = t.interroger(1, dfn[u], dfn[u] + taille[u] - 1);
			if(val > i) f.push_back({i, val});
			t.modifier(1, dfn[u], i);
		}
	}
	REP(i, m) {
		if(i) REP(j, n - 1) {
			int l = j, r = dernier[S[i][j]];
			if(l > r) echanger(l, r);
			f.push_back({l, r});
		}
		REP(j, n - 1) dernier[S[i][j]] = j;
	}
	trier(ALL(f));
	int reponse = 0;
	int r = -1;
	for(auto h : f) {
		if(FI(h) <= r) maximiser(r, SE(h));
		else reponse++, r = SE(h);
	}
	return reponse;
}