[문제 풀이 보고서] 2014 CM / ICPC 아시아 안산 역

제목 링크
C.Coprime（HDU5072）
사고의 방향
'두 개의 상호 질 또는 두 개의 상호 질' 을 만족 시 키 는 3 원 조 의 개 수 를 통계 한 다 는 뜻 이다.우선 폭력 매 거 는 시간 을 초과 할 것 이다.데이터 의 규 모 는 O (n) 의 알고리즘 으로 만 문 제 를 해결 할 수 있 음 을 암시 한다.이렇게 직접 법 으로 집계 하 는 것 은 좀 어 려 운 것 같다.그래서 간접 법 이 우 리 를 도와 번 거 로 움 을 줄 일 수 있 는 지 살 펴 보 자.우 리 는 조건 을 만족 시 키 지 못 하 는 3 원 그룹 을 Not (a, b, c) 로 정의 합 니 다. 이것 은 '있 고 하나의 수 대 상호 질' 이나 '있 고 하나의 수 대 불 상호 질' 을 만족 시 키 는 3 원 그룹 입 니 다.이렇게 하면 Not (a, b, c) 에서 반드시 두 개의 수 는 'Not (a, b, c)' 중의 한 수 와 그 상호 질 을 만족 시 키 고 다른 수 는 그 상호 질 을 만족 시 킬 것 이다.이렇게 하면 우 리 는 문 제 를 '임의의 숫자 a, 얼마나 많은 수 와 불 호 질' 로 바 꿀 수 있다.a 와 서로 질 이 맞지 않 는 수의 수량 을 n (a) 으로 설정 합 니 다.최종 Not (a, b, c) 의 수량 ans = ∑ a (n (a) − 1) (n − n (a)) 2.왜 2 로 나 눠 요?앞에서 언급 했 듯 이 Not (a, b, c) 중 두 개의 수 만족 과 다른 두 개의 수 는 각각 서로 질 적 이 고 서로 질 적 이지 않 기 때문이다.즉, 구 한 Not (a, b, c) 의 수량 은 절반 이 중복 되 는 것 이다.이제 문 제 는 n (a) 을 어떻게 구 하 느 냐 로 완전히 바 뀔 수 있다.우 리 는 a 의 범위 내 에서 a 의 소인 자의 개수 가 매우 적 다 는 것 을 알 아 차 렸 다.그러면 우 리 는 상수 에 가 까 운 시간 안에 a 의 소 인 자 를 매 거 할 수 있다.예 를 들 어 a = 24 라면 a 의 소인 자 는 2 와 3 이다.그래서 n (a) 은 이 소인자 의 배수의 수량 과 같다.이렇게 하면 틀림없이 중 복 된 셈 이다.원수 조 에 6 이 들 어가 면 6 은 2 와 3 으로 두 번 계산 된다.이런 난처 한 국면 을 해결 하기 위해 서 우 리 는 이런 반복 되 는 난처 한 수용 원리 에 전문 적 으로 대처 하여 해결한다.우리 가 매 거 한 소인자 의 조합, 예 를 들 어 a = 24 라면 a 의 소인자 의 조합 은 2, 3, 6 = 2 이다×3 。초기 명령 n (a) = 0, 소수 인자 의 조합 m 에 홀수 개의 소수 인자 가 포함 되 어 있 을 때 n (a) 에 mul (m) (mul (m) 을 더 하면 원시 배열 에서 m 의 배수 의 개 수 를 나타 내 고 mul 배열 은 예비 처리 에서 체 법 을 통 해 선형 으로 처리 할 수 있다).소인자 의 조합 m 에 짝수 개의 소인자 가 포함 되 어 있 을 때 n (a) 은 mul (m) 을 뺀 다.모든 조합 이 매 거 진 후에 n (a) 을 구 할 수 있다.
코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10, maxNum = 1e5 + 10;
int t, n, ub, a[maxn], cnt[maxn], mul[maxn];
ll num, ans, all;
vector <int> pf[maxn];

int main() {
    //            
    for(int i = 2; i < maxNum; i++) {
        if(pf[i].size() == 0) {
            for(int j = i; j < maxNum; j += i) {
                pf[j].push_back(i);
            }
        }
    }
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        ub = 0;
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            ub = max(ub, a[i]);
            cnt[a[i]]++;
        }
        //            
        memset(mul, 0, sizeof(mul));
        for(int i = 1; i <= ub; i++) {
            for(int j = i; j <= ub; j += i) {
                mul[i] += cnt[j];
            }
        }
        ans = 0;
        //    a[i]    a[i']    
        for(int i = 0; i < n; i++) {
            //      1   
            if(a[i] == 1) {
                continue;
            }
            int nf = pf[a[i]].size();
            int nn = 1 << nf;
            num = 0;
            //         
            for(int j = 1; j < nn; j++) {
                //      
                int m = 1;
                int flag = 0;
                for(int k = 0; k < nf; k++) {
                    if((j >> k) & 1) {
                        m *= pf[a[i]][k];
                        flag++;
                    }
                }
                //     ，    
                //    a[i]         
                num += (flag & 1 ? 1 : -1) * mul[m];
            }
            //               
            //             
            if(num > 0) {
                ans += (num - 1) * (n - num);
            }
        }
        all = (ll)n * (n - 1) * (n - 2) / 6;
        printf("%I64d
", all - ans / 2);
    }
    return 0;
}

D.Galaxy（HDU5073）
사고의 방향
이 문 제 는 물리 지식 을 좀 알 아야 할 것 같 지만 사실은 사용 하지 않 는 다.문 제 를 철저히 읽 은 후에 이 문 제 는 실제로 우리 에 게 k 개의 행성 을 이동 한 후 질량 심 과 행성 의 거리의 제곱 과 최소 치 를 구 하 라 는 것 을 발견 했다.매 거 방안 과 매 거 질 심의 복잡 도가 너무 높 기 때문에 우 리 는 주제 의 뜻 을 깊이 파 야 한다.생각 한 결과 우 리 는 '외곽' 의 k 개 행성 을 이동 하 는 경향 이 있 는데 이렇게 하면 비교적 작은 제곱 합 을 얻 을 수 있 을 것 같다.예 를 들 어 우리 가 5 개의 행성 이 왼쪽 에서 오른쪽으로 순서대로 1, 2, 3, 4, 5 라 고 가정 하면 k 가 3 이면 우 리 는 1, 2, 5 또는 1, 4, 5 등 외곽 의 행성 을 이동 하 는 경향 이 있다.사실 이런 욕심 전략 이 효과 적 이라는 것 을 증명 할 수 있다.지금 바로 그것 이 증명 되 었 다 고 생각 합 니 다. 그 다음 에 이 k 개의 행성 은 어디로 이동 합 니까?미래 (이동 후) 로 이동 하 는 질량 심 은 제곱 과 가능 한 한 작 게 할 것 이다.그래서 우 리 는 연속 적 인 n - k 개의 행성 을 매 거 하여 이 행성 들 을 움 직 이지 않 게 한 다음 에 질량 심 을 구하 고 마지막 으로 이 행성 들 이 질량 심 거리의 제곱 합 을 직접 구 할 수 있다.여기까지 알고리즘 은 이미 매우 빠 르 지만 n 의 규모 가 비교적 크 고 연속 적 으로 질량 심 과 제곱 화 를 구하 면 알고리즘 의 복잡 도 를 너무 높 일 수 있다.
질량 심 좌표 에 대해 n - k 개 행성 의 좌표 와 sum 을 유지 하면 질량 심 을 구 할 수 있다.
avg=sumn−k 。
제곱 합
ans=∑i(xi−avg)2 ，
전개
ans=∑ix2i−∑i2×xi×avg+∑iavg2 ，
영 squ = ∑ ix2i, 있 으 면
ans=squ−sum2n−k 。
sum 과 squ 를 유지 하면 ans 를 효과적으로 구 할 수 있 음 을 알 수 있 습 니 다.sum 과 squ 의 값 이 매우 클 수 있 으 므 로 결과 의 정 도 를 확보 하기 위해 long long 형 변 수 를 사용 해 야 합 니 다. 그러면 프로그램 이 미리 부동 소수점 이 나타 나 지 않도록 해 야 합 니 다.이 를 위해 변형 상식 (n - k) ans = (n - k) squ - sum 2 를 통 해 너무 일찍 나눗셈 이 나타 나 지 않도록 함으로써 너무 일찍 부동 소수점 이 나타 나 지 않도록 할 수 있다.
코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 5e4 + 10;
int t, n, k;
ll a[maxn], sum, squ, res, ans;

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; i++) {
            scanf("%I64d", &a[i]);
        }
        if(n == k || n == k + 1) {
            puts("0");
            continue;
        }
        sort(a, a + n);
        sum = squ = 0;
        for(int i = 0; i < n - k; i++) {
            sum += a[i];
            squ += a[i] * a[i];
        }
        ans = (n - k) * squ - sum * sum;
        for(int i = 0; i < k; i++) {
            int j = i + n - k;
            sum += (a[j] - a[i]);
            squ += (a[j] * a[j] - a[i] * a[i]);
            res = (n - k) * squ - sum * sum;
            ans = min(ans, res);
        }
        printf("%.10f
", (double)ans / (n - k));
    }
    return 0;
}

E.Hatsune Miku（HDU5074）
사고의 방향
우선 데이터 규모 때문에 검색 이 안 될 겁 니 다.그 다음으로 이렇게 복잡 한 요소 간 의 의존 관 계 는 욕심 전략 을 찾기 어렵 다 는 것 을 의미한다.그리고 동적 계획 을 시도 해 보 세 요.이것 은 선형 구조 이기 때문에 앞의 n 음표 의 최 적 화 를 고려 합 니 다.우 리 는 d [i] 를 앞의 i 개 (i 개 포함) 음부 로 확정 한 후에 발생 하 는 가장 좋 은 해 로 규정 할 수 있다.지금 우 리 는 d [i], d [i - 1], d [1] 라 는 정 보 를 사용 하여 d [i + 1] 을 확인 하려 고 합 니 다.유감스럽게도 우 리 는 이렇게 적은 정 보 를 통 해서 만 d [i + 1] 을 내 놓 을 수 없다.그렇다면 어떤 정보 가 부족 할 까?생각 한 결과 i 번 째 음부 가 어떤 음부 인지 알 면 d [i + 1] 를 얻 을 수 있 습 니 다.현재 d [i] [j] 를 앞의 i 개 (i 개 포함) 음부 로 다시 규정 한 후, i 번 째 음 부 는 j 이 며, 이러한 상황 (상태) 에서 가장 좋 은 해 입 니 다.이로써 상태 전이 방정식: d [i] [j] = max {d [i - 1] [k] + v [k] [j], 1 ≤ k ≤ m} 을 얻 을 수 있 으 며, 그 중에서 v 는 아름 다운 값 을 확정 하 는 행렬 이다.또한 이 문제 에서 검색 해 가 편리 하기 때문에 동적 계획 대신 기억 화 검색 을 하 는 것 도 좋다.
코드

#include <bits/stdc++.h>
using namespace std;

const int maxn = 105, maxm = 55;
int t, n, m, a[maxn], v[maxm][maxm], d[maxn][maxm];

//      
int dfs(int cur, int num) {
    if(cur > n) return 0;
    int res = 0;
    if(a[cur] > 0) {
        res = v[num][a[cur]] + dfs(cur + 1, a[cur]);
    }
    else {
        //     cur        
        for(int j = 1; j <= m; j++) {
            int tmp = d[cur+1][j] ? d[cur+1][j] : dfs(cur + 1, j);
            res = max(res, v[num][j] + tmp);
        }
    }
    //            
    return d[cur][num] = res;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= m; j++) {
                scanf("%d", &v[i][j]);
            }
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        memset(d, 0, sizeof(d));
        printf("%d
", dfs(1, 0));
    }
    return 0;
}

I.Osu!（HDU5078）
사고의 방향
단순 실현 문제.제목 대로 이 루 면 된다.
코드

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
int kase, n;
double d, ans;
double t[maxn], x[maxn], y[maxn];

int main() {
    scanf("%d", &kase);
    while(kase--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf%lf", &t[i], &x[i], &y[i]);
        }
        ans = 0;
        for(int i = 1; i < n; i++) {
            d = hypot(x[i] - x[i-1], y[i] - y[i-1]);
            ans = max(ans, d / (t[i] - t[i-1]));
        }
        printf("%.10f
", ans);
    }
    return 0;
}

(기타 제목 약)