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

誤読

文字通りくそコード

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;
}

CF 779 C

本日2度目の誤読な、一回別の問題解いてるのとおんなじだから
差ではい

signed main() {
	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> price[2];
	price[0].resize(n);
	price[1].resize(n);
	int ans = 0;
	REP(i, n) {
		int a;
		scanf("%d", &a);
		price[0][i] = a;
	}
	REP(i, n) {
		int a;
		scanf("%d", &a);
		price[1][i] = a;
		ans += a;
	}

	vector<int> sa(n);
	REP(i, n) {
		sa[i] = price[0][i] - price[1][i];
	}
	sort(ALL(sa));

	REP(i, m) {
		ans += sa[i];
	}
	rep(i, m, n) {
		if (sa[i] < 0)
			ans += sa[i];
		else break;
	}
	printf("%d\n", ans);
	return 0;
}

CF 779 B

誤読な、誤読
太字の周りは1万回読もう

signed main() {
	int k;

	int num;
	scanf("%d %d",&num, &k);
	char buf[11];
	itoa(num,buf,10);
	string str(buf);
	int zc = 0;
	for (auto itr : str) {
		if (itr == '0')
			zc++;
	}
	reverse(ALL(str));
	int ans = 0,cc = 0;
	for (auto itr : str) {
		if (itr != '0') {
			ans++;
		}
		else {
			cc++;
		}
		if (cc == k) {
			break;
		}
	}

	if (cc != k) {
		printf("%d\n", str.length() - 1);
		return 0;
	}
	printf("%d\n", ans);

	return 0;
}