だれか心優しい人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; }