Particle

競技プログラミングについての雑記

SRM 670 Div1 Easy Bracket107

s に含まれる 1 文字を別な場所に動かすと、LCS(s, t) が |s| または、|s|-1 になるようにできる。

s >= 4 であるので、必ずLCS(s, t) が s -1 かつ、正しくカッコが対応している t が存在する。

t の候補 (LCS(s, t) が |s|-1 であるようなすべての文字列) は、高々 O(N^2) であるので全候補に対し、カッコの対応を計算すれば、O(N^3) で計算できる。

string s;
int n;
#define N 60
int dp[N][N][2];
int sum[N];
set<string> st;

class Bracket107 {
	public:
	int check(const string &t){
		int cnt = 0;
		rep(i, n){
			if(t[i]=='(') cnt++;
			else cnt--;
			if(cnt<0) return 0;
		}
		return 1;
	}
	int yetanother(string s_) {
		s=s_;
		n = s.size();
		st.clear();
		st.insert(s);
		rep(i, n-1){
			string t = s;
			for(int j = i; j < n-1; j++){
				swap(t[j], t[j+1]);
				st.insert(t);
			}
		}
		for(int i = n-1; i > 0; i--){
			string t = s;
			for(int j = i; j > 0; j--){
				swap(t[j], t[j-1]);
				st.insert(t);
			}
		}
		int res = -1;
		for(auto &t: st){
			if(check(t)){
				res++;
			}
		}
		return res;
	}
};

SRM 666 Div1 Medium SumOverPermutations

左端のビンから考え、DP をする。
dp[i: i 番目のビン][j: i 番目のビンは、左の i 個のビンの中で j 番目に使われる][k: (i+1)番目のビンが i 番目のビンよりあとなら 1、そうでないなら 0] ::= 条件を満たす状態数
とし、累積和を計算しながら DP を計算する。

#define N 4010
int dp[N][N][2];

class SumOverPermutations {
	public:
	int findSum(int n) {
		if(n==1) return 1;
		mset(dp, 0);
		dp[0][1][0] = 1;
		for(ll i = 1; i <= n; i++){
			for(ll j = 0, sum = 0; j < i; j++){
				(sum+=dp[i-1][j][1])%=mod;
				(dp[i][j+1][0]+=sum*(n-2)%mod)%=mod;
				(dp[i][j+1][1]+=sum*(n-1)%mod)%=mod;
			}
			for(ll j = i, sum = 0; j > 0; j--){
				(sum+=dp[i-1][j][0])%=mod;
				(dp[i][j][0]+=sum*(n-1)%mod)%=mod;
				(dp[i][j][1]+=sum*(n)%mod)%=mod;
			}
		}
		ll res = 0;
		rep(i, n+1) (res+=dp[n][i][1])%=mod;
		return (res+mod)%mod;
	}
};

SRM 666 Div1 Easy WalkOverATree

頂点 0 まで戻ってくる場合の問題について考える。
すると、無駄な探索をしなければ、L/2+1 個の頂点に到達することができる。
頂点 0 まで戻る必要が無い場合には、深さが最大となる頂点までの距離の分 (すなわち深さの最大値) だけ移動距離を増やせるため、L' = L+ max{depth} として、L'/2+1 個の頂点に到達できる。
頂点数が L に対して小さいときは、頂点数との min を取ることを忘れないことに注意する。

#define N 60
int d[N];

class WalkOverATree {
	public:
	int maxNodesVisited(vector <int> p, int L) {
		int m = p.size();
		rep(i, m) d[i+1] = d[p[i]]+1;
		int mx = 0;
		rep(i, m+1) chmax(mx, d[i]);
		if(mx>=L) return min(m+1, L+1);
		return min(m+1, (L+mx)/2+1);
	}
};

SRM 661 Div1 Medium ColorfulLineGraphs

求める値は、簡単な考察で分かる。(各 i に対して、どこに辺を張るかを考えると、辺を張るときは K-1 倍、張らないとき K 倍となる)
M が 10^6 以下と小さいので、1 周期分計算し、周期の回数(N/M回)だけかけ、周期からはみ出す分(N%M の部分)を掛け合わせれば良い。

N, K の値が大きいのでオーバーフローなどに注意

ll pow_mod(ll a, ll r, ll m ){
	ll x = 1;
	while(r){
		if(r&1) (x*=a)%=m;
		(a*=a)%=m;
		r>>=1;
	}
	return x;
}
 
