【USACO】2019 January Contest,Platinum題解

109871 ワード

【OJ】USACO 【タイプ】タイトル記録【試合】USACO 【アルゴリズム】差分とプレフィックスと思想【アルゴリズム】ダイナミック企画【データ構造】線分樹【データ構造】スタック【資料】いい問題です【アルゴリズム】反発原理【データ構造】デカルトツリー【アルゴリズム】倍増と二分【データ構造】STテーブル

**【T1】**Redistricting
【タイトルリンク】

クリックしてリンク

を開く
【問題解リンク】

クリックしてリンク

を開く
【考え方のポイント】

はG Gを+1+1,H H Hを−1−1−1とし,元の配列接頭辞とs i s_とする.i si .

動的計画d p i=Σj=1 kd p i−j+[s i−s i−j≧0]dp_を得ることができる{i}=\sum_{j=1}^{k}dp_{i-j}+[s_i-s_{i-j}≥0] dpi=∑j=1kdpi−j+[si−si−j≥0] .

最近のk k個の位置のd p dp dp値を線分ツリー++スタックで維持し,遷移時にs i−s i−j≧0 s_を列挙するi-s_{i−j}≧0 si−si−j≧0が成立するか否かは,s s sの実行可能区間に対応する区間最小値を問い合わせればよい.

時間複雑度O(NL o g N)O(NlogN)O(NlogN).

【コード】

#include
using namespace std;
const int MAXN = 3e5 + 5;
const int INF = 2e9;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct Heap {
	priority_queue <int, vector <int>, greater <int> > Main, Delt;
	void ins(int x) {Main.push(x); }
	void del(int x) {Delt.push(x); }
	int top() {
		while (!Main.empty() && !Delt.empty() && Main.top() == Delt.top()) {
			Main.pop();
			Delt.pop();
		}
		if (Main.empty()) return INF;
		else return Main.top();
	}
} Heap[MAXN * 2];
struct SegmentTree {
	struct Node {
		int lc, rc;
		int Min;
	} a[MAXN * 4];
	int n, root, size;
	void update(int root) {
		a[root].Min = min(a[a[root].lc].Min, a[a[root].rc].Min);
	}
	void build(int &root, int l, int r) {
		root = ++size;
		if (l == r) {
			a[root].Min = INF;
			return;
		}
		int mid = (l + r) / 2;
		build(a[root].lc, l, mid);
		build(a[root].rc, mid + 1, r);
		update(root);
	}
	void init(int x) {
		n = x, root = size = 0;
		build(root, 1, n);
	}
	void del(int root, int l, int r, int pos, int val) {
		if (l == r) {
			Heap[l].del(val);
			a[root].Min = Heap[l].top();
			return;
		}
		int mid = (l + r) / 2;
		if (mid >= pos) del(a[root].lc, l, mid, pos, val);
		else del(a[root].rc, mid + 1, r, pos, val);
		update(root);
	}
	void del(int pos, int val) {
		del(root, 1, n, pos, val);
	}
	void add(int root, int l, int r, int pos, int val) {
		if (l == r) {
			Heap[l].ins(val);
			a[root].Min = Heap[l].top();
			return;
		}
		int mid = (l + r) / 2;
		if (mid >= pos) add(a[root].lc, l, mid, pos, val);
		else add(a[root].rc, mid + 1, r, pos, val);
		update(root);
	}
	void add(int pos, int val) {
		add(root, 1, n, pos, val);
	}
	int query(int root, int l, int r, int ql, int qr) {
		if (l == ql && r == qr) return a[root].Min;
		int ans = INF, mid = (l + r) / 2;
		if (mid >= ql) chkmin(ans, query(a[root].lc, l, mid, ql, min(qr, mid)));
		if (mid + 1 <= qr) chkmin(ans, query(a[root].rc, mid + 1, r, max(mid + 1, ql), qr)); 
		return ans;
	}
	int query(int l, int r) {
		if (l > r) return INF;
		else return query(root, 1, n, l, r);
	}
} ST;
char s[MAXN];
int n, k, dp[MAXN], sum[MAXN];
int main() {
	freopen("redistricting.in", "r", stdin);
	freopen("redistricting.out", "w", stdout);
	read(n), read(k);
	scanf("
%s", s + 1);
	sum[0] = n;
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1];
		if (s[i] == 'G') sum[i]++;
		else sum[i]--;
	}
	ST.init(2 * n);
	ST.add(sum[0], dp[0]);
	for (int i = 1; i <= n; i++) {
		dp[i] = min(ST.query(1, sum[i]) + 1, ST.query(sum[i] + 1, 2 * n));
		ST.add(sum[i], dp[i]);
		if (i >= k) ST.del(sum[i - k], dp[i - k]);
	}
	writeln(dp[n]);
	return 0;
}

