2018-2019 ACM-ICPC, Asia East Continent Finals 문제 해결

다음 모든 AC 문제 해결 프로그램은 Premium Technology 팀에서 제공됩니다.
A. Exotic … Ancient City
해제 링크: 2018 EC-Final 부분 해제(A, J) ABCDEFGIJKL CodeForces Gym 102056 간략한 해제
B. Mysterious … Host
문제 해결 링크: ABCDEFGIJKL CodeForces Gym 102056 간략한 문제 해결
C. Heretical … Möbius
문제풀이 링크: [중국의 잉여정리] [기교] codeforces 102056C Heretical... M捖bius Gym-102056C(2018EC final)-CRT ABCDEFGIJKL CodeForces Gym 102056 간략한 문제풀이
D. Deja vu of … Go Players
AC의 C++ 언어 프로그램:

#include
using namespace std;
#define endl "
"
#define int long long
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int n,m;
main()
{
    IO;
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1,x;i<=n;i++){
            cin>>x;
        }
        for(int i=1,x;i<=m;i++){
            cin>>x;
        }
        if(n>m) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}

E. Immortal … Universe
문제 해결 링크: ABCDEFGIJKL CodeForces Gym 102056 간략한 문제 해결
F. Interstellar … Fantasy
AC의 C++ 언어 프로그램:

#include 
#include 
#include 
#include 
#include 
using namespace std;

const double pi = acos(-1);
double os, ot, st, os2, ot2, st2;
double r1, r2, ans1, ans2, ans3;
typedef struct node {
	double x, y, z;
} node;
double sqr(double x) { return x * x;}
double calR(double a2, double b2, double c2) { return (acos((a2 + b2 - c2) / (2 * sqrt(a2 * b2))));}
double dis2(node a, node b) { return sqr(a.x - b.x) + sqr(a.y - b.y) + sqr(a.z - b.z); } 

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		node oo;
		double R;
		node s, t;
		scanf("%lf%lf%lf%lf", &oo.x, &oo.y, &oo.z, &R);
		scanf("%lf%lf%lf%lf%lf%lf", &s.x, &s.y, &s.z, &t.x, &t.y, &t.z);

		os2 = dis2(oo, s); ot2 = dis2(oo, t); st2 = dis2(s, t);
		if(st2 == 0) {
			printf("%.8lf
", 0.0);
			continue;
		}
		os = sqrt(os2); ot = sqrt(ot2); st = sqrt(st2);
		if(calR(ot2, st2, os2) >= pi / 2 || calR(os2, st2, ot2) >= pi/2) {
			printf("%.8lf
", st);
			continue;
		}
		double R_sot = calR(ot2,os2,st2);
		double h = os * ot * sin(R_sot) / st;
		if(h >= R) {
			printf("%.8lf
", st);
			continue;
		}
		r1 = acos(R / os);
		r2 = acos(R / ot);
		ans1 = sqrt(os2 - R * R);
		ans2 = sqrt(ot2 - R * R);
		ans3 = R * (R_sot - r1 - r2);
		printf("%.8lf
",ans1 + ans2 + ans3);
	}
}

G. Omnipotent … Garland
문제 해결 링크: ABCDEFGIJKL CodeForces Gym 102056 간략한 문제 해결
H. Saintly … Coins
I. Misunderstood … Missing
AC의 C++ 언어 프로그램:

#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int MAXN = 101;
int n;
ll dp[2][MAXN][MAXN*MAXN+1];
ll a[MAXN], b[MAXN], c[MAXN];
int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld", &n);
		for(int i = 1; i <= n; i++)
			scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
		memset(dp, 0, sizeof(dp));
		dp[n & 1][1][n] = a[n];
		for(int i = n - 1; i >= 1; i--) {
			for(int j = 1; j <= n - i; j++) {
				int u = (i + i + j) * (j - 1) / 2 + n, v = (n + n - j + 1) * j / 2;
				for(int k = u; k <= v; k++) {
					dp[i & 1][j + 1][k + i] = max(dp[i & 1][j + 1][k + i], dp[(i + 1) & 1][j][k] + a[i]);
					dp[i & 1][j][k] = max(dp[i & 1][j][k], dp[(i + 1) & 1][j][k] + (k - j * i) * b[i]);
					dp[i & 1][j][k] = max(dp[i & 1][j][k], dp[(i + 1) & 1][j][k] + j * c[i]);
				}
			}
		}
		ll ans = 0;
		for(int j = 1; j <= n; j++)
			for(int k = 1; k <= MAXN * MAXN + 1; k++) ans = max(ans, dp[1][j][k]);
		printf("%lld
", ans);
	}
}

J. Philosophical … Balance
해제 링크: 2018 EC-Final 부분 해제(A, J) ABCDEFGIJKL CodeForces Gym 102056 간략한 해제
K. Desperate … Fire Survive
문제 해결 링크: ABCDEFGIJKL CodeForces Gym 102056 간략한 문제 해결
L. Eventual … Journey
AC의 C++ 언어 프로그램:

#include 
#include 
#include 
#include 
const int MAXN = 100000;
using namespace std;
int lr[MAXN + 5], num[MAXN + 5];
int n, m, nl, nr, nl1, nr1;
int main() {
	cin >> n >> m;
	nl = nr = 0;
	for (int i = 1; i <= n; i++){
		cin >> lr[i];
		if (lr[i]) nl++;
		else nr++;
	}
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		if (lr[u] != lr[v]) {
			if (num[u]==0) {
				if (lr[u] == 1) nl1++;
				else nr1++;
			}
			if (num[v]==0){
				if (lr[v] == 1) nl1++;
				else nr1++;
			}
			num[u]++;
			num[v]++;
		}
	}
	for (int i = 1; i <=n;i++){
		int ans = 0;
		if (lr[i] == 1){
			if (num[i] == 0) ans += nl - 1 + nr1 * 2 + (nr - nr1 ) * 3;
			else ans += num[i] + (nl - 1) + 2 * (nr - num[i]);
		} else{
			if (num[i] == 0) ans += nr - 1 + nl1 * 2 + (nl - nl1) * 3;
			else ans += num[i] + (nr - 1) + 2 * (nl - num[i]);
		}
		if (i != n) cout << ans << " ";
		else cout << ans << endl;
	}
	return 0;
}

문제 해결 링크: ABCDEFGIJKL CodeForces Gym 102056 간략한 문제 해결