Atcoder Dwango Programming Contest 6th

\(A\) \(Falling\) \(Asleep\)

Title Link

\(description:\)

Give you a song list \ (, \) \ (n \) song name \ (s_i \) and playback duration \ (t_i \) \ (, \)

Reading a song name \ (st, \) requires calculating the total playing time of all songs after this song \ (. \) in the song list

\(solution:\)

Violence \ (. \) time complexity \ (O(n + \sum|s_i| \)

\(code:\)

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0',c = getchar();
    return x;
}
template <typename T> void read(T &x){
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
int n; string st,s[500]; int t[500];
int main(){
	cin >> n;
	for (int i = 1; i<= n; ++i) cin >> s[i] >> t[i];
	cin >> st; 
	int id = -1; long long ans = 0;
	for (int i = 1; i <= n; ++i) if (s[i] == st) id = i;
	for (int i = id+1; i <= n; ++i) ans += t[i];
	cout << ans << endl;
    return 0;
}

\(B\) \(Fusing\) \(Slimes\)

Title Link

\(description :\)

There are \ (n(n ≤ 10 ^ 5) \) stones \ (, \) each stone has its initial coordinates \ (x_i. \)

Each time, you will randomly select a pile \ (, \) that is not on the far right, move the pile to the position \ (, \) of the pile of stones closest to it on its right, and combine the two piles of stones into a pile \ (. \)

Find the sum of the moving distance of \ (, \) stones in all cases \ (, \) times \ ((n-1)! \)\ (.\)

Answer pair \ (P = 1e9 + 7 \) modulo \ (. \)

\(solution :\)

Consider a distance \ (d_i = x_{i+1} - x_i \)

Definition $dp[n] = $the expected number of times that a \ (n \) stone \ (, \) passes a distance after the \ (n \) stone is moved

It is not difficult to get \ (dp[i] = dp[i-1] + 1/i \)

You can directly calculate the distance of each pair of answers (\.)

Time complexity \ (O(n). \)

\(code :\)

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0',c = getchar();
    return x;
}
template <typename T> void read(T &x){
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int P = 1e9 + 7,N = 500050;
int n,fac[N],inv[N];
int x[N];
int f[N];
long long ans,now;
int main(){
	int i;
	read(n);
	for (i = 1; i <= n; ++i) read(x[i]);
	for (fac[0] = i = 1; i <= n; ++i) fac[i] = 1ll*fac[i-1]*i%P;
	for (inv[0] = inv[1] = 1,i = 2; i <= n; ++i) inv[i] = 1ll*inv[P%i]*(P-P/i)%P;
	for (i = 1; i <= n; ++i){
		int prob; prob = inv[i];
		f[i] = 1ll*prob*(f[i-1]+1) % P;
		f[i] += 1ll*(P+1-prob)*f[i-1] % P;
		f[i] %= P;
	}
	ans = 0;
	for (i = 1; i <= n-1; ++i){
		int dist = x[i+1] - x[i];
		ans = (ans + 1ll*dist*f[i]%P)%P;
	} 
	cout << 1ll*fac[n-1]*ans%P << endl;
    return 0;

\(C\) \(Cookie\) \(Distribution\)

Title Link

$description : $

There are \ (n \) individuals \ (, \) you want to send them candy \ (. \) in \ (k \) days

Read in \ (a_1.. a_k, \), where \ (a_i \) means that on the \ (I \) day \ (a_i \) individuals \ (, \) will be evenly and randomly selected from \ (n \) individuals, and each of them will be given a sugar \ (. \)

Record \ (c_i \) as the number of candy sent by the \ (I \) \ (, \) and find the expectation \ (. \) of \ (\ Pi c_i \)

\(n<=10^3,k<=20\)

\(solution:\)

Seeking \ (\ prod c_i \) is equivalent to seeking the number of schemes to choose a sugar from each of the \ (n \) individuals

Consider enumerating \ (x_i \) to indicate when the candy selected from the \ (I \) person came from \ (. \)

\It doesn't matter what (x_i \) is \ (, \) what matters is that \ (cnt2_i: \) indicates how many \ (x_j\) \(=\) \(i \)

What is the contribution of this choice to the answer

\[\large \prod^{k}_{i=1} C^{a_k-cnt2_k}_{n-cnt2_k} \times \prod_{i=1}^{k} (cnt2_i!)^{-1} \times n! \]

Then use a \ (O(nk^2) dp \) to solve this problem \ (. \)

\(code :\)

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0',c = getchar();
    return x;
}
template <typename T> void read(T &x){
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

const int N = 1050,K = 20 + 5,P = 1e9 + 7;
int n,k,a[K];
int fac[N],nfac[N],inv[N];
inline int C(int n,int m){ return (n<m||n<0||m<0) ? 0 : 1ll*fac[n]*nfac[m]%P*nfac[n-m]%P; }
int t[K][N];
int dp[K][N];
int main(){
	int i,j,e;
	read(n),read(k); for (i = 1; i <= k; ++i) read(a[i]);
	inv[0] = fac[0] = nfac[0] = inv[1] = fac[1] = nfac[1] = 1;
	for (i = 2; i <= n; ++i){
		fac[i] = 1ll*fac[i-1]*i%P;
		inv[i] = 1ll*(P-P/i)*inv[P%i]%P;
		nfac[i] = 1ll*nfac[i-1]*inv[i]%P;
	} 
	for (i = 1; i <= k; ++i)
	for (j = 0; j <= n; ++j) t[i][j] = 1ll*C(n-j,a[i]-j)*nfac[j]%P;
	dp[0][0] = 1;
	for (i = 1; i <= k; ++i)
	for (j = 0; j <= n; ++j){
		dp[i][j] = 0;
		for (e = 0; e <= j; ++e) dp[i][j] = (dp[i][j] + 1ll * t[i][e] * dp[i-1][j-e]) % P;
	}
	int ans = 1ll * dp[k][n] * fac[n] % P; 
    cout << ans << endl;
	return 0;
}

\(D\) \(Arrangement\)

Title Link

\(description :\)

Give you a picture \ (G,\) \(G \) has \ (n \) points \ (, \) \ (n*(n-2) \) directed edges \ (. \)

The complementary graph of graph \ (G \) is a directed graph \ (. \) with all point out degrees \ (= 1 \) \ ((\) may have self ring \ () \)

Find a Hamiltonian path with the smallest dictionary order \ (, \) and output \ (- 1. \) if it does not exist

\(n<=10^5\)

\(solution :\)

First of all, if the scale is small enough \ ((n < = 8) \), it can be directly violent \ (O(n!) \)

Then we consider dealing with the answer \ (. \) for the larger case of \ (n \)

Record $cnt_i = $how many \ (, \) are in the current figure (a_j = i \)

If there is a point \ (P \) that satisfies \ (cnt_p = n-1 \), then we must choose this point as the first point of the path \ (. \)

If there is no such point \ (, \), we can select the point with the lowest number \ (. \) among the current points

Then the problem becomes a subproblem with the scale of \ (n-1 \) \ (, \) but there is an additional limit \ (. \) that cannot start with a certain number

Then we can write a data structure that supports query \ (cnt \) maximum value \ (, \) \ (cnt \) single point modification and query the lowest number of the current point set \ (, \) delete a point \ (, \) and write another \ (O(n!) \) Violence is enough \ (. \)

Complexity \ (O(8! +nlogn) \)

\(code:\)

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0',c = getchar();
    return x;
}
template <typename T> void read(T &x){
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int N = 100050;
int n,a[N];

namespace subtask0{
	int ans[100],vis[100]; bool ok;
	int p[100];
	inline void chk(){
		for (int i = 2; i <= n; ++i) if (a[ans[i-1]] == ans[i]) return;
		ok = 1; for (int i = 1; i <= n; ++i) p[i] = ans[i];
		return; 
	}
	inline void dfs(int dep){
		if (ok) return;
		if (dep > n){ chk(); return; }
		for (int i = 1; i <= n; ++i) if (!vis[i]){
			vis[i] = 1,ans[dep] = i;
			dfs(dep+1);
			vis[i] = 0;
		}
	}
	inline void solve(){
		ok = 0; memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); dfs(1);
		if (!ok){ puts("-1"); return; }
		for (int i = 1; i <= n; ++i) cout << p[i] << ((i<n) ? (' '):('\n'));
	}
}

int mx[N<<2],mxi[N<<2],data[N<<2],cnt[N];
inline void Build(int o,int l,int r){
	if (l^r){
		int mid = l+r>>1; Build(o<<1,l,mid); Build(o<<1|1,mid+1,r);
		mx[o] = max(mx[o<<1],mx[o<<1|1]); data[o] = min(data[o<<1],data[o<<1|1]);
		mxi[o] = mxi[ (mx[o<<1]>mx[o<<1|1]) ? (o<<1) : (o<<1|1) ];
		return;
	}
	mx[o] = cnt[l]; data[o] = (mx[o] >= 0) ? (l) : (n+1); mxi[o] = l;
}
inline int Ask(int o,int l,int r,int p){
	if (l==r) return mx[o];
	int mid = l+r>>1; return (p<=mid) ? Ask(o<<1,l,mid,p) : Ask(o<<1|1,mid+1,r,p);
} 
inline void Add(int o,int l,int r,int p,int v){
	if (l==r){ mx[o]=v; data[o] = (mx[o] >= 0) ? (l) : (n+1); return; }
	int mid = l+r>>1; if (p<=mid) Add(o<<1,l,mid,p,v); else Add(o<<1|1,mid+1,r,p,v);
	mx[o] = max(mx[o<<1],mx[o<<1|1]); data[o] = min(data[o<<1],data[o<<1|1]);
	mxi[o] = mxi[ (mx[o<<1]>mx[o<<1|1]) ? (o<<1) : (o<<1|1) ];
}
inline int Nowv(){ return data[1]; }
inline int Query(int pos){ if (pos==0) return -1; return Ask(1,1,n,pos); }
inline void Modify(int x,int v){ cnt[x] = v; Add(1,1,n,x,v); }


int ans[N];
int vis[N],nowc[N],lc;
int qwq;
inline void chk(){
	for (int i = qwq; i <= n; ++i) if (ans[i]==a[ans[i-1]]) return;
	for (int i = 1; i <= n; ++i) write(ans[i]),putchar((i<n)?(' '):('\n'));
	exit(0);
}
inline void dfs(int dep){
	if (dep>n){ chk(); return; }
	for (int i = 1; i <= lc; ++i) if (!vis[i]){
		vis[i] = 1;
		ans[dep] = nowc[i];
		dfs(dep+1);
		vis[i] = 0;
	}
}
inline void solve_force(int l,int r){
	qwq = l;
	for (int i = 1; i <= n; ++i) if (Query(i) >= 0) nowc[++lc] = i,vis[lc] = 0;
	dfs(l);
}
inline bool unproperty(){
	for (int i = 1; i <= n; ++i) cnt[i] = 0;
	for (int i = 1; i <= n; ++i) ++cnt[ans[i]];
	for (int i = 1; i <= n; ++i) if (cnt[i] != 1) return 1;
	for (int i = 2; i <= n; ++i) if (ans[i] == a[ans[i-1]]) return 1;
	return 0;
}
int main(){
	int i,banp,ret,siz,p;
	int pp,val;
	read(n);
	for (i = 1; i <= n; ++i) read(a[i]);
	for (i = 1; i <= n; ++i) if (a[i]==i) a[i]=0;
	for (i = 1; i <= n; ++i) ++cnt[a[i]];
//	if (n==2){ puts("-1"); return 0; }
	if (n<=8){ subtask0::solve(); return 0; }
	
	Build(1,1,n);
	for (banp = 0,siz = n,i = 1; i <= n; ++i,--siz){
		if (siz <= 6){
			solve_force(i,n); 
		}
		banp = a[ans[i-1]];
		if (banp != 0 && (ret=Query(banp)) >= 0){
			Modify(banp,-1);
			if (mx[1] == siz-1){
				p = mxi[1];
				ans[i] = p;
				Modify(ans[i],-1);
			}
			else{
				p = data[1];
				ans[i] = p;
				Modify(ans[i],-1);
			}
			pp = a[ans[i]];
			if ((val=Query(pp))>=0){ --val; Modify(pp,val); }
			Modify(banp,ret);
		}
		else{
			if (mx[1] == siz-1){
				p = mxi[1];
				ans[i] = p;
				Modify(ans[i],-1);
			}
			else{
				p = data[1];
				ans[i] = p;
				Modify(ans[i],-1);
			}
			pp = a[ans[i]];
			if ((val=Query(pp))>=0){ --val; Modify(pp,val); }
		}
	}
	if (unproperty()){ puts("-1"); return 0; }
	for (i = 1; i <= n; ++i) write(ans[i]),putchar((i<n)?(' '):('\n'));
}

\(E\) \(Span\) \(Covering\)

Title Link

\(description:\)

There are \ (n \) segments with length \ (l_i \) \ (. \)

You want to put these segments on a coordinate axis with a length of \ (X \) \ (\) \ (n < = 100 \) \ (X < = 500 \) \ () \)

