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

誤読

文字通りくそコード

数列の好きな範囲で大きいほうからk個のsumをO(1)で求める

追記;ウェーブレットはO(1)だぞ、O(1)だからな 決して重めのO(logn)とかではない
追記2;これはメモリがすごい


まあWaveletMatrixをしましょう。(完)




解説をします。

僕が説明下手なのはいつものことなので我慢して読むなり読まないなりしてください。

まずWaveletを理解していない人は↓を読んで君もWaveletマスターになろう

これ見てからウェーブレット木の世界 | Preferred Research

これ読んでwww.scribd.com





ARC074Dについて、某さんが上からk個のsumライブラリほしいみたいなことを言っていたので、書いてみたら書けた。

もやし先輩 on Twitter: "上からn個の和、WaveletでめっちゃくまくやればO(1)でできそう"


上からk番目の値を求める操作を知ってるとイメージしやすそうなので理解して

基本的にはk番目の値を求める操作と同じく潜っていきます(この場合は再帰でやっていきます)。その過程で、bit桁ごとに2のべき乗ずつ合算していくことで、最終的に全体のsumを出すイメッジです。

図解

f:id:akihiro1001:20170523205307p:plain

↑な感じに行列があったとする。(オレンジ枠は緑枠の数字のnbit目、紫線は0,1のボーダー)

・n桁目のみでのsum

popc(立ってるビットの数) * 2^n であり、さらにこれに下位bitでのsumを加算する。(pow使うな)

・下位bitでのsumの出し方

本題の操作をmore_Kthsum(start, end, kth, n桁目)(kth >= 1)

ランクはrank(start,end, 0 or 1)で閉区間 (0か1のbit数)

n桁目の段階で、popc > kth の場合は、more_Kthsum(ボーダー + rank(0,s,1), ボーダー + rank(0,e,1), kth, n-1)であり、これはk番目の値を求めるときの操作とおんなじでまあ普通

そうでない場合がミソで、ナイーブな方法だと、

    more_Kthsum(rank(0,s,0), rank(0,e,0), kth - cou, n-1) + more_Kthsum(ボーダー + rank(0,s,1), ボーダー + rank(0,e,1), cou, n-1)

だが、ここで分岐してしまうのは計算量大爆発なのでなんとかして一本化したい。

注目すべきは→のほうで、範囲内の立ってるビット全てのsumを求めている。

ここで各桁において、立ってるbitの場所だけ 現在の桁以上の桁を削った後 の累積和をあらかじめ取っておくと、→が[end,start)の和に置き換わって計算量爆下げハッピーO(1)である。(↓図)

※現在の桁については n桁目のみでのsum で加算されてしまっているので、n桁目のみでのsumを出す時点で引くなりなんなり上手い感じに処理して

f:id:akihiro1001:20170523213754p:plain




例えば、

[2,7)で大きいほうから4個のsumを求めたいとする

・2bit目 popc = 3 kth = 4 popc <= kthなので、popc*2^2 + [2,7)の和 + more_Kthsum(0, 2, 1, 1)である。

・1bit目 popc = 2 kth = 1 popc > kthなので、popc*2^1 + moreKthsum(4, 6, 1, 0)

・0bit目 popc = 1 終わりなのでpopcを返す。

みたいな感じになります。

僕が説明下手なのはいつものことなので我慢して読んでください。

これでARC074Dを通したので張る(説明と若干違ったり、bitvectorがゴミ実装だったりするけど我慢して)
Submission #1304562 - AtCoder Regular Contest 074 | AtCoder



備考:

良いこのみんなはWaveletMatrixの計算量O(1)を真に受けるな。これは競プロやぞ

これを利用したら小さいほうからk個もまあできます。(普通の累積和-大きいほうから(end-start)-k個 てきな)

(完)

Union-Find with deletions

謎のデータ構造を見つけてしまった。実装したくなかったが、してしまった。後悔しかしていない。

UnionFindといえば競プロerであればほとんどの人が知ってると思われるが、あれはUniteとFindはあってもある要素をフリーにするという操作ができない。

UF木の葉以外を削除しようとすると計算量が増えてしまうのは想像がつくと思う。

そこでUnion-Find with Deletionsというのがあって、これを使うとUniteをO(A(n)),FindをO(A(n)),DeleteをO(1)でできるようになっておいしい。
(追記)論文でUniteがO(1)なのは集合をしていしてUniteする実装だからで、要素を指定してそれらの属するグループを併合するっていうのはFindを挟む必要があるのでO(A(n))になっているだけです。


主なアイデア

1.要素の部分と木構造の部分を切り離して木のノードが要素を持つという形にすると、削除したいノードの持つ要素とその木の中での葉の要素をswapしてから葉を消せばよい。

2.入りだけのオイラーツアーを持つことで葉のノードがわかる。

