競技プログラミング 11 （過去問 ABC 057）

リアタイ参加できなかったので…。

A: Remaining Time - AtCoder Beginner Contest 057 | AtCoder
A問題（所要時間 1分くらい）

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#define ll long long
const int MOD= 1e9 + 7;
using namespace std;
 
int main()
{
	int a, b;
	cin >> a >> b;
	if (a + b < 24) cout << a + b << endl;
	else cout << a + b - 24 << endl;
	return 0;
}

B: Checkpoints - AtCoder Beginner Contest 057 | AtCoder
B問題（所要時間 12分くらい）
マンハッタン距離って大学への数学で読んだなあと思いました（思っただけです）。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#define ll long long
const int MOD= 1e9 + 7;
using namespace std;
 
int main()
{
	int n, m, l, a[50], b[50], c[50], d[50], ans[50];
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		l = MOD;
		for (int j = 0; j < m; j++) {
			if (l > abs(a[i] - c[j]) + abs(b[i] - d[j])) {
				l = abs(a[i] - c[j]) + abs(b[i] - d[j]);
				ans[i] = j;
			}
		}
		cout << ans[i] + 1 << endl;
	}
	return 0;
}

C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder
C問題（所要時間 28分くらい）
√n にしたかったところを n/2 にしていて少し時間かかりました。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#define ll long long
const int MOD= 1e9 + 7;
const int INF = 1000000005;
using namespace std;
 
int check(ll x) {
	int ret = 0;
	while (x != 0) {
		x /= 10;
		ret++;
	}
	return ret;
}
 
int main()
{
	ll n;
	cin >> n;
	int a, b, ans = INF;
	for (ll i = 1; i <= sqrt(n); i++) {
		if (n == (n / i)*i) {
			a = check(i);
			b = check(n / i);
			ans = min(ans, max(a,b));
		}
	}
	cout << ans << endl;
	return 0;
 
}

D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder
D問題（所要時間 3時間くらい）
今回の個人的問題作（？）
まず1つ、combinationを計算するのに階乗を使用していたのでオーバーフローして計算が全然合わず、1時間経過しました。
（でも途中でKEYABINGO!2を見てる）
次にしょうもないミスを直すのに20分。
最後にどうしてもテストケースが3つ突破できなかったので、諦めて解答を見たら見慣れないモノがあったので自分の解答に入れてみたら即ACでした…。
まぁそれがfixedだったわけですが、今まで小数を扱う問題をまともに練習していなかったので浮動小数点数と固定小数点数の違いがよくわかってませんでした。
情報科学をまともに勉強していない弊害が出てしまいました…。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#define ll long long
const int MOD= 1000000007;
const int INF = 1000000005;
using namespace std;
 
ll nCr(ll n, ll r) {
	ll c[51][51];
	for (int i = 0; i <= 50; i++) {
		c[0][i] = 0;
		c[i][0] = 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= r; j++) {
			c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
		}
	}
	return c[n][r];
}
 
int main() {
	ll n, m = 1, count = 1, a, b, v[50], ans = 0;
	double sum = 0;
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v, v + n);
	for (ll i = n - 1; i > n - a - 1; i--) {
		sum += v[i];
	}
	for (ll i = n - a; i < n; i++) {
		if (v[i] == v[i + 1])count++;
		else {
			m = i + a - n + 1;
			break;
		}
	}
	for (ll i = n - a; i >= 0; i--) {
		if (v[i] == v[i - 1]) count++;
		else break;
	}
	if (v[n - a] == v[n - 1]) {
		for (ll i = a; i <= min(count,b); i++) {
			ans += nCr(count, i);
		} 
	} else {
		ans = nCr(count, m);
	}
 
	cout << fixed << sum / a << endl;
	cout << ans << endl;
	return 0;
}

ということで3完でした。
今回は全体的にアルゴリズムはなんとかなっていても実装の部分で落としてしまった感じなので、もうちょっとコード書いていかなきゃいけないなと思います。