誤読

文字通りくそコード

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

マンハッタン距離ー>XとYを分解して考えられるかも