[코드포스] Codeforces Round #775 (Div. 2) (코포 775 딥2) 풀이

https://codeforces.com/contest/1649

Dashboard - Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics) - Codeforces

 

 

A. Game

풀이

• 인접한 땅과 땅사이 이동은 비용없이 가능
• 점프 단 한번 할 수 있는데 i, i + x 점프 비용 x
• 물 없으면 비용 0 으로 갈 수 있고 물이 있으면 점프를 첫부분과 연결된 땅의 오른쪽 끝에서 시작하여 , 끝부분과 연결된 땅의 왼쪽끝에서 도착하는 것이 최적이다.

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
 
        vector<int> a(N);
        long long ans = 0;
        for (int i = 0; i < N; ++i) {
            cin >> a[i];
        }
 
        int i = 0;
        while (i < N - 1) {
            if (a[i + 1] == 0) {
                break;
            }
            ++i;
        }
        if (i == N - 1) {
            cout << "0\n";
            continue;
        }
 
        int j = N - 1;
 
        while (j > 0) {
            if (a[j - 1] == 0) {
                break;
            }
            --j;
        }
 
        cout << j - i << '\n';
    }
 
}

 

B. Game of Ball Passing

풀이

• 패스 수 대로 배열 정렬
• 1, 2, 3, ... , n 번 그룹에서 n 번 공 가지고 출발해서 앞번호로 차례로 패스, n 번 마지막으로 공가져간다고 하면
• a[n] <= sum(a[1] ... a[n - 1]) 일 때 1개의 공으로 다 처리 가능,
  • 1번 0 될 때까지 1, ... n 그룹 패스
  • 2번 0 될 때까지 2, ... n 그룹 패스
• a[n]  이 클 때는 큰만큼 추가 공 필요

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
 
        vector<long long> a(N);
        long long sum = 0;
        for (auto & e : a) {
            cin >> e;
            sum += e;
        }
        sort(all(a));
        if (a.back() == 0) {
            cout << "0\n";
            continue;
        }
 
        long long ans = 1;
        if (sum - a.back() < a.back()) {
            ans = a.back() - sum + a.back();
        }
 
        cout << ans << '\n';
    }
}

 

C. Weird Sum

풀이

• 하나의 color 에 대해서
  • x 좌표들에 대해서
    • 그 x 좌표가 정답에 더해지는 부분은 그 좌표보다 작은 부분들 - 그 x 좌표 

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 
    map<int, map<int, int> > mr;
    map<int, map<int, int> > mc;
    set<int> colors;
    int N, M;
    cin >> N >> M;
 
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int c;
            cin >> c;
            colors.insert(c);
            ++mr[c][i];
            ++mc[c][j];
        }
    }
 
    long long ans = 0;
    for (auto c: colors) {
        long long tmp = 0;
        long long tmpCnt = 0;
        for (auto it = mr[c].begin(); it != mr[c].end(); ++it) {
            ans += (it -> first * tmpCnt - tmp) * it -> second;
            tmp += it -> first * it -> second;
            tmpCnt += it -> second;
        }
 
        tmp = 0;
        tmpCnt = 0;
        for (auto it = mc[c].begin(); it != mc[c].end(); ++it) {
            ans += (it -> first * tmpCnt - tmp) * it -> second;
            tmp += it -> first * it -> second;
            tmpCnt += it -> second;
        }
    }
    cout << ans << '\n';    
}

 

D. Integral Array

풀이

• 몫의 범위는 0 ~ C
• 지금 배열안에 존재하지 않는 값에 대하여, 그 값이 몫으로 나올 수 있는지 체크
• 모든 배열 원소에 대하여, 원소 값을 x 라 하면, x * c ~ x * (c + 1) 사이에 값이 있으면 몫으로 그 값이 나올 수 있겠다.
• c 는 0~C 까지 돌려야되고 x 는 x * c <= C 까지만 돌려도 되므로
• 시간 복잡도 계산은 C + C/ 2 + C / 3 ...  = ClogC

코드

• 시간복잡도: $O(ClogC)$

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int TC; cin >> TC;
    while (TC--) {
        int N, C;
        cin >> N >> C;
 
        vector<int> exist(C + 1, false);
        vector<int> a(N);
        for (auto& e: a) {
            cin >> e;
            exist[e] = true;
        }
 
        vector<int> pe(C + 1, 0);
        for (int i = 1; i < C + 1; ++i) {
            pe[i] = pe[i - 1] + exist[i];
        }
 
        bool yes = true;
        for (int i = 1; i <= C; ++i) {
            if (exist[i]) continue;
            for (int j = 1; j * i <= C; ++j) {
                if (!exist[j]) continue;
                // i not exist, j exist, check exist something / j = i
                if (pe[min(C, j * (i + 1) - 1)] - pe[j * i - 1]) {
                    yes = false;
                    break;
                }
            }
            if (!yes) break;
        }
 
        if (yes) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

 

 

E. Tyler and Strings

풀이

• j = 0 ... i -1 에서 s[j] = t[j] 이고, s[i] < t[i] 인 개수 를 i가 0 ... m 일 때 더해주면 답이다.

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    long long N, M;
    cin >> N >> M;
 
    vector<long long> s(N), t(M);
    vector<long long> t2(2 * 200001, 0);
    vector<long long> fact(200001, 1LL);
    long long MOD = 998244353;
    for (long long i = 1; i < fact.size(); ++i) {
        fact[i] = i * fact[i - 1] % MOD;
    }
 
    auto fpow = [&](long long base, long long p) {
        long long ret = 1;
        while (p) {
            if (p & 1) {
                ret = ret * base % MOD;
            }
            base = base * base % MOD;
            p >>= 1;
        }
        return ret;
    };
 
    int n = 200001;
    long long div = 1;
 
    for (auto& e: s) {
        cin >> e;
        ++t2[n + e];
    }
 
    for (long long i = 1; i <= 200000; ++i) {
        if (t2[n + i]) {
            div = div * fpow(fact[t2[n + i]], MOD - 2) % MOD;
        }
    }
 
    for (auto& e: t) {
        cin >> e;
    }
 
    for (int i = n - 1; i >= 1; --i) {
        t2[i] = t2[i << 1] + t2[i << 1 | 1];
    }
 
    auto query = [&](int l, int r) {
        long long ret = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret += t2[l++];
            if (r & 1) ret += t2[--r];
        }
        return ret;
    };
 
    auto update = [&](int p, int val) {
        for (t2[p += n] = val; p > 1; p >>= 1) t2[p >> 1] = t2[p] + t2[p ^ 1];
    };
 
    long long ans = 0;
    for (int i = 0; i < M; ++i) {
        ans += div * fact[N - i - 1] % MOD * query(0, t[i]) % MOD;
        ans %= MOD;
 
        if (t2[n + t[i]]) {
            div = div * t2[n + t[i]] % MOD;
            update(t[i], t2[n + t[i]] - 1);
        } else {
            if (i >= N) ans += 1, ans %= MOD;
            break;
        }
    }
    cout << ans << '\n';
}