kojingharangの日記

SRM 656 Div1 250 RandomPancakeStack

01:18 |

• パンケーキが N 個あり、パンケーキ i の直径は i+1 でおいしさは d[i] である。残ってるパンケーキから等確率で 1 個選びある皿に乗せていく。
• 皿に乗ってる一番上のパンケーキの直径より大きなのが選ばれた時点で終了。取るやつがなくなっても終了。おいしさの期待値を求めよ。
• 1≦N≦250, 1≦d[i]≦1000

• DPが思いつかないので...
• 1/N! の確率で [1, N] の permutation p が選ばれることになる。これを p[i-1]＞p[i] である最大の i までについて Σd をとったものがその場合のおいしさ。
• 縦に N! 通り、横に permutation を書いていってどうにか規則的に足せないか考えていると...
• m+1 番目が X でありそれがおいしさにカウントされるような permutation の数は O(1) で求められることに気づく。
• ? ? ? X ? ?
• 前半は X より大きな N-x 個の数から m 個選び、後半は残りの N-m-1 個の順列なので Combination(N-x, m) * (N-m-1)!
• というわけで、全 m, X についてその場合の数 * d[X] を足して最後に N! で割ったものが答え。

• Accepted

• dp でやる場合は dp[Topの直径][今まで何個使ったか], dp[N][0]=1, 配った時パンケーキごとに使った数を覚えていくとよい模様。

#define D long double

class RandomPancakeStack {
	public:
	D fac(int x) {
		D v = 1;
		REP(i, x) v*=i+1;
		return v;
	}
	D f(int x, int m, int N) {
		int k = N-m-1;
		if(N-x<m) return 0;
		return fac(N-x)*fac(k)/(fac(m)*fac(N-x-m));
	}
	double expectedDeliciousness(vector <int> d) {
		int N = d.size();
		D ans = 0;
		REP(v, N) {
			D lans = 0;
			REP(di, N) {
				D z = f(v+1, di, N);
				lans += z;
			}
			lans *= d[v];
			ans += lans;
		}
		D div = fac(N);
		return ans / div;
	}
};

ツイートする

Google code jam 2015 Round1A B. Haircut

19:29 |

• B個の1人用床屋があり床屋 i は 1 人切るのに M[i] 分(整数)かかる。行列ができており、同時に複数の店が空いたら i が小さい店にすぐ入る。N人目の人は何番の床屋で切ることになるか？
• (Large) 1≦テストケースの数≦100, 1≦N≦10^9, 1≦B≦1000, 0≦M[i]≦100000

• small はとりあえず LCM(M) を求めて N % その時間までに切り終わった人数までシミュレート。
• ぱっと思いつかなかったので、C small 解いて戻ってきたところ、時刻を決めると切り終わった人数が O(B) で分かることに気づく
• そんな感じで二分探索して Bl.cpp を書く → Bs.cpp で解いた B-small の結果と一致 → large download, 実行
• あ
• Bl.cpp と思っていたビルド＆実行ソースは Bs.cpp だった....。Bl.cpp はただの 1 回も実行されてなくてバグりまくり → 8分デバッグ → 死

• (あとで)
• N 人目が始まる最小の時刻は簡単には求められないんじゃないかと思って累計 N-1 人終わったあたりをぐにぐにしてたが、
• t が終わった時点で始まってる人数は Σ t/M[i]+1 と終了人数 + B で簡単に求まるのだった。終わったらすぐ始まるのだから、そりゃそうだ。
• N 人目が始まった時刻には実際のところ複数の人が始まってる可能性があるので、B を後ろからみてって割り切れるとこをカウントして N になったとこが答え。

• 終わった人数基準でやるなら、N 人目が始まる時刻の下限であるのべ N-B 人が終わった時刻からシミュレートすればよい。(10^8 なのでOK)

• コマンドライン安全標語: 一、自分を信用するべからず

• Accepted in practice

int main() {
	int test_cases;
	cin>>test_cases;
	ll B,Nth;
	string s;
	REP(ttt, test_cases) {
		cin>>B>>Nth;
		VI w(B);
		REP(i, B) cin>>w[i];
		ll lo=-1, hi=1LL<<60; // hi ... began at least N
		while(lo+1<hi) {
			ll mid = (lo+hi)/2;
			ll began = 0;
			REP(i, B) began += mid / w[i] + 1;
			if(began<Nth) lo=mid; else hi=mid;
		}
		ll t = hi;
		ll began = 0;
		REP(i, B) began += t / w[i] + 1;
		ll beganP = 0;
		REP(i, B) beganP += (t-1) / w[i] + 1;
		assert(beganP<Nth);
		assert(Nth<=began);
		int ans = 0;
		for(int i=B-1;i>=0;i--) {
			if(t%w[i]==0) {
				if(began--==Nth) {ans = i+1; break;}
			}
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

ツイートする

2015 TCO Round1A 1000 Revmatching

10:38 |

• N頂点-N頂点 の重み付き２部グラフが与えられる。完全マッチングにならないように辺を減らしたい。消す辺の重みの合計の最小値を求めよ。
• 1≦N≦20, 0≦重み≦9

• 左右のどれかの頂点を完全に孤立させれば少なくとも完全マッチングにはならんだろう
• 十分か分からないけど他に思いつかないので書いてみる→最後のサンプルでだめ
• ググるもいまいちそれっぽいのが出ず。
• フロー？
• 片側の頂点数 20 だから部分集合総当り？

• (あとで)
• Hall の定理を使うらしい。
• 任意の左の頂点部分集合 L に対応する右の頂点集合 R が |L|≦|R| ←→完全マッチングが存在する
• ある L について |L|＞|R| になればいいので、
• 部分集合それぞれについて、|L|＞|R|になるように R につながる辺を消した時の最小コストを求めてその最小値を返せばよい。
• ほー、覚えておこう。

• Accepted in practice

class Revmatching {
public: 
	int smallest( vector <string> A ) { 
		ll N = A.size(); 
		ll ans = 1000000; 

		RANGE(b, 1, 1<<N) {
			VI rmCosts(N); 
			// li ... left index  ri ... right index
			REP(li, N) if(b>>li&1) REP(ri, N) rmCosts[ri] += A[li][ri]-'0'; 
			sort(ALL(rmCosts));
			ll nL = POPCOUNT(b); 
			ll rmCost = 0;
			// rm R nodes as little as possible so that |L|>|R|, which means |L|-1 = |R|
			REP(i, N - (nL-1)) rmCost += rmCosts[i];
			ans = min(ans, rmCost); 
		} 
		return ans; 
	}
}; 

ツイートする

2015 TCO Round1A 500 Autogame

03:34 |

• N個の場所がありそれぞれにどこかの場所を指す矢印の根元がある。各場所に最大1個のトークンを置き一斉に矢印の通りに動かすのを K 回やる。
• 同じ場所にトークンが２つになってしまったら負け。負けないようなトークンの置き方は何通りあるか。mod 10^9+7で。
• 1≦N≦50, 1≦K≦10^9

• 全場所にトークンを置いたとして、K回動かしてトークンの位置を追跡する。
• 枝分かれしないので、１回合流したら合流しっぱなし。
• なので、最終的に場所が違う→独立に選べる
• 各場所について、最終的に集まったトークンの中から１個選ぶor0個選ぶ、ということで場所ごとに個数+1を掛ければよさげ。
• トークンIDの集合になるから vector<int> かとおもったけど単に個数でいいのだ。
• 最初 50 回くらいやれば収束するだろうからと 1000 回まわしたが K が小さいときもあるんだったということで min(K, 1000) に変更。あぶない。

• Accepted

class Autogame {
	public:
	int wayscnt(vector <int> a, int K) {
		int N=a.size();
		VI w(N);
		REP(i, N) w[i]=1;
		REP(loop, min(K, 1000)) {
			VI nw(N);
			REP(i, N) nw[a[i]-1]+=w[i];
			w = nw;
		}
//		cout<<w<<endl;
		ll ans=1;
		REP(i, N) {
			ans*=w[i]+1;
			ans %= 1000000007LL;
		}
		return ans;
	}
};

ツイートする

SRM 650 Div1 250 TaroFillingAStringDiv1

20:01 |

• A,Bからなる長さ N の文字列を、隣接する２文字が同じような組の数が最小となるように作りたい。
• ただし、Pos[i] 番目の文字は Value[i] (0≦i＜M)でないといけない。何通り作れるか? mod 10^9+7で。
• 1≦N≦10^9, 0≦M≦50

• A_A なら ABA にするしかない。
• A_B なら AAB か ABB のどちらか。
• A__B なら ABAB しかない。
• A__A なら ABAA か AABA かな (あとで: 正しくは ABBA も含めた3通り)
• 端は常に１通り (__A は ABA)

• というわけで、全 X___(_がkコ)___Y について、X==Y かつ kが奇数なら 1 通り、そうでないときは 2 通り、X!=Yだったりkが偶数だったりしたら反転、でいいかな
• sampleより大幅に少ない場合がある
• A__A の場合は3通りか。
• 隣り合う文字が同じになる開始位置が k+1 コあるということか。
• 各 ___ について、(X==Y) ^ kが奇数 ? k+1 : 1
• →提出

• おお N は結局使わないのか
• Accepted

• sampleに救われたが本来そうであってはいけない ...けど結果オーライ

class TaroFillingAStringDiv1 {
	public:
	int getNumber(int N, vector <int> P, string S) {
		int M=P.size();
		vector<PII> w(P.size());
		REP(i, M) w[i] = MP(P[i], (ll)S[i]);
		sort(ALL(w));
		modll ans = 1;
		// # of cands in start and end interval is 1
		RANGE(i, 1, M) {
			ll gap = w[i].first - w[i-1].first - 1;
			int odd = gap & 1;
			int same = w[i].second==w[i-1].second;
			ll v = same ^ odd ? gap+1 : 1;
			if(gap) ans *= v;
		}
		return ans;
	}
};

ツイートする