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

誤読

文字通りくそコード

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

CF 779 A

はい
もっと速読

signed main() {
	int n;
	vector<int> cou(5), cou2(5);
	scanf("%d", &n);
	REP(i, n) {
		int a;
		scanf("%d", &a);
		a--;
		cou[a]++;
	}
	REP(i, n) {
		int a;
		scanf("%d", &a);
		a--;
		cou2[a]++;
	}
	REP(i, 5) {
		if ((cou[i] + cou2[i]) % 2) {
			printf("-1\n");
			return 0;
		}
	}

	int cc = 0;

	REP(i, 5) {
		cc += abs((cou[i] + cou2[i]) / 2 - cou[i]);
	}

	printf("%d\n", cc/2);

	return 0;
}

CF 776D - The Door Problem

コンテスト中にACできなかった、悲しい

ツイッターで思いっきり嘘解法を述べてしまった

lockを2回介してもUniteできるので、unite出来なくなるまで無限に回す(不安)

最初、ライツアウトだし方程式立ててガウスジョルダンで常勝wwwwwってやってたけど10^10だった

ガウスジョルダンを自前で書きたいので今度書く

signed main() {

	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> door(n);
	REP(i, n) {
		scanf("%d", &door[i]);
	}
	UnionFind uf(m + 2);
	vector<vector<int>> fs(n);
	vector<pair<int, vector<int>>> sw;
	int k;
	REP(i, m) {
		scanf("%d", &k);
		vector<int> lt;
		REP(j, k) {
			int a;
			scanf("%d", &a);
			a--;
			fs[a].push_back(i);
			if (!door[a])
				lt.push_back(a);
		}
		sw.push_back({ i,lt });
	}
	REP(i, n) {
		if (door[i]) {
			uf.unionSet(fs[i][0], fs[i][1]);
		}
	}

	bool f = 1;
	while (f) {
		map<int, set<int>> kanset;
		f = 0;
		for (auto itr : sw) {
			for (auto itr2 : itr.second) {
				if (!door[itr2]) {
					for (auto itr3 : fs[itr2]) {
						if (itr3 != itr.first)
							kanset[uf.root(itr3)].insert(uf.root(itr.first));
					}
				}
			}
		}
		for (auto itr : kanset) {
			if (!itr.second.empty()) {
				int to = *itr.second.begin();
				for (auto itr2 : itr.second) {
					if (!uf.findSet(to, itr2))
						f = 1;
					uf.unionSet(to, itr2);
				}
			}
		}
	}
	REP(i, n) {
		if (!door[i]) {
			if (uf.findSet(fs[i][0], fs[i][1])) {
				printf("NO\n");
				return 0;
			}

		}
	}
	printf("YES\n");
	return 0;
}

ARC069-E Frequency

はい
実際に書けばわかる

E<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<D


#define int ll
signed main() {
	int n;
	scanf("%lld", &n);
	vector<int> ax;
	map<int, int> ar;
	map<int, int> ac;
	REP(i, n) {
		int a;
		scanf("%lld", &a);
		if(!ar.count(a))
			ar[a] = i;
		else
			ar[a] = min(ar[a], i);
		ac[a]++;
		ax.push_back(a);
	}
	ax.push_back(0);
	sort(ALL(ax));
	ax.erase(unique(ALL(ax)), ax.end());
	sort(ALL(ax),greater<int>());
	vector<int> ans(n);
	int axc = 0;
	auto itr = ar.rbegin();
	for (axc = 0; axc < ax.size()-1; itr++) {
		pii cur = *itr;
		ans[itr->second] += (ax[axc] - ax[axc + 1]) * ac[itr->first];
		ac[ax[axc + 1]]+= ac[ax[axc]];
		ar[ax[axc + 1]] = min(ar[ax[axc + 1]], itr->second);
		axc++;
	}
	REP(i, n) {
		printf("%lld\n", ans[i]);
	}
	return 0;
}