Hatena::Grouptopcoder

zerokugi's contest memo

2015-03-21CodeChef March Challenge 2015

苦労したので備忘録として書いておく 読む価値はあんまり無いかもしれない

Count Substrings

永続遅延Segtree(区間加算、区間和)で殴ると簡単に書ける

各iについて左端毎に「右端がi以下である有向な区間の数」をセットした Segtreeをn個作ると seg[r].query(l, r) が答えになる

(ソース見たほうが分かりやすい)

ちなみにクエリ先読みすれば永続化はいらなくなる

http://www.codechef.com/viewsolution/6453408


int T, n, k, q;
char s[100005];
int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	scanf("%d", &T);
	while(T--){
		scanf("%d%d%d %s", &n, &k, &q, s);
		vi c(2);
		SegTreeDynamicLazy<handler> seg(n);
		vector<SegTreeDynamicLazy<handler>::Node*> roots;
		roots.pb(seg.root);
		int l = 0;
		REP(i, n){
			c[s[i]-'0'] ++;
			while(c[0] > k || c[1] > k) c[s[l++]-'0'] --;
			roots.pb(seg.update(l, i+1, 1, roots[i], 1));
		}
		REP(i, q){
			int l, r;
			scanf("%d%d", &l, &r); l--;
			printf("%lld\n", seg.query(l, r, roots[r], 1));
		}
		SegTreeDynamicLazy<handler>::Node::allClear();
	}
	return 0;
}

Sereja and Random Array

線形合同法の方はよく見るとseedの下位16bitしか答えに影響しないので全部調べる

クエリ全部Trieに突っ込んで一気に判定するとよい

i文字目までたまたま一致する確率は 2^(-i) なので ハズレseed1個あたりの期待計算量は O(1) になる

http://www.codechef.com/viewsolution/6450115

Chef and Problems

Aiに出てくる回数が多い数字と少ない数字に分けて処理する平方分割

多い数字についてはクエリ毎に全部の数字について区間内の最左最右を調べる

少ない数字についてはクエリ先読み+数列を左からなめながら Segtree を構築していく

http://www.codechef.com/viewsolution/6415128

Counting on a Tree

とりあえずこの問題では辺の重みを素因数分解した時に指数が2以上のものは1にしてしまっても問題ない

と、すると素因数の数は最大7個 (2*3*5*7*11*13*17=510510) になるので約数の数は最大2^7個

初期値(部分点)

各辺を重みの全ての約数の辺に拡大してやり,同じ値を持つ辺からなるグラフを作る

(辺の総数は最大 2^7*100000 個)

この時各重み毎にグラフ上の到達可能な点対数を求めて(dfsでO(E))素因数の数の偶奇で包除すると答えの初期値が求まる

クエリによる値の更新

ある辺 e=(u, v) を a → b に変更する場合を考える

eを境にして両側へ伸びる部分木UとVに対して,dfsでuからの(vからの)全パスのgcdを求める

U×Vのペアについてgcdを取った値が

  • a, bともに共通の素因数を持つ → クエリ前後ともにパスが存在する
  • a のみと共通の素因数を持つ → クエリによってパスはなくなる
  • b のみと共通の素因数を持つ → クエリによってパスが新しく増える
  • a, bともに共通の素因数を持たない → パスは存在しないまま

なので,2個目と3個目にあたる組み合わせ数をそれぞれ求めて足して引けばクエリによる差分が求まる

(ただし Q*N 回 gcd 取るとTLEするので素因数のリストで値を管理してビット演算で gcd を取ったりして頑張って速くしないと通らなかった)

http://www.codechef.com/viewsolution/6439242

Random Number Generator

10点はkitamasa法

満点は多項式の除算とFFTを使って解くらしい

(ここからは非想定解であまり頭のよくない方法だけど,一応無理やり満点取れたので記しておく)

kitamasa法を FFT を使って速くする(※まちがい)ことを考えた結果

  • 序盤の a(2m)をa(0)からa(2n-2) で表すフェイズは畳み込みするだけ
  • 後半のanからa(2n-2)をa0からa(n-1)に押し戻すフェイズは畳み込み適用不可能

ここで後半部分を

  • a(n+k)からa(n+2*k)をa(k)からa(n+k)に押し戻す

という処理をダブリングっぽく適用していくと log n 回の畳み込みで押し戻せる O(n^2) → O(n logn logn)

ただし,これを行うためにはa(k)をa(0)~a(n)で表したものが必要 → 前処理に O(n^2) 必要…

k = sqrt(n) として平方分割っぽく押し戻していくと O(n^1.5 logn) になるけど前処理が O(n^1.5) になる

あとは定数倍がんばったら通った(kのパラメータ職人とか、2とか4進める時はダブリングせずに1個ずつ進めるとか、 FFT の使いまわせる計算を先にやっとくとか、限界までMODは取らないとか…)

多分最終的にオーダーは O(k^1.5 logk logn) になってるはず…

http://www.codechef.com/viewsolution/6464373