誤読

文字通りくそコード

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

ARC069-D Menagerie

蟻本でのすごい既視感
完全に食物連鎖だ!UF!勝利!優勝!
ではなかったのでね
UFでうまくできそうではあるんだけど、いまいちわからなかったので
思考停止メモ化再帰をした
思考停止で解けるようになったのはそれはそれで嬉しかったりもする
完全に原始人コード

int n;
int s[100001];
int ans[100001];
 
int dp [100001] [2] [2] [2] [2];
 
bool dfs(int cur, int bbk, int bk, int ck, int ek) {
	if (cur == n - 1) {
		ans[n-1] = ek;
		
		bool f = 0;
		if (ck) {
			if (s[cur] && ans[0] == ans[n - 2])
				f = 1;
			else if (!s[cur] && ans[0] != ans[n - 2])
				f = 1;
		}
		else {
			if (s[cur] && ans[0] != ans[n - 2])
				f = 1;
			else if (!s[cur] && ans[0] == ans[n - 2])
				f = 1;
		}
		if (f && ck == ek) {
			REP(i,n) {
				printf("%c",ans[i]?'S':'W');
			}
			printf("\n");
			return 1;
		}
		return 0;
 
	}
	if (dp[cur][bbk][ck][ck][ek] != -1)
		return dp[cur][bbk][ck][ck][ek];
 
	int nk;
	if (ck) {
		if (s[cur])
			nk = bk;
		else
			nk = 1 - bk;
	}
	else {
		if (s[cur])
			nk = 1-bk;
		else
			nk = bk;
	}
	ans[cur] = ck;
	ans[cur-1] = bk;
	return  dp[cur][bbk][ck][ck][ek] = dfs(cur + 1, bk, ck, nk, ek);
}
 
signed main() {
	scanf("%d%*c", &n);
	REP(i, n) {
		char c;
		scanf("%c", &c);
		s[i] = c == 'o';
	}
	Fill(dp, -1);
	if (s[0]) {
		if (dfs(1, 1, 1, 1, 1))
			return 0;
		if(dfs(1, 0, 1, 0, 0))
			return 0;
		if (dfs(1, 1, 0, 0, 1))
			return 0;
		if (dfs(1, 0, 0, 1, 0))
			return 0;
	}
	else {
		if (dfs(1, 1, 1, 0, 1))
			return 0;
		if (dfs(1, 0, 1, 1, 0))
			return 0;
		if (dfs(1, 1, 0, 1, 1))
			return 0;
		if (dfs(1, 0, 0, 0, 0))
			return 0;
	}
	printf("-1\n");
	return 0;
}