Codeforces Round#351 Div2

http://codeforces.com/contest/673
涙の二完。
A: Bear and Game
　なんかテレビを15分見ると飽きるとかいう問題。これに10分かかるのは遅いなあ……。

bool t[100];
int main(){
    int n; scanf("%d", &n);
    memset(t, 0, sizeof(t));
    rep(i, n){
        int a; scanf("%d", &a);
        t[a] = true;
    }
    int ans = 0, sum = 0;
    REP(i, 1, 91){
        if(t[i]) sum = 0;
        else sum++;
        if(sum == 15){
            printf("%d\n", i);
            return 0;
        }
    }
    puts("90");
    return 0;
}

B : Problem for Round
　グループ分け。Div2の最大値とDiv1の最小値を持てばできます。m == 0がコーナー。

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int lo = -1, up = INF;
    rep(i, m){
        int a, b;
        scanf("%d%d", &a, &b);
        int c = min(a, b), d = max(a, b);
        lo = max(lo, c);
        up = min(up, d);
    }
    if(lo >= up){
        puts("0");
        return 0;
    }
    if(m == 0){
        printf("%d\n", n - 1);
        return 0;
    }
    int res = up - lo;
    printf("%d\n", res);
    return 0;
}

C : Bear and Colors
1~nからなる数列が与えられます。ある連続部分列において最も出現回数が多い数字がdominant numberとされるので、数字ごとのdominant獲得回数を求めろと言う問題。
　３乗を投げてTLEしてしまったのですが、普通に区間をスライドさせて数字ごとの出現回数を記録すれば大丈夫ですね……。

int f[5000], res[5000], t[5000];
int main(){
    int n; scanf("%d", &n);
    rep(i, n) {
        scanf("%d", t + i);
        t[i]--;
    }
    rep(i, n){
        memset(f, 0, sizeof(f));
        int ma = -1, x = -1;
        REP(j, i, n){
            f[t[j]]++;
            if(ma < f[t[j]] || (ma == f[t[j]] && x > t[j])){
                ma = f[t[j]];
                x = t[j];
            }
            res[x]++;
        }
    }
    rep(i, n)
      printf("%d\n", res[i]);
    return 0;
}

D : Bear and Two Points
　一見ゴツく見えるけど実は貪欲で解けます、という。
a-c-hoge-d-b
c-a-hoge-b-d（hogeは共通)
という風にすれば、共通の辺がn - 3個のパスが作れます。必要な辺の数は共通辺＋共通じゃない辺×２でn + 1個だから、k <= nのときはダメです。あとn == 4でもダメ。

int main(){
    int n, k, a, b, c, d;
    vector<int> path;
    scanf("%d%d", &n, &k);
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if(n == 4 || k <= n) goto fail;
    REP(i, 1, n + 1)
      if(i != a && i != b && i != c && i != d)
        path.push_back(i);
    printf("%d %d ", a, c);
    rep(i, n - 4)
      printf("%d ", path[i]);
    printf("%d %d\n", d, b);
    printf("%d %d ", c, a);
    rep(i, n - 4)
      printf("%d ", path[i]);
    printf("%d %d\n", b, d);
    return 0;
  fail:
    puts("-1");
    return 0;
}

Eは難しいのでまた後で書きます。

それにしてもCFは本当にダメだなあ。まともな成績を取れたことが一度もありません。