誤読

文字通りくそコード

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

ARC069-C Scc Puzzle

僕のIDが題名についてる問題

m/4のところをm/3にしてばぐってた

あとほんとlong longな

signed main() {
	ll n, m;
	scanf("%lld %lld", &n, &m);
	ll ans = min(n, m / 2), ama = m-ans*2;
	if(ama > 0)
		ans += ama / 4;
	printf("%lld\n", ans);
	return 0;
}

ARC044-B 最短路問題

こういう組み合わせやるのがね、すごい不安
SRM(そんなに経験ないけど)で組み合わせや!っていってDPではいみたいのがよくあるので、自信をもってできない
修練が必要
スライドだとテーブル創る云々いってるけどmodpowでポウって感じでよゆう

signed main() {
	int n;
	scanf("%d", &n);
	map<int,int> num;
	int Max = 0;
	REP(i, n) {
		int a;
		scnaf("%d", &a);
		num[a]++;
		Max = max(Max, a);
		if (!i && a != 0) {
			printf("0\n");
			return 0;
		}
	}
	if (num[0] != 1) {
		printf("0\n");
		return 0;
	}
 
	ll ans = 1;
	rep (i, 1, Max+1) {
		ll cur = num[i];
		ll bef = num[i - 1];
 
		ans *= mod_pow(mod_pow(2, bef,MODU)-1,cur,MODU);
		ans %= MODU;
		ans *= mod_pow(2, cur*(cur - 1)/2, MODU);
 
		ans %= MODU;
	}
 
	printf("%lld\n", ans);
	return 0;
}

ARC044-C ビーム

マンハッタン距離は分解して解くことが多い

DPー>(H+W)*Tで思考停止しない

変化がどれだけあるかわかってるなら余計なところを削れるかも

signed main() {
	int w[2], q;
	scanf("%d %d %d", &w[0], &w[1], &q);
 
	map<int,set<int>> biim[2];
 
	REP(i, q) {
		itn a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		c--;
		biim[b][a].insert(c);
	}
	int ans = 0;
 
	REP(cc, 2) {
		int dp[100001] = {};
 
		set<int> bef;
		for (auto itr : biim[cc]) {
			for (auto itr2 = bef.begin(); itr2 != bef.end(); itr2++) {
				if (*itr2 > 0) dp[*itr2] = dp[*itr2 - 1] + 1;
				if (*itr2 < w[cc] - 1) dp[*itr2] = min(dp[*itr2], dp[*itr2 + 1] + 1);
			}
			for (auto itr2 = bef.rbegin(); itr2 != bef.rend(); itr2++) {
				if (*itr2 > 0) dp[*itr2] = dp[*itr2 - 1] + 1;
				if (*itr2 < w[cc] - 1) dp[*itr2] = min(dp[*itr2], dp[*itr2 + 1] + 1);
			}
			for (auto itr2 : itr.second) {
				dp[itr2] = INT_MAX-100000;
			}
			bef = itr.second;
		}
		int ad = INT_MAX;
		REP(i, w[cc]) {
			ad = min(ad, dp[i]);
		}
		if (ad >= INT_MAX-100000) {
			printf("-1\n");
			return 0;
		}
		ans += ad;
	}
	printf("%d\n", ans);
	return 0;
}