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

年中春休み

年中春休みじゃないです。

競技プログラミング 10 (復習)

過去の復習です。解けなかったけど復習が不十分なモノが多かったので。

C: Lining Up - AtCoder Beginner Contest 050 | AtCoder
当時、掛け算を全て行ってから10^9+7で割るという作業をしていました。
凄いアホだったと思う。昔のコードをちょっと書き直しただけ。

#include <iostream>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#define ll long long int
using namespace std;
 
int main(){
	ll n;
	ll a[100000];
	ll b = 1, c = 2;
	ll ans = 1;
 
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
 
	if (n % 2 == 0) {
		for (int i = 0; i < n; i += 2) {
			if (a[i] == a[i + 1] && a[i] == b) {
				b += 2;
			}
			else {
				ans = 0; break;
			}
		}
	}
	else {
		if (a[0] != 0) {
			ans = 0;
		}
		else {
			for (int i = 1; i < n; i += 2) {
				if (a[i] == a[i + 1] && a[i] == c) {
					c += 2;
				}
				else {
					ans = 0; break;
				}
			}	
		}
	}
	if (ans != 0) {
		for (int i = 0; i < n / 2; i++) {
			ans *= 2;
                        ans = ans % 1000000007;
		}
	}
	cout << ans << endl;
	return 0;
}


C: Factors of Factorial - AtCoder Beginner Contest 052 | AtCoder
約数を出す方法を当時は思いつきませんでした。
解説を見てなるほど~となって終わっていたのでしっかり実装できるか確認。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#define ll long long
using namespace std;
 
int main() {
	ll n, a[1000], ans = 1;
	cin >> n;
	for (int i = 0; i < 1000; i++) {
		a[i] = 1;
	}
 
	for (int j = 2; j <= n; j++) {
		int k = j;
		for (int i = 2; i < 1000;) {
			if (k % i == 0) {
				k /= i;
				a[i]++;
			} else {
				i++;
			}
		}
	}
	for (int i = 0; i < 1000; i++) {
		ans *= a[i];
		ans = ans % 1000000007;
	}
	cout << ans << endl;
	return 0;
}


C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder
当時は全く思いつかなかったのですが、深さ優先探索でいけそうかな?と思ったので練習がてら。
実装するのに1時間半くらいかかりました。深さ優先探索幅優先探索の実装が苦手すぎる…。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#define ll long long
using namespace std;

int n, m, ans = 0;
bool a[8][8] = {}, b[8] = {};


int dfs(int x, int t) {
	if (t == n - 1) return ans += 1;
	for (int i = 0; i < n; i++) {
		if (a[x][i] && !b[i]) {
			b[i] = true;
			ans = dfs(i, t + 1);
			b[i] = false;
		}
	}
	return ans;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		tmp1--; tmp2--;
		a[tmp1][tmp2] = a[tmp2][tmp1] = true;
	}
	b[0] = true;
	cout << dfs(0, 0) << endl;
	return 0;
}



ということで今日はこんな感じ。
試行錯誤したり、調べながらではあったけど、深さ優先探索が初めて自分の力で実装出来たので嬉しい。
イメージをハッキリさせてもっとサクッと解けるようにしたいです。