**【T2】**Exercise Route
【タイトルリンク】

クリックしてリンク

を開く
【問題解リンク】

クリックしてリンク

を開く
【考え方のポイント】

問題は、エッジが交差するツリー上のパス対数を計算することに等しい.

は、2つの経路の交差が空であるか、または1つの経路であることに気づき、その経路の深さが最も小さいエッジx x xを列挙することを考慮し、その上のエッジをy y y yとし、x x x xを含む経路数をc n t x cnt_と記す.x cntx,x,y x,y x,yを同時に含む経路数c n t x,y cnt_{x,y} cntx,y .x x xを交差経路上で最も深い辺とする経路対数は(c n t x 2)−(c n t x,y 2)binom{cnt_x}{2}−binom{cnt_{x,y}{2}(2 cntx)−(2 cntx,y)である.c n t x , c n t x , y cnt_x,cnt_{x,y}cntx,cntx,yはツリー上の差分で得ることができる.

は、1つのパスに2つの深さが最も小さいエッジが存在する可能性があることに気づき、この場合、上記のアルゴリズムによって2回統計されるため、余分な計算の部分を除去する必要がある.すなわち,2つの経路のLc a Lca Lcaでは答えを統計し,両端が属するサブツリーと同じ経路がこのような交差を形成する可能性があり,簡単に統計すればよい.

時間複雑度O(NL o g N)O(NlogN)O(NlogN).

【コード】

#include
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXLOG = 20;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
vector <int> a[MAXN]; ll ans;
vector <pair <int, int> > b[MAXN];
int cnt[MAXN], exclude[MAXN];
int depth[MAXN], father[MAXN][MAXLOG];
void work(int pos, int fa) {
	depth[pos] = depth[fa] + 1;
	father[pos][0] = fa;
	for (int i = 1; i < MAXLOG; i++)
		father[pos][i] = father[father[pos][i - 1]][i - 1];
	for (unsigned i = 0; i < a[pos].size(); i++)
		if (a[pos][i] != fa) work(a[pos][i], pos);
}
int lca(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (depth[father[x][i]] >= depth[y]) x = father[x][i];
	if (x == y) return x;
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (father[x][i] != father[y][i]) {
			x = father[x][i];
			y = father[y][i];
		}
	return father[x][0];
}
int jump(int x, int y) {
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (depth[father[x][i]] > depth[y]) x = father[x][i];
	return x;
}
void getans(int pos, int fa) {
	for (auto x : a[pos])
		if (x != fa) {
			getans(x, pos);
			cnt[pos] += cnt[x];
			exclude[pos] += exclude[x];
		}
	ans += (cnt[pos] - 1ll) * cnt[pos] / 2;
	ans -= (exclude[pos] - 1ll) * exclude[pos] / 2;
}
int main() {
	freopen("exercise.in", "r", stdin);
	freopen("exercise.out", "w", stdout);
	int n, m; read(n), read(m), m -= n - 1;
	for (int i = 1; i <= n - 1; i++) {
		int x, y; read(x), read(y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	work(1, 0);
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		read(x), read(y), z = lca(x, y);
		cnt[x]++, cnt[y]++, cnt[z] -= 2;
		exclude[x]++, exclude[jump(x, z)]--;
		exclude[y]++, exclude[jump(y, z)]--;
		if (x != z && y != z) b[z].emplace_back(x, y);
	}
	getans(1, 0);
	for (int i = 1; i <= n; i++) {
		map <pair <int, int>, int> exclude;
		for (auto c : b[i]) {
			int x = jump(c.first, i);
			int y = jump(c.second, i);
			if (x > y) swap(x, y);
			exclude[make_pair(x, y)]++;
		}
		for (auto x : exclude)
			ans -= (x.second - 1ll) * x.second / 2;
	}
	writeln(ans);
	return 0;
}

**【T3】**Train Tracking 2
【タイトルリンク】

クリックしてリンク

を開く
【問題解リンク】

クリックしてリンク

を開く
【考え方のポイント】

は、区間の最大値の位置を見つけることを考慮し、問題を両側の処理に再帰する.

現在の区間[l,r][l,r][l,r]に対応するa l,a l+1,a l+2,.,a r − k + 1 a_l,a_{l+1},a_{l+2},...,a_{r-k+1} al,al+1,al+2,...,Ar−k+1が等しいと,問題は明らかに動的計画で解決でき,すなわち,[l,r][l,r][l,r]のすべての数が最大値を超えず,連続するk kの個数ごとに最大値が存在することを保証できる.

そうでなければ、区間の最大値になるように、決定された位置を見つけることができます.

具体的には、M a x=m a x{a l,a l+1,a l+2,.,a r−k+1}Max=max{a_l,a_{l+1},a_{l+2},...,a_{r-k+1}}Max=max{al,al+1,al+2,...,ar−k+1},a l=M a x a_l=Max al=Maxは、[l,l+k−1][l,l+k−1][l,l+k−1][l,l+k−1]に区間最大値が存在することを示し、a p o s

それ以外の場合、すなわちa l

は両側の処理に再帰すればよい.

具体的な実装には、S T STテーブルを使用する必要がある.

時間複雑度O(NL o g N)O(NlogN)O(NlogN).

【コード】

#include
using namespace std;
const int MAXN = 2e5 + 5;
const int P = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
namespace rmq {
	const int MAXN = 1e5 + 5;
	const int MAXLOG = 18;
	int Max[MAXN][MAXLOG], Min[MAXN][MAXLOG], Log[MAXN];
	int queryMax(int l, int r) {
		int len = r - l + 1, tmp = Log[len];
		return max(Max[l][tmp], Max[r - (1 << tmp) + 1][tmp]);
	}
	int queryMin(int l, int r) {
		int len = r - l + 1, tmp = Log[len];
		return min(Min[l][tmp], Min[r - (1 << tmp) + 1][tmp]);
	}
	void init(int *a, int n) {
		for (int i = 1; i <= n; i++) {
			Min[i][0] = a[i];
			Max[i][0] = a[i];
			Log[i] = Log[i - 1];
			if ((1 << (Log[i] + 1)) <= i) Log[i]++;
		}
		for (int t = 1; t < MAXLOG; t++)
		for (int i = 1, j = (1 << (t - 1)) + 1; j <= n; i++, j++) {
			Max[i][t] = max(Max[i][t - 1], Max[j][t - 1]);
			Min[i][t] = min(Min[i][t - 1], Min[j][t - 1]);
		}
	}
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
int n, k, a[MAXN];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int same(int len, int Max) {
	static int dp[MAXN];
	int sum = 0; dp[0] = 1; 
	for (int i = 1; i <= len; i++) {
		sum = 1ll * sum * Max % P;
		update(sum, dp[i - 1]);
		if (i - k - 1 >= 0) update(sum, P - 1ll * dp[i - k - 1] * power(Max, k) % P);
		dp[i] = sum;
	}
	int ans = 0;
	for (int i = 0; i <= len && i <= k - 1; i++)
		update(ans, 1ll * dp[len - i] * power(Max, i) % P);
	return ans;
}
int solve(int l, int r, int RMax) {
	int len = r - l + 1;
	if (len < k) return power(RMax + 1, len);
	int Max = rmq :: queryMax(l, r - k + 1);
	int Min = rmq :: queryMin(l, r - k + 1);
	if (Max == Min) return same(len, Max);
	if (a[l] == Max) {
		int ql = l, qr = r - k + 1;
		while (ql < qr) {
			int mid = (ql + qr) / 2;
			if (rmq :: queryMin(l, mid) != Max) qr = mid;
			else ql = mid + 1;
		}
		int pos = ql - 1;
		return 1ll * solve(l, pos - 1, Max) * solve(pos + 1, r, Max) % P;
	} else {
		int ql = l, qr = r - k + 1;
		while (ql < qr) {
			int mid = (ql + qr) / 2;
			if (rmq :: queryMax(l, mid) == Max) qr = mid;
			else ql = mid + 1;
		}
		int pos = ql + k - 1;
		return 1ll * solve(l, pos - 1, Max) * solve(pos + 1, r, Max) % P;
	}
}
int main() {
	freopen("tracking2.in", "r", stdin);
	freopen("tracking2.out", "w", stdout);
	read(n), read(k);
	for (int i = 1; i <= n - k + 1; i++) {
		read(a[i]);
		a[i] = 1e9 - a[i];
	}
	rmq :: init(a, n - k + 1);
	writeln(solve(1, n, 1e9));
	return 0;
}

yzoj 2377賛芬梭哈題解

遡及法の概要