class ColorfulLineGraphs {
	public:
	int countWays(long long N, long long K, int M) {
		ll mod = M;
		K--;
		if(K==0) return 1;
		ll res = 1;
		while(N%M){
			(res*=(N%mod*K%mod+1))%=mod;
			N--;
		}
		ll res2 = 1;
		rep(i, M) (res2*=i*K%mod+1)%=mod;
		(res*=pow_mod(res2, N/M, M))%=mod;
		return res;
	}
};

SRM 661 Div1 Easy MissingLCM

lcm は、各素数ごとに max を取るのと同じなので、各素数ごとに独立に M の lower bound を計算できる。

class MissingLCM {
	public:
		bool isPrime(ll x){
			if(x<=1) return false;
			for(ll i = 2; i*i <= x; i++) if(x%i==0) return false;
			return true;
		}
	int getMin(int N) {
		ll res = N+1;
		for(ll i = 2; i <= N; i++){
			if(!isPrime(i)) continue;
			ll j = i;
			while(j*i<=N) j *= i;
			ll x = (N/j+1)*j;
			chmax(res, x);
		}
		return res;
	}
};

SRM 660 Div1 Medium Privateparty

各頂点に対して独立に期待値を求める。
有向グラフにして考える。
開始頂点を w とする。
頂点 u から v に辺が張られているとする。u が先に招待される場合は、自明に u は招待される。
v が先に招待される場合は、v の先の頂点まで見る必要があるので DFS を行う。
開始頂点 w から u の距離が k のとき、前者の係数は、1-1/(k+2), 後者の係数は、 1/(k+2) となる。(後者の場合は、w から u までのパスに含まれるすべての頂点より先に招待される必要があり、w から v までのパスに含まれる頂点数が k+2 個であることから分かる)

一見閉路があるように見えるが、1週してきた場合は、頂点が無い場合と同一視できる。

#define N 100
bool used[N];
vector<int> a;

class Privateparty {
	public:
	double dfs(int u, int k){
		used[u] = true;
		if(used[a[u]]){
			used[u] = false;
			return 1.0;
		}
		double y = dfs(a[u], k+1);
		used[u] = false;
		return (k-1.0)/k+(1.0)/k*(1-y);
	}
	double getexp(vector <int> a_) {
	a=a_;
		int n = a.size();
		double res = 0.0;
		rep(i, n) res += dfs(i, 2);
		return res;
	}
};

SRM 659 Div1 Medium CampLunch

想定解とはおそらく少し違う方法で解いた (定数倍高速化を頑張って TLE ギリギリなので、想定解が思いつくならそちらの方がよい。)

まず、i 日目で隣り合う 2 人がどうペアになるか全列挙し、高速ゼータ変換を行う。すると、i 日目の食事で、ペアにできない人の集合を固定したときに、何通りあるかが計算できる。
各人の状態を「前の日と2連続」、「次の日と2連続」、「どちらでもない」の 3 通りにして DP をすると、計算量が O(N*3^M)になる。(DP テーブルとして持つのは、「前の日と2連続」、「それ以外」の 2 通り)
定数倍高速化することで 1.95 sec くらいになる。(ローカルでは、サンプルが、3.6 sec)

#define L 16
ll dp[L+1][1<<L];
ll dp2[1<<L];
vector<string> a;

class CampLunch {
	public:
	int f(int i, int j){
		return a[i][j]-'A';
	}
	int count(int n, int m, vector <string> a_) {
		a=a_;
		mset(dp, 0);
		ll mask = (1<<m)-1;
		dp[0][0] = 1;
		rep(i, n){
			mset(dp2, 0);
			rep(j, 1<<(m-1)){
				int j2 = j;
				bool ok = true;
				while(j2){
					if((j2&3)==3) ok = false;
					j2 >>= 1;
				}
				if(!ok) continue;
				int t = 0;
				rep(k, m-1){
					if(1&(j>>k)){
						t |= 1<<f(i, k);
						t |= 1<<f(i, k+1);
					}
				}
				dp2[t^mask]++;
			}
			rep(j, m) rep(b, 1<<m) if(0==(1&(b>>j))) dp2[b] += dp2[b|(1<<j)];
			rep(j, 1<<m){
				for(int k = j; ;k=(k-1)&j){
					(dp[i+1][k]+=dp[i][j&~k]*dp2[j]);
					if(k==0) break;
				}
			}
			rep(j, 1<<m) dp[i+1][j]%=mod;
		}
		return dp[n][0];
	}
};