読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 194/195/196

yukicoder open 2015 small後半
コンテスト中解けなかった3問になります.
6問目があと20分あれば解けたので悔しいです.
早解きの練習をしてもっと早く解けるようになりたいです.

- 194 フィボナッチ数列の理解(1)

  • 問題概要

初項F_1,,,,F_N
F_k=\sum_{i=1}^N F_{k-i},S_k=\sum_{i=1}^k F_{i}
で与えられる数列のF_K,S_Kを求めよという問題です。
ただし二種類のテストケースが存在しそれぞれ制約が異なる。
testcase01~10: 2\le N\le 10^4,N < K \le 10^6
testcase11~20: 2\le N\le 30,N < K \le 10^{12}

  • 解説

testcase01~10: 2\le N\le 10^4,N < K \le 10^6のとき、
Nが大きいのでコンパニオン行列やきたまさ法ぶっぱするとTLEします。
S_k=F_k +S_{k-1}
F_k=S_k-1 -S_{k-N-1}
というふうに表せ、小さい順に求めていけばO(K)で求められるのでACです。
数列Sを使ってFを求めるDPですね。

testcase11~20: 2\le N\le 30,N < K \le 10^{12}
Nが小さいのでF_Kはきたまさ法ぶっぱでよさそうです。Kがintの範囲を超えるので繰り返し二乗法を使う場合は注意が必要です。
S_Kについて考えます。
S_k=F_k +S_{k-1}
F_k=S_k-1 -S_{k-N-1}
この二つの式から、
S_k=2S_{k-1}-S_{k-N-1}というSだけの式が作れるのがわかると思います。
つまりSはN+1項間定数係数漸化式なのです。N+1であることに注意して、初項を求めてやれば同様にきたまさ法を適用することが可能です。
したがって計算量はN^2 \log K

テストケースに対してアプローチを変える問題は初めてでした。きたまさ法の解説的なものは別記事に用意しています。

#include<iostream>
#include<utility>
#include<vector>
using namespace std;


#define LL long long
#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define all(b) (b).begin(),(b).end()
LL A[1000001];
LL S[1000001];
LL N, K;

const LL mod =(LL) 1e9 + 7;

#define MAX_LOGN 60
template <class T>
struct Mr{
	vector<T> first;
	vector<T> C;
	vector<vector<T>> bin;
	T zero, one;
	int M;
	//n(1,,,2M)をn(1,,,M)に修正、O(M^2)
	void form(vector<T> &n){
		rev(i, M + 1, 2 * M + 1){
			reE(j, 1, M)n[i - j] = (n[i - j] + (C[M - j] * n[i]));
			n[i] = zero;
		}
	}
	//lとrを足し合わせる、O(M^2)
	void add(vector<T> &l, vector<T> &r, vector<T> &ans){
		reE(i, 1, 2 * M)ans[i] = zero;
		reE(i, 1, M)reE(j, 1, M)ans[i + j] = (ans[i + j] + (l[i] * r[j]));
		form(ans);
	}
	//初期化、O(M*MAX_LOGN)
	Mr(const vector<T>& f, const vector<T>& c, int m, T e1, T e0){
		M = m;
		first.reserve(M + 1); C.reserve(M);
		zero = e0, one = e1;
		first.push_back(zero);
		rT(i, M){ first.push_back(f[i]); C.push_back(c[i]); }
		bin.resize(MAX_LOGN);
		rT(i, MAX_LOGN)bin[i].resize(2 * M + 1);
		rE(i, 2 * M)bin[0][i] = zero; bin[0][1] = one;
		reT(i, 1, MAX_LOGN){
			add(bin[i - 1], bin[i - 1], bin[i]);
		}
	}
	//N項目の計算、戻り値がTの形であることに注意、O(M^2*logN)
	T calc(LL n){
		n--;
		vector<T> tmp, result = bin[0];
		for (int b = 0; n; b++, n >>= 1)
			if (1 & n){ tmp = result; add(tmp, bin[b], result); }
		T ans = zero;
		reE(i, 1, M)ans = ans + (result[i] * first[i]);
		return ans;
	}
};
//テンプレート、デフォルトコンストラクタのオーバーロードを忘れない
#define MOD 1000000007
struct X{
	LL val;
	X(LL  v){ val = v; }
	X(){ val = 0; }
	LL operator=(const X &another){ return val = another.val; }
	LL operator*(const X &another)const{ return (val*another.val) % MOD; }
	LL operator+(const X &another)const{ return (val + another.val) % MOD; }
};


