AtCoder蟻本 準備編 １くじ引き・三角形

1-1 くじ引き

JOI 2007 本選 C ダーツ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0529

概要

数列から重複を許して多くとも4つの項を取り出すとき、
取り出した項の和の最大値を答えよ。
ただし、最大値はを超えてはならない。

制約

方針

、のうち1項、のうち2項の和を配列に格納する。
この配列のそれぞれの要素について、
の中から足して以下で最もに近い要素を探す。
その和の最大値を最終的に出力する。

解答

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	while(true){
		ll n, m;
		cin >> n >> m;
		if(n == 0 && m == 0) return 0;

		ll a[n];
		rep(i, n) cin >> a[i];

		vector<ll> v;
		v.push_back(0);
		rep(i, n) if(a[i] <= m) v.push_back(a[i]);
		rep(i, n){
			rep(j, n){
				if(a[i] + a[j] <= m) v.push_back(a[i] + a[j]);
			}
		}

		sort(v.begin(), v.end());
		
		ll ans = 0;
		for(ll x : v){
			auto it = upper_bound(v.begin(), v.end(), m-x);
			it--;
			if(x + *it <= m){
				ans = max(ans, x + *it);
			}
		}

		cout << ans << endl;
	}
}

1-6 三角形

ARC004A 2点間距離の最大値 ( The longest distance )

A: 2点間距離の最大値 ( The longest distance ) - AtCoder Regular Contest 004 | AtCoder

概要

平面上にこの点がある。このうち2点を結んで線分を作るとき、
線分の長さの最大値を求めよ。

制約

方針

全ての線分の長さを算出し、その最大値を出力する。

解答

Submission #3825370 - AtCoder Regular Contest 004 | AtCoder

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	int x[n], y[n];
	rep(i, n) cin >> x[i] >> y[i];
 
	double mx = -1.0;
	for(int i = 0; i< n; i++){
		for(int j = i+1; j < n; j++){
			int xd = x[i] - x[j];
			int yd = y[i] - y[j];
 
			double d = sqrt(xd * xd + yd * yd);
			mx = max(mx, d);
		}
	}
 
	cout << fixed << setprecision(6) << mx << endl;
 
}

ABC051B B - Sum of Three Integers

B - Sum of Three Integers

概要

2つの整数がある。
3つの整数について、
、を満たす
は何通りあるか。

制約

方針①

、は全通り試す。
は自動的にとなるため、これが
以上以下ならの組が1つ出来ることになる。

解答①

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int k, s;
	cin >> k >> s;
 
	ll ans = 0;
	rep(x, k+1){
		rep(y, k+1){
			int z = s - x - y;
			if(0 <= z && z <= k) ans++;
		}
	}
 
	cout << ans << endl;
}

方針②

DP

解答②

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int k, s;
	cin >> k >> s;
	ll dp[8000][3];
	// dp[i][j] := 変数を j+1個使いiを作るときの組み合わせ数
 
	rep(i, s+1) rep(j, 3) dp[i][j] = 0LL;
	rep(i, k+1) dp[i][0] = 1LL;
 
	rep(j, 2){
		rep(i, s+1){
			rep(l, k+1){
				if(i-l >= 0) dp[i][j+1] += dp[i-l][j];
			}
		}
	}
 
	// rep(i, s+1) rep(j, 3) cout << dp[i][j] << (j == 2 ? "\n" : " ");
	cout << dp[s][2] << endl;
}