And if a condition \ (: \) is met, it cannot cover the outside \ (, \) and there cannot be a place that is not covered by any line segment \ (. \)

Number of solutions \ (. \)

\(solution:\)

First, sort \ (l_i \) from large to small \ (. \)

Consider a \ (dp: \)

$f[i][j][k] = \ (I \) intervals before $constitute \ (j \) adjacent open intervals \ (, \) and the number of schemes with a total length of \ (K \) \ (. \)

There are three types of transfers \ (: \)

\(1. \) open a new interval \ (; (J - > j + 1) \)

\(2. \) merge the current interval and the interval I added into one interval \ (; (J - > J) \)

\(3. \) merge two adjacent intervals into one interval \ ((J - > J-1) \)

The length of the \ (1 \) transfer is determined \ (, \) is \ (k + len \)

The length of the \ (2 \) \ (3 \) transfer is \ (. \) that needs to be enumerated

It seems that the complexity is \ (O(n^2X^2), \), but when enumerating to \ (I \), only the state of \ (k * l_i < = J \) is useful \ (. \)

Therefore, the complexity is \ (O(?? \) can pass \ () \ (\) as if \ (O(nX^2)? \)\ ()\)

\(code:\)

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0',c = getchar();
    return x;
}
template <typename T> void read(T &x){
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int N = 100 + 5,M = 1050,P = 1e9 + 7;
int n,m;

int f[N][M],g[N][M];
inline void upd(int &x,int y){ x+=y; x>=P?x-=P:0; x<0?x+=P:0; }
inline void DP(int L){
	int i,j,k;
//	cout <<"DP " << endl;
//	for (i = 1; i <= n; ++i,cout << endl)
//	for (j = 1; j <= m; ++j) cout <<f[i][j] << ' ';
	
	for (i = 1; i <= n; ++i)
	for (j = 1; j <= m; ++j) g[i][j] = f[i][j],f[i][j] = 0;
	for (i = 1; i <= n; ++i)
	for (j = 1; j <= m; ++j) if (g[i][j]>0){
		upd(f[i+1][j+L],1ll*(i+1)*g[i][j]%P);
		upd(f[i][j],1ll*g[i][j]*(P+j-i*(L-1))%P);
		for (k = 1; k < L; ++k) upd(f[i][j+k],2ll*g[i][j]%P*i%P);
		for (k = 0; k < L-1; ++k) upd(f[i-1][j+k],1ll*g[i][j]*(L-k-1)%P*(i-1)%P);
	}
}
int a[N];
int main(){
	int i,j;
	int rm;
	read(n),read(m); for (i = 1; i <= n; ++i) read(a[i]),++a[i]; rm = m; m += 1;
	sort(a+1,a+n+1); reverse(a+1,a+n+1);
	memset(f,0,sizeof(f)); f[1][a[1]] = 1;
	for (i = 2; i <= n; ++i) DP(a[i]);
	
//	cout <<"DP " << endl;
//	for (i = 1; i <= n; ++i,cout << endl)
//	for (j = 1; j <= m; ++j) cout <<f[i][j] << ' ';
	int ans = 0;
	for (i = 1; i <= 1; ++i) ans += f[i][rm+i],ans %= P;
    cout << ans << endl;
	return 0;
}

Tags: atcoder

Posted by poisedforflight on Thu, 19 May 2022 14:34:10 +0300