Codeforces #228 Div1

だれか心優しい人D教えてください。マジで。

黄色(弱)になった

A
貪欲。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>

using namespace std;
typedef long long ll;

int main() {
    int n;
    int x[102] = {};
    cin >> n;
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        x[d]++;
    }
    int n2 = n;
    int r = 0;
    while (n2) {
        r++;
        int c = 0;
        for (int i = 0; i < 102; i++) {
            while (x[i] && c <= i) {
                x[i]--;
                c++;
                n2--;
            }
        }
    }
    cout << r << endl;
    return 0;
}

B
グラフ。n<=1000に注意。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;
const int MAX_N = 990, MAX_I = 32;
bool e[MAX_N][MAX_N] = {};
int main(int argc, char *argv[]) {
    ll k;
    cin >> k;

    e[0][2] = true;
    e[0][3] = true;
    if (k & 1) {
        e[0][4] = true;
    }
    int l = 2;
    int nl;
    for (ll i = 1; i < MAX_I; i++) {
        nl = l+i+2;
        e[l][nl] = true;
        e[l][nl+1] = true;
        e[l+1][nl] = true;
        e[l+1][nl+1] = true;
        if (k & (1 << i)) {
            e[l][nl+2] = true;
            e[l+1][nl+2] = true;
        }
        for (int j = l+2; j < nl; j++) {
            e[j][nl+j-l+1] = true;
        }
        l = nl;
    }
    if (k&(1LL << MAX_I)) {
        e[nl][1] = true;
        e[nl+1][1] = true;
    }
    for (int i = nl+2; i < nl+MAX_I+2; i++) {
        e[i][1] = true;
    }
    cout << nl+MAX_I+2 << endl;
    for (int i = 0; i < nl+MAX_I+2; i++) {
        for (int j = 0; j < nl+MAX_I+2; j++) {
            cout << ((e[i][j] || e[j][i]) ? 'Y' : 'N');
        }
        cout << endl;
    }
    return 0;
}

C
貪欲。ゼロサムなので自分の最大化＝相手の最小化。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>

using namespace std;
typedef long long ll;
const int MAXN = 110;
int main() {
    int n;
    int sum = 0;
    cin >> n;
    vector<int> v[MAXN];
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int a;
            cin >> a;
            sum += a;
            v[i].push_back(a);
        }
    }
    vector<int> k;
    for (int i = 0; i < n; i++) {
        if (v[i].size()%2) {
            k.push_back(v[i][v[i].size()/2]);
        }
    }
    int cc = 0;
    sort(k.begin(), k.end(), greater<int>());
    for (int i = 0; i < k.size(); i++) {
        if (!(i%2)) cc += k[i];
    }
    for (int i = 0; i < n; i++) {
        int ss = v[i].size()/2;
        for (int j = 0; j < ss; j++) {
            cc += v[i][j];
        }
    }
    printf("%d %d\n", cc, sum-cc);
    return 0;
}