3.経路圧縮でいつものやつじゃなくてTarjan and Jan van Leeuwenが考えた経路圧縮を使いましょう。(ノードを親の親にくっつける)

説明能力が皆無なのでこの論文とこのスライドを合わせて読むと実装できます(大嘘)


この論文の通りにだと実装できなかったんですけど、アレンジを加えて頑張りましょう💢💢💢💢💢💢💢💢

↓ぼくのじっそう(ゴミ)

[C++] class UFNode; class LNode { public: UFNode *Myval; LNode *Prev, *Next; L - Pastebin.com


普通に汎用性高そう(小並感)なので今後の競プロ界のトレンド間違いなしだよ

せっかく無限に時間を溶かして書いたのに使う問題とか一切見当たらないため非常にアレなので使えそうなのがあったらほんと教えてください。

HOJにverify問投稿しようかな…

DSU on tree (CF600 E CF570 D)

GuniとかSackともいうっぽい、汎用性が高そうなので実装した。あと問題を2つ解いた



木があって各頂点にプロパティを持っている(例えば、ノードに色がついてるなど)時に、あるプロパティを持つ頂点の数を調べなさいとか、この部分木には何種類のプロパティがあるとか、そういったクエリを先読みして全部でO(n log n)でこたえられるテク。(部分木ごとに答えられる(大事))

ただ、これを使う問題は普通のマージテクだけでとけることもおおいっぽい


例題として、頂点に色がついた木で各頂点の部分木に何種類の色があるか出力する問題を考える。頂点数は10^5とか10^6とかくらい

愚直に各頂点からそれぞれdfsするとO(V^2)かかるし、ダメ

vector<int> cnt(n),ans(n);
int cou = 0;
void add(int cur, int p, int x){
//cnt[cur]が0->1になったときansが1増える、またその逆
    cou -= (bool)cnt[ col[cur] ];
    cnt[ col[cur] ] += x;
    cou += (bool)cnt[ col[cur] ];

    for(auto itr: g[cur])
        if(itr != p)
            add(itr, cur, x)
}
void dfs(int cur, int p){
    add(cur, p, 1);
////この時点でcurを根とする部分木での答えが出てる/////
    ans[cur] = cou;
//////////////////////////////////////////////////////
    add(cur, p, -1);
    for(auto itr : g[v])
        if(itr != p)
            dfs(u, v);
}

これをこうするとO(nlogn)↓

vector<int> cnt(n), sz(n),ans(n);/////szには部分木のサイズが入っているものとする
int cou = 0;
vector<bool> isbig(n);

void add(int cur, int p, int x){
//cnt[cur]が0->1になったときansが1増える、またその逆
    cou -= (bool)cnt[ col[cur] ];
    cnt[ col[cur] ] += x;
    cou += (bool)cnt[ col[cur] ];
///////////////////////////////////////////////////

    for(auto itr : g[cur])
        if(itr != p && !isbig[itr])
            add(itr, cur, x)
}
void dfs(int cur, int p, bool keep){
    pii bigc = {};
    for (auto itr : g[cur])
        if (itr != p)
            bigc = max(bigc, { sz[itr], itr });
    for (auto itr : g[cur])
	if (itr != p && itr != bigc.second)
	    dfs(itr, cur, false);
    if (bigc.first)
	dfs(bigc.second, cur, true), isbig[bigc.second] = 1;

    add(cur, p, 1);
////この時点でcurを根とする部分木での答えが出てる/////
    ans[cur] = cou;
//////////////////////////////////////////////////////
    if(bigc.first) isbig[bigc.second] = 0;
    if (!keep) 
	add(cur, p, -1);//結果をクリアする
}

これは何をしているかというと、

①子で最大の部分木探す
③最大じゃないやつ->最大のやつって順番でdfs
④最大のやつだけは親の頂点に帰るときに結果を持って帰る(一番大事)
・addでは、最大フラグが立ってるやつ以外に潜る(最大フラグが立っている場合、最大のやつdfsの結果が残っているのでやる必要がない)(最重要)

要は、子で最大の部分木の計算結果を親に持ち帰ることで、その分の計算を省くことをしてる

なぜこれでO(nlogn)が達成できるかというと、マージテクと同じ原理です(僕はそもそもマージテクの原理を雰囲気で理解してしまってるので、雰囲気で理解して(まあ最大を廃部いてるんだから計算量も減るでしょ!w))

備考
・部分木ごとに結果が出てるっていうのを強く意識するとよい
・基本的にコメントで囲ってるところを変えて問題を解く
・クエリを処理するとなると、ansに代入してるところでループを回したくなることがよくあるが、できるだけaddのところで随時処理してあげて、ループをなくそう(計算量大爆発、地球滅亡)
デバッグはわりとしやすい(4時間)



入門:
Problem - E - Codeforces
頂点に数字がついてて、部分木で最頻の数字をDominating Colorとか言うんだけど、その合計を求めてという話

随時(大事)Maxを更新してあげて、随時(大事)最頻値の合計を数えてあげる(随時じゃないと、ansに代入するところでMaxを求めるループを回さないといけないのでダメ)
地味にintだとオーバーフローするのが最大のイライラポイント
Submission #25946251 - Codeforces

実装違うけどちょっと早いver↓
Submission #25888745 - Codeforces


Problem - D - Codeforces
頂点に文字がついてて、部分木と全体での深さが指定される。部分木内の指定された高さの頂点についてる文字を並べ替えて回文が作れますか?という話
・回文を作るには奇数個の文字が1つ以下ならよい。
・深さごとにカウントを持つといける
・クエリを頂点ごとに持つのもイケメンポイント

Submission #25922457 - Codeforces


上の二つを解いたら感覚がつかめた。
両方とも想定解ではないっぽい。(上はただのマージテク、下はオイラーツアーでほいみたいなことをするっぽい)


このエントリにすごいお世話になった、感謝して(いろんな実装が乗ってる)(問題も載ってるのでとくっきゃない)
http://codeforces.com/blog/entry/44351


備考
・CFのブログって変なのいっぱいあるよね
・Rngedbaseループの変数名をitrにしてしまう癖があるんだけど、なんか違うっぽい

2-SAT (ARC069-F)

ARC069-Fがすごく解きたかった

2-SATは知ってた(以前minisatとか触った関連)ので書くのにはそんなに困らなかった。

解の構築は普通にできそうだけど、どこにも書いてないのが怖い(今度書いてみるよ)

さらっと探してみても使う問題を見ないし、実はだるかったりするんかな

・ARC069-F Flag

にぶたんはそれはそうで、判定部に2-SATを使う。

普通に2-SATを組むとすると、

候補2つのうちどちらか1つだけを使う ( ( ¬ A ) ∨ ( ¬ B )) ∧ ( A ∨ B ) に加えて、

各旗候補地についてmid以内にある旗と共存できないっていうのを

¬ ( A ∧ B ) → ( ¬ A ) ∨ ( ¬ B )と書き換えられることを使って表すことになる。

しかし、これだとImplicationグラフでの辺の数がO(V^2)とかになってやばいので減らす努力をしなければならない。


各旗候補地について、共存できないとして論理式につっこむのは連続してる旗たちなので

区間をセグ木っぽく表してあげて、 旗と共存できない ではなく 区間と共存できない として論理式を作ってあげるとO(VlogV)の辺で抑えられる。


また、親の区間が偽なら子の区間はかならず偽(その逆はない)なので ( ( ¬子 ) ∨ 親 ) を加える

f:id:akihiro1001:20170327122002j:plain:w500

僕のソース
Submission #1180258 - AtCoder Regular Contest 069 | AtCoder

bool TWO_SAT(int n, vector<pii> clause, vector<int> &ans) {
	DGraph g(n * 2);
	for (auto itr : clause) {
		g.con(itr.first + n, itr.second);
		g.con(itr.first, itr.second + n);
	}
	vector<int> scc;
	SCC(g, scc);

	REP(i, n) {
		if (scc[i] == scc[i + n]) {
			return 0;
		}
	}

	return 1;
}

  
・備考

TWO_SATってめちゃくちゃダサくないか

必要十分な論理式を考えるのがほんと難しい

論理式を考えるのがすごく楽しい

Tarjan's SCC

lowlinkを書いたばかりだったので、lowlinkを使ってSCCが書けると聞いて飛びついた。(が、完全に罠だった)

kosarajuは書いたことあるけどtarjanはないって人多そう(実際のとこ定数倍とかで早いのはどっち)

日本語の資料が微塵もなくて辛かった(有志は英wiki全部移植して)

①強連結成分は、dfs木を作ったときに必ず部分木になる(強連結成分はどの点からでもすべての点に行けるのでそれはそう)

②lowlinkとorderが等しい頂点が強連結成分の部分木の根(もしlowlinkのほうが小さかったら、それよか上まで自由に行けるので)

ので、dfsの行きがけでスタックに頂点を積んでいき、戻るときにlowlinkとorderが等しい頂点が見つかったら現在いる頂点が出てくるまでスタックから積んできた頂点を取り出す。そいつらがひとまとまりの強連結成分。

f:id:akihiro1001:20170327113005j:plain:w300

・罠

一般的なlowlinkは無向グラフでやるもので、有向グラフでlowlinkを無向と同様にやるとdfsするときの順番で結果が変わってしまうので少し違う。無向の時は後退辺だけだが、有向の場合は再帰のスタックに積まれてる頂点への辺も含めて考える。(ほんとにどこにも書いてなくて有向リンク界隈の廃れを感じる(そんなものはない))

あと、これを使って2-SATを書いたよ

void SCC(DGraph& g, vector<int>& scc) {
	vector<int>  orb(g.vn, -1);
	scc.resize(g.vn, -1);
	int cc = 0,k = 0;

	vector<bool> used(g.vn);
	stack<int> st;
	function<int(int)> dfs = [&](int cur) {
		int low = orb[cur] = ++k;
		st.push(cur);
		used[cur] = 1;
		for (auto itr : g.g[cur]) {
			if (orb[itr.first] == -1)
				low = min(low, dfs(itr.first));
			else if (used[itr.first])
				low = min(low, orb[itr.first]);
		}
		if (low == orb[cur]) {
			while (1) {
				int cp = st.top(); st.pop();
				used[cp] = 0;
				scc[cp] = cc;
				if (cp == cur)
					break;
			}
			cc++;
		}
		return low;
	};
	REP(i, g.vn)
		if (orb[i] < 0)
			dfs(i);
}

Lowlinkと橋全列挙と関節点全列挙

HOJのこれ
Hamako Online Judge
を解こうとして、関節点かぁ~ってなったのでLowlinkと関節点とついでに橋を書いた
灘のパソコン部の部誌は有用

平面座標を1次元に直すとき*wってやるのほんとやめような
実際期末試験 on Twitter: "は? https://t.co/BD6vz8wDqv"

グラフ系が割と充実してきて良い

Lowlink:

void Lowlink(BiDGraph& g,vector<int>& lowlink, BiDGraph& dfsg, vector<int>& orb, int st = 0) {
	orb.resize(g.vn, INT_MAX);
	lowlink.resize(g.vn, INT_MAX);
	int k = 0;
	function<void(int,int)> dfs = [&](int cur, int f) {
		int nex = 0;
		orb[cur] = k++;
		lowlink[cur] = orb[cur];
		for (auto itr : g.g[cur]) {
			if (f == itr.first) continue;
			if (orb[itr.first] == INT_MAX) {
				dfs(itr.first,cur);
				lowlink[cur] = min(lowlink[cur], lowlink[itr.first]);
				dfsg.con(cur,itr.first);
			}
			else {
				lowlink[cur] = min(lowlink[cur], orb[itr.first]);
			}
		}
	};
	dfs(st,-1);
	return;
}

関節点:

void Joint(BiDGraph& g, vector<int>& joints, int st = 0) {
	vector<int> lowlink, orb; 
	BiDGraph dfsg(g.vn);
	Lowlink(g, lowlink, dfsg, orb, st);

	REP(i,dfsg.vn) {
		if (st == i) continue;
		if (orb[i] == INT_MAX) continue;
		for (auto itr : dfsg.g[i]) {
			if (orb[itr.first] == INT_MAX) continue;
			if (orb[i] > orb[itr.first]) continue;

			if (orb[i] <= lowlink[itr.first]) {
				joints.push_back(i);
				break;
			}
		}
	}
	if(dfsg.g[st].size() > 1)
		joints.push_back(st);
}

void Bridge(BiDGraph& g, vector<pii>& bridges, int st = 0) {
	vector<int> lowlink, orb;
	BiDGraph dfsg(g.vn);
	Lowlink(g, lowlink, dfsg, orb, st);

	REP(i, dfsg.vn) {
		for (auto itr : dfsg.g[i]) {
			if (orb[i] > orb[itr.first]) continue;

			if (orb[i] < lowlink[itr.first]) {
				bridges.push_back({ i, itr.first });
			}
		}
	}
}

CF 779 D

知見を得た。


100前後するやつでACできた
判定部分をラムダでまとめるとif(judge())みたいな感じでキレイだし、100前後するやつも書けるので採用
結局、rの値が可能範囲にあったために起きたバグ
半開万歳

signed main() {
	char buf[200001];
	scanf("%s", buf);
	string p = buf;
	scanf("%s", buf);
	string t = buf;
	vector<int> h(p.length());
	REP(i, p.length()) {
		int a;
		scanf("%d", &a);
		a--;
		h[a] = i + 1;
	}
	int l = 0, r = p.length()+100;

	while (1) {

		auto judge = [&](int cur) {
			int pp = 0;
			REP(i, t.length()) {
				bool ex = 0;
				for (; p.length() > pp; pp++) {
					if (p[pp] == t[i] && cur <= h[pp]) {
						ex = 1;
						pp++;
						break;
					}
				}
				if (!ex) {
					return false;
					break;
				}
			}
			return true;
		};
		int mid = (l + r) / 2;

		if (judge(mid)) {
			l = mid;
		}
		else {
			r = mid;
		}

		if (r - l == 1) {
			printf("%d\n", l - 1);
			break;
		}
	}

	return 0;
}