pair<LL, LL> case1(){
	
	for (LL i= N + 1; i <= K; i++){
		A[i] = (mod + S[i - 1] - S[i - N - 1]) % mod;;
		S[i] = (A[i] + S[i - 1])%mod;
	}

	return make_pair(A[K],S[K]);
}

pair<LL, LL> case2(){
	vector<X> f((unsigned)N, 0), s((unsigned)N+1, 0), a((unsigned)N, 1), b((unsigned)N+1, 0);
	for (int i = 0; i < N; i++){
		f[i] = A[i+1];
		s[i+1] = S[i + 1];
	}
	b[(unsigned)N] = 2;
	b[0] = mod - 1;
	Mr<X> mr(f, a, (int)N, X(1), X(0));
	Mr<X> nr(s, b, (int)N + 1, X(1), X(0));

	return make_pair(mr.calc(K).val, nr.calc(K+1).val);

}

int main(void){
	cin >> N >> K;
	for (LL i = 1; i <= N; i++){
		cin >> A[i];
		S[i] = S[i - 1] + A[i];
		S[i] %= mod;
	}

	pair<LL, LL> res;
	if (K <= 1000000)res= case1();
	else res = case2();
	cout << res.first << " " << res.second << endl;
	return 0;
}

- 195 フィボナッチ数列の理解(2)

  • 問題概要

F_k=F_{k-1}+ F_{k-2}
であらわされる定数係数漸化式がある
F_1=A,F_2=Bとしたとき、
x,y,zが与えられたときF_a=x,=F_{b}=y, F_{b}=z
を満たす(a,b,c)が存在する辞書順最小の(A,B)を出力せよという問題です。

  • 解説

線形性がありそうだなとは思っていたが自力では解法までたどり着けませんでした。
A=s,B=0の数列をLとすると、
L={s,0,s,s,2s,3s...}
A=0,B=tの数列をRとすると、
R={0,t,t,2t,3t...}
という風に片方が0の数列には線形性があります。
ここで、A=s,B=tの数列をTとすると、
T={s,t,s+t,s+2t,2s+3t}というようにLとRを足した数列になります。
これを利用して解きます。
あらかじめ、L={1,0,1,1,2,3...},R={0,1,1,2,3...}を求めておきます。
i,jを固定して、T(i)=x,T(j)=yを満たすA,Bを求めます。T(i)=A*L(i)+B*R(i)です。
x=A*L(i)+B*R(i)
y=A*L(j)+B*R(j)
i,jは与えられているのでL(i),R(i),L(j),R(j),x,yは定数、A,Bが変数とみると連立一次方程式です。
正整数のペア(A,B)が見つかり、かつA*L(k)+B*R(k)=zとなるkが存在するならばそれは解の候補です。
したがって、すべてのi,jについて上の連立方程式を解き、正整数の方程式の解(A,B)が存在するならば、A*L(k)+B*R(k)=zを満たすkが存在するかを調べ、存在するならば(A,B)は解の候補です。
解の候補の中で辞書順最小のものを出力すればAC.
L,Rはともに要素数が50未満なので、すべてのi,jについて調べるのにO(50^2)さらにすべてのzについて調べるのにO(50)
したがってO(50^3)ぐらいで求められます。
x=y=zのときは(1,?)が解になるはずなので(1,k=(x-L(i))/R(i))となる最小の正整数kを求めてやればよい。
すべてのiを探索すればよいのでこちらはO(50)

連立方程式の計算calcで結構面倒なことしているので掃出し法とかするちゃんとしたライブラリ作ったほうがいいかもしれない。

#include<iostream>
#include<algorithm>
#define LL long long 
const LL MAXN = 1e9;
using namespace std;
#define mp(a,b) make_pair(a,b)
typedef pair<LL, LL> P;


inline P calc(LL l1, LL r1, LL l2, LL r2, LL c1, LL c2){
	LL y;
	//if (l1 != 2||l2!=5)return mp(-1,0);
	if (l1 == 0){
		if (r1 == 0 || c1%r1)return mp(-1, 0);
		y = c1 / r1;
	}
	else if (l2 == 0){
		if (r2 == 0 || c2%r2)return mp(-1, 0);
		y = c2 / r2;
		swap(c2, c1); swap(l1, l2),swap(r2,r1);
	}
	else{
		r1 *= l2, c1 *= l2;
		l2 *= l1, r2 *= l1, c2 *= l1;
		r1 -= r2, c1 -= c2;
		if (r1 < 0)r1 *= -1, c1 *= -1;
		if (c1 <= 0 || r1 <= 0 || c1%r1)return mp(-1, 0);
		y = c1 / r1;
	}
	c2 -= r2*y;
	
//	cout << y << " " << c2 << " " << l2 << endl;
	if (c2 <= 0 ||l2<=0 || c2%l2)return mp(-1, 0);
	return mp(c2 / l2, y);
}


int main(){
	LL x, y, z;
	LL left[50] = { 1, 0 };
	LL right[50] = { 0, 1 };
	LL test[50] = { 1, 1 };
	LL sz = 0;
	cin >> x >> y >> z;

	for (int i = 2; left[i - 1] <= MAXN; i++){
		left[i] = left[i - 1] + left[i - 2];
		right[i] = right[i - 1] + right[i - 2];
		test[i] = test[i - 1] + test[i - 2];
//		cout << left[i] + right[i] << " " << test[i] << endl;
		sz++;
	}
	P res = mp(-1ll, 0ll);

	if (x == y&&y == z){
		res = mp(1, x);
		for (int i = 2; i < sz; i++){
			if (x - left[i]>0 && (x - left[i]) % right[i] == 0)
				res = min(res, mp(1ll, (x - left[i]) / right[i]));
		//	cout << right[i] << endl;
		}
	}
	else{
		if (x == y)
			swap(y, z);
		for (int i = 0; i < sz; i++)
			for (int j = 0; j < sz;j++)
				if (i != j){
					auto p = calc(left[i], right[i], left[j], right[j], x, y);
					if (p.first < 0)continue;
					for (int k = 0; k < sz; k++)
						if (z == p.first*left[k] + p.second * right[k])
							if (res.first < 0 || p < res)
								res = p;
				}


	}
	if (res.first>0)
	cout << res.first<<" "<<res.second << endl;
	else cout << -1<<endl;
	return 0;
}

- 196 典型DP (1)

  • 問題概要

頂点0が根となる根付木が与えられる.
頂点を黒と白に塗り分けるときその組み合わせは何通りあるか求める問題です。
ただし親が黒なら子も黒でなければならないという制約が存在。

  • 解説

親から順に組み合わせをdpで求めていきました。子から求めていくdpはO(N^3)しか思いつきませんでした。
全ノード中黒がw個となる組み合わせをpt(w)とし、頂点i以上の階層で一つ以上黒色のノードが存在しかつ全ノード中黒がw個となっている組み合わせをdp(i,w)とします。
ややこしいですがこれが大事です。
DPをするにあたって、頂点iを含む根付木のサイズをN(i)としたとき、
iを塗るかどうかなのでpt(w)=pt(w-N(i))+pt(w)で求められそうです。
しかしiよりも階層が上のノードが黒で塗りつぶされていた場合、既にiは黒色になっているのでその場合を考慮しなければなりません。
したがって、追加分add(w,i)=pt(w-N(i))-dp(par(i),w-N(i))として、
pt(w)=add(w,i)+pt(w)
dp(w,i)=add(dp(w,i)+dp(w,par(i))
で二つの配列を計算してやればうまくいきます。
計算量は全ての頂点でO(N)のdpをするのでO(N^2)です。
ソースコード

include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;

#define LL long long
const LL MOD = 1000000007;
int nodesize[2001];
vector<list<int>> child(2001);
vector<list<int>> adj(2001);

LL pt[2001] = { 1 };
LL pc[2001][2001];
LL par[2001];

int K;
int dfs(int v){
	for (int &u : adj[v])if (par[u] == -1){
		child[v].push_back(u);
		par[u] = v;
	}
	for (int &u : child[v])nodesize[v]+=dfs(u);
	return (++nodesize[v]);
}
void dfs2(int v){
	for (int i = K; i >= nodesize[v]; i--){
		pt[i] = (MOD+pt[i] + pt[i - nodesize[v]] - pc[par[v]][i - nodesize[v]]) % MOD;
		pc[v][i] = (MOD+pc[par[v]][i] + pt[i - nodesize[v]] - pc[par[v]][i - nodesize[v]])%MOD;
	}
	for (int &u : child[v])dfs2(u);
	return;
}

int main(void){
	int N;
	int a, b;
	cin >> N>>K;
	for (int i = 1; i < N; i++){
		par[i] = -1;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(0);
	dfs2(0);
	cout << pt[K] << endl;

	return(0);
}