Codeforces Round #253 (Div. 1) (A, B, C)

Codeforces Round #253 (Div. 1)
タイトルリンク
A:いくつかのカードを与えて、それから今いくつかのカードの情報を提示して、ヒントを最小限に抑えて、すべてのカードが見分けられるようにします.考え方:全部で2^10種類の状況を直接暴力的に列挙し、それぞれの状況を推定し、推定するときは2枚のカードを列挙して推定すればいい.CF機は本気で強いと言わざるを得ませんが、2秒制限でも10^8は走れます
B:n個の発生確率を与えて、中のいくつかの事件を選んで、ちょうど1件の発生確率が最大になるようにします.構想:貪欲で、大きいから小さいまで確率を並べて、それから一つ一つの確率が入ってきてもっと大きいかどうかを推定して、あるならこの事件を増加して、ないならスキップします
C:n個の数字を与えて、一つ一つ数字を削除することを要求して、数字の左あるいは右に数字がないと得点しないと仮定して、さもなくば得点はmin(左の数字、右の数字)です.考え方:貪欲で、2つの状況を考慮して、1つの下凹の形状で、このような状況の下で間違いなく中間の優先から両側に持って行って、このような状況に対して1つのスタックでメンテナンスすることができて、毎回スタックに入る前に、まず間を取って答えを記録して、スタックに入ります.このように処理し終わって、下の凹みの形はすべてなくて、図形は先に増加してから形を減らして、この時答えは固定して、最大の2つの値はきっと取れないので、残りはすべて取ることができます.この二つの部分を合わせると答えです
コード:A題:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const char c[15] = {'1', '2', '3', '4', '5', 'B', 'Y', 'W', 'G', 'R'};

int n, vis[105][2];
char card[105][5];

int bitcount(int x) {
    if (x == 0) return 0;
    return bitcount(x>>1) + (x&1);
}

bool judge(int s) {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 10; i++) {
    if (s&(1<<i)) {
        for (int j = 0; j < n; j++) {
        for (int k = 0; k < 2; k++) {
            if (card[j][k] == c[i])
            vis[j][k] = 1;
        }
        }
    }
    }
    for (int i = 0; i < n; i++) {
    if (vis[i][0] && vis[i][1]) continue;
    for (int j = i + 1; j < n; j++) {
        if (strcmp(card[i], card[j]) == 0) continue;
        if (vis[j][0] && vis[j][1]) continue;
        if (!vis[i][0] && !vis[i][1] && !vis[j][0] && !vis[j][1]) return false;
        if (!vis[i][0] && !vis[j][0] && card[i][1] == card[j][1]) return false;
        if (!vis[i][1] && !vis[j][1] && card[i][0] == card[j][0]) return false;
    }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    scanf("%s", card[i]);
    int ans = 10;
    for (int i = 0; i < (1<<10); i++) { 
    if (judge(i)) {
        ans = min(ans, bitcount(i));
    }
    }
    printf("%d
", ans);
    return 0;
}

B題:

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 105;
int n, save[N], sn;
double p[N], sum;

double cal(int now) {
    double ss = sum * (1 - p[now]);
    double ans = sum * p[now];
    for (int i = 0; i < sn; i++) {
    ans += ss / (1 - p[save[i]]) * p[save[i]];
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
    scanf("%lf", &p[i]);
    }
    sort(p, p + n);
    sn = 1;
    save[0] = n - 1;
    sum = (1 - p[n - 1]);
    double Max = p[n - 1];
    for (int i = n - 2; i >= 0; i--) {
    double tmp = cal(i);
    if (tmp > Max) {
        sum *= (1 - p[i]);
        Max = tmp;
        save[sn++] = i;
    }
    }
    printf("%.12lf
", Max);
    return 0;
}

C題:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 500005;
int n, top;
long long stack[N], x, ans;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    while (top > 0 && stack[top - 1] >= stack[top] && x >= stack[top]) {
        ans += min(stack[top - 1], x);
        top--;
    }
    stack[++top] = x;
    }
    sort(stack + 1, stack + 1 + top);
    for (int i = 1; i <= top - 2; i++) {
    ans += stack[i];
    }
    printf("%lld
", ans);
    return 0;
}