Particle

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

AGC 017 E Placing Squares

E - Placing Squares

N を増やしたときの差分について観察するとうまく解けるようになる。
M = 0 の場合でも難しいので、まずは M = 0 の場合を考える。
右端の正方形が k*k で、それ以外の正方形の面積の積(=重み)が a であるような状況を考える。
右端に辺を追加すると、
右端の正方形が (k+1)*(k+1)、重みが a になるか、
右端の正方形が 1*1、重みが k*k*a になる。
よく見ると、
(重み)*(右端の正方形の面積) の総和
(重み)*(右端の正方形の辺の長さ) の総和
(重み)*(右端の正方形の個数) の総和
を線形変換しているので、行列累乗で解ける。(試していないが、editorial に書かれている解法で出てくる行列と同じになるはず。)

M が 0 でないときも、遷移が少し変わるだけなので、そこだけ違う行列をかければよい。

typedef vector<ll> vec;
typedef vector<vec> mat;
#define M 100010
ll n, m;
ll d[M];
 
void mul(mat &A, mat &B){
	int n = A.size();
	mat C(n, vec(n, 0));
	rep(k, n) rep(i, n) rep(j, n) C[i][j]+=A[i][k]*B[k][j]%mod;
	A.swap(C);
	rep(i, n) rep(j, n) A[i][j] %= mod;
}
 
int main(){
	scanf("%lld%lld", &n, &m);
	rep(i, m) scanf("%lld",d+i+1);
	d[m+1] = n;
	mat A(3, vec(3, 1));
	A[0][0] = A[0][1] = 2;
	A[2][1] = 0;
	mat B(A);
	rep(i, 3) B[i][0]--;
	mat X(3, vec(3, 0));
	rep(i, 3) X[i][i] = 1;
	rep(i, m+1){
		if(i) mul(X, B);
		ll t = d[i+1]-d[i]-1;
		mat C(A);
		while(t){
			if(t&1) mul(X, C);
			mul(C, C);
			t >>= 1;
		}
	}
	ll res = 0;
	rep(i, 3) res += X[0][i];
	printf("%lld\n", (res+mod)%mod);
	return 0;
}

SRM 691 Div1 Medium Moneymanager

X = 0 であるときは、a/b が大きい方が前に来るようにすればよい。
前半・後半に分ける集合を固定したときも、それぞれの集合内では、a/b が大きい方が前に来るのが最適となっている。
あとは、前半・後半にどう分けるかが問題となるのだが、a/b でソートして、後半部分の b の合計を固定すると DP で計算することができる。
自分の実装では、a/b で降順にソートし、前半・後半部分の後ろから敷き詰めていくような DP で解いた。(4 次元の状態数を持つことになるので MLE に注意する)
計算量は、O(N^4*maxB^2)で、少しだけシビアなので、あまり定数倍が重くなりすぎないようにする。

ll dp[2][30][260][260];

class Moneymanager {
	public:
	int getbest(vector <int> a, vector <int> b, int X) {
		int n = a.size()/2;
		vector<P> v(2*n);
		rep(i, 2*n) v[i] = P(a[i], b[i]);
		auto f = [&](const P &i, const P &j){ return i.fst*j.snd<j.fst*i.snd;};
		sort(all(v), f);
		ll sum = 0;
		mset(dp, -1);
		rep(k, 260) dp[0][0][0][k] = 0;
		rep(i, 2*n){
			int t = i%2;
			mset(dp[!t], -1);
			for(int j = 0; j <= min(i, n); j++){
				for(int k = 0; k < 260; k++){
					for(int l = 0; l <= k; l++){
						if(dp[t][j][l][k]<0) continue;
						chmax(dp[!t][j][l][k], dp[t][j][l][k]+(sum-l+k+v[i].snd)*v[i].fst);
						if(l+v[i].snd<=k) chmax(dp[!t][j+1][l+v[i].snd][k], dp[t][j][l][k]+(l+v[i].snd)*(v[i].fst));
					}
				}
			}
			sum += v[i].snd;
		}
		ll res = -INF;
		rep(i, 300){
			if(dp[0][n][i][i]>=0) chmax(res, dp[0][n][i][i]+X*i);
		}
		return res;
	}
};

SRM 678 Div1 Medium TheEmpireStrikesBack

まず、LIS になるように余分な惑星を取り除く (x1<=x2 && y1<=y2 となっているときは、2 番目を選ぶほうが明らかに嬉しい+2 番目の惑星が取り除かれるときは、1 番目の惑星も取り除かれるので、1 番目の惑星は除外して考えて良い)
すると、T を固定したときに greedy にミサイルを打つ回数の最小値が求められるようになるので、二分探索する。

class TheEmpireStrikesBack {
	public:
	int find(int AX, int BX, int CX, int AY, int BY, int CY, int N, int M) {
		set<P> st;
		P p = P(AX, AY);
		st.insert(p);
		rep(i, N-1){
			p = P((p.fst*BX+CX)%mod, (p.snd*BY+CY)%mod);
			st.insert(p);
		}
		for(auto it = st.begin(); it!=st.end();){
			auto it2 = it;
			++it2;
			if(it2==st.end()) break;
			if(it->snd<=it2->snd){
				st.erase(it);
				it = it2;
				if(it!=st.begin()) --it;
			} else ++it;
		}
		vector<ll> x, y;
		for(auto &&val: st){
			x.pb(val.fst);
			y.pb(-val.snd);
		}
		int n = x.size();

		ll lb = -1, ub = 1e9;
		while(ub-lb>1){
			ll md = (lb+ub+1)/2;
			int m = 0;
			int pos = 0;
			while(pos<n){
				int pos2 =upper_bound(all(y), y[pos]+md)-y.begin()-1;
				pos = upper_bound(all(x), x[pos2]+md)-x.begin();
				m++;
			}
			(m<=M?ub:lb)=md;
		}
		return ub;
	}
};

SRM 675 Div1 Medium LimitedMemorySeries1

長さ n (<= 5e6) の数列が与えられる。k 番目に小さい値を答えるクエリが q (<= 100) 回与えられる。
1 MB 以下、10 sec 以下でクエリの答えの総和を求める問題。

問題文にも書かれているように、メモリが足りないので数列を保持することはできない。
数列の要素の値の最大値は 1e9+7 であり、sqrt(1e9+7) 個の int 型配列を持つことができることに着目する。(実際には、(1e9+7)^(1/k) (k は小さい整数) 個の int 配列を持つことができれば十分だが、この問題では k = 2 とできる)
すると、平方分割の要領で各クエリの答えの区間を 1/sqrt(1e9+7) 倍にできる。これを 2 回繰り返すことで、答えを求めることができる。
各クエリに対して高々 2 回だけ数列を生成すれば良いので、時間計算量は O(NQ)、空間計算量はO((maxX)^1/2) となる。(下の実装では、各クエリに対して数列の生成は高々 1 回程度となっている)

ll n, x0, a, b;
vector<int> q;
#define M 31623
#define M2 (1000000007/M)
int sum[M+100], sum2[M2+100];

// Parallel binary search で解けると思ったが、log が付いたため TLE となった
/* TLE
ll f(vector<int> &c, ll lb, ll ub){
	if(c.empty()) return 0;
	if(ub-lb<=1){
		return ub*c.size();
	}
	ll md = (lb+ub+1)/2;
	ll cnt = 0;
	ll x = x0;
	rep(i, n){
		if(x<=md) cnt++;
		x = (x*a+b)%mod;
	}
	vector<int> a, b;
	int m = c.size();
	rep(i, m){
		if(cnt>=q[c[i]]) a.pb(c[i]);
		else b.pb(c[i]);
	}
	return f(a, lb, md)+f(b, md, ub);
}
*/

class LimitedMemorySeries1 {
	public:
	long long getSum(int n_, int x0_, int a_, int b_, vector <int> q_) {
		n=n_;x0=x0_;a=a_;b=b_;q=q_;
		mset(sum, 0);
		sort(all(q));
		vector<int> c(q.size());
		rep(i, q.size()) q[i]++;
		rep(i, q.size()) c[i] = i;
		ll x = x0;
		rep(i, n){
			sum[x/M2]++;
			x = (x*a+b)%mod;
		}
		rep(i, M+10) sum[i+1]+=sum[i];
		ll res = 0;
		for(int j = 0; j <= M+10; j++){
			if(q.empty()) break;
			if(q[0]>sum[j]) continue;
			mset(sum2, 0);
			ll x = x0;
			rep(i, n){
				ll t = x/M2;
				if(t<=j){
					if(t<j) sum2[0]++;
					else sum2[x%M2]++;
				}
				x = (x*a+b)%mod;
			}
			rep(i, M2+10) sum2[i+1]+=sum2[i];
			rep(i, M2+10){
				while(!q.empty()&&q[0]<=sum2[i]){
					res += j*M2+i;
					q.erase(q.begin());
				}
			}
		}
		return res;
		//return f(c, -1, mod-1);
	}
};

SRM 675 Div1 Easy TreeAndPathLength3

この回は個人的に Easy も Med も面白い問題だと思った。

s が小さいとき (497 以下のとき) は、パスグラフでも 500 頂点を超えないようにできる。
そうでないときは、1 頂点 u の周りに 101 個頂点をくっつけた木を考えて、その周りに 頂点を付け足していくとうまく構成することができる。
s が残り 100 以上であれば、u から距離 2 離れた頂点を追加する。このとき、毎回別の頂点に隣接するように追加しなければならないことに注意する。すると、長さ 3 のパスが 100 増えるので、s を 100 減らす。
s が残り 100 未満であれば、前のステップで追加した頂点の先に頂点を s 個パス状に追加する。 1 頂点追加するごとに長さ 3 のパスが 1 つ増える。

ワーストケースは、s = 9999 の場合で、300 頂点になる。

class TreeAndPathLength3 {
	public:
	vector <int> construct(int s) {
		vector<int> res;
		if(s<100){
			rep(i, s+2){
				res.pb(i);
				res.pb(i+1);
			}
			return res;
		}
		rep(i, 101){
			res.pb(101);
			res.pb(i);
		}
		int t = 102;
		while(s>=100){
			res.pb(t);
			res.pb(t-102);
			s -= 100;
			t++;
		}
		while(s){
			res.pb(t);
			res.pb(t-1);
			s--;
			t++;
		}
		return res;
	}
};

AGC 005 E Sugigma: The Showdown

問題: E - Sugigma: The Showdown

まず、しぐま君 (追いかけられる方のプレイヤー) の必勝条件について考える。
すぎむ君 (追いかける方のプレイヤー) の木において、距離が 3 以上離れた頂点を行き来できるような頂点に先に到達し、直後のターンに負けないことと同値となっている。
適当な根としたすぎむ君の木について考えると、距離が 3 以上離れた頂点であるかの判定が簡単にできる。(この判定方法を思いつくのは少しむずかしいかも)

必勝となる頂点を確定させたあとは、すぎむ君、しぐま君の順で、交互に BFS をしながらお互いの動ける範囲を計算すればよい。(すぎむ君、しぐま君の順で計算するのは本質では無いが、少しだけ見通しがよくなる)

#define N 200100
vector<int> g[N], g2[N];
int n, x, y, a[N], b[N], c[N], d[N];
int d2[N], w[N], used[N], p[N];

int dfs2(int u){
	for(auto v: g2[u]){
		if(d2[v]<0){
			d2[v] = d2[u]+1;
			dfs2(v);
			p[v] = u;
		}
	}
}

int main(){
	cin>>n>>x>>y; x--; y--;
	rep(i, n-1) cin>>a[i]>>b[i];
	rep(i, n-1) cin>>c[i]>>d[i];
	rep(i, n-1){
		a[i]--; b[i]--;
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	rep(i, n-1){
		c[i]--; d[i]--;
		g2[c[i]].pb(d[i]);
		g2[d[i]].pb(c[i]);
	}
	mset(d2, -1);
	d2[y] = 0;
	dfs2(y);
	p[y] = -1;
	rep(i, n-1){
		int t = d2[a[i]]-d2[b[i]];
		if(abs(t)>2){
			w[a[i]] = 1;
			w[b[i]] = 1;
			continue;
		}
		int a2 = a[i], b2 = b[i];
		if(t==0){
			a2 = p[a2];
			b2 = p[b2];
		}
		while(t>0){
			a2 = p[a2];
			t--;
		}
		while(t<0){
			b2 = p[b2];
			t++;
		}
		if(a2!=b2){
			w[a[i]] = 1;
			w[b[i]] = 1;
		}
	}
	queue<int> q, q2;
	q.push(x); q2.push(y);
	w[y] = -1;
	if(w[x]==1){
		cout<<-1<<endl;
		return 0;
	}
	w[x] = 2;
	int cnt = 1;
	for(int i = 2; ; i+=2){
		queue<int> q3, q4;
		while(!q2.empty()){
			int u = q2.front(); q2.pop();
			for(auto v: g2[u]){
				if(w[v]<0) continue;
				if(w[v]==2) cnt--;
				w[v] = -1;
				q4.push(v);
			}
		}
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(auto v: g[u]){
				if(w[v]<0||w[v]==2) continue;
				if(w[v]==1){
					cout<<-1<<endl;
					return 0;
				}
				w[v] = 2;
				cnt++;
				q3.push(v);
			}
		}
		if(cnt==0){
			cout<<i<<endl;
			break;
		}
		q.swap(q3);
		q2.swap(q4);
	}
	return 0;
}

SRM 670 Div1 Medium Treestrat

まず、木なので高々 N ステップでゲームが終了する。
A のトークンは複数あるが、すべて独立に計算できるので、それぞれ別に計算する。
A のトークンが 1 つの場合は、BFS を行うことで、解が計算できる。

#define N 55
int d[N][N];
class Treestrat {
	public:
	int roundcnt(vector <int> t, vector <int> A, vector <int> B) {
		int n = t.size()+1;
		int m = n-1;
		int res = N;
		for(auto x: A){
			mset(d, 0);
			for(auto y: B) d[0][y] |= 1;
			d[0][x] |= 2;
			int cnt = 0;
			while(true){
				memcpy(d[cnt+1], d[cnt], sizeof(d[0]));
				rep(i, m){
					int u = i+1, v = t[i];
					d[cnt+1][u] |= d[cnt][v];
					d[cnt+1][v] |= d[cnt][u];
				}
				bool ok = false;
				++cnt;
				rep(i, n) if(d[cnt][i]==2) ok = true;
				if(!ok) break;
			}
			chmin(res, cnt);
		}
		return res;
	}
};