AGC 023 A-C

昨日AGC023に出ました.

順位:657位

パフォーマンス:1475

レーティング:1662→1641(-21)

はい,大爆死という奴ですね...

A問題は200点じゃないけどすぐわかる.でもB問題がぜんぜんわからず,C問題に行くなどしてたら終わってしまった.ただ自分が失敗してしまっただけで実装もシンプルで良い問題だった.

続きを読む

Codeforces #453 Div2C

Codeforces #453 Div2C Hashing Trees

根つき木を,高さiの頂点がいくつあるかをa[i]と対応させることをかんがえる.配列aが与えられる.この配列に対応する木が一つにかぎられるかどうかを判定せよ.二つ以上存在するときは,そのような木を二つ構成せよ.

a[i]>1かつa[i+1]>1となるようなiが存在するときは,高さi+1の頂点を高さiの頂点のどれに割り振るかで異なる二つの木が作れる.逆に全てのiについてa[i]≦1またはa[i+1]≦1のときは明らかに一通りの木しかない.構成は適当に頑張る.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int a[100000];
int par1[200000];
int par2[200000];
int main() {
    int h;
    cin >> h;
    for (int i = 0; i < h + 1; i++) cin >> a[i];
    bool ok = 1;
    for (int i = 1; i < h + 1; i++) {
        if (a[i - 1] > 1 && a[i] > 1) {
            ok = 0;
            break;
        }
    }
    if (ok) {
        cout << "perfect" << endl;
        return 0;
    }
    par1[0] = 0;
    int idx = 1;
    for (int i = 1; i < h + 1; i++) {
        int p = idx;
        for (int j = 0; j < a[i]; j++) par1[idx++] = p;
    }
    par2[0] = 0;
    idx = 1;
    for (int i = 1; i < h + 1; i++) {
        if (a[i - 1] > 1 && a[i] > 1) {
            int p1 = idx;
            int p2 = idx - 1;
            for (int j = 0; j < a[i] - 1; j++) par2[idx++] = p1;
            par2[idx++] = p2;
        }
        else {
            int p = idx;
            for (int j = 0; j < a[i]; j++) par2[idx++] = p;
        }
    }
    cout << "ambiguous" << endl;
    cout << par1[0];
    for (int i = 1; i < idx; i++) cout << " " << par1[i];
    cout << endl;
    cout << par2[0];
    for (int i = 1; i < idx; i++) cout << " " << par2[i];
    cout << endl;
}

Codeforces #459 Div2C

Codeforces #459 Div2C TheMonster

(または)または?からなる文字列sが与えられる.sの部分文字列のうち,?を(または)に置きかえたとき正しいカッコ列(左カッコと右カッコの対応がとれた列)に出来るものはいくつあるか?という問題.

始点を固定して,そこから伸ばしていく.カッコ列といえばA=(左カッコの数)-(右カッコの数)が常に0以上(★)であって末尾まで見たときAが0になっていればいいという有名な話がある.今回は?があるのだが,それは問題が生じるまで全て)だとみなしてしまう.ある所でAが負になったら,そこでこれまでに出てきた?を)から(にかえて+2してやる(もう?がのこっていなければ無理).この方法で文字列を作っていくと,★を満たす中で最も(がすくないものが見つかる.このときA=0ならばOK.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int now = 0;
        int cnt = 0;
        for (int j = i; j < n; j++) {
            if (s[j] == '(') now++;
            else now--;
            if (s[j] == '?') cnt++;
            if (now < 0) {
                if (cnt == 0) break;
                cnt--;
                now += 2;
            }
            else if (now == 0) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

ARC 096 C-E

昨日ARC096に出ました.

順位:212位

パフォーマンス:2008

レーティング:1608→1662(+54)

早どきに失敗した割には黄パフォ出て良かったかな.今年ICPCでチームを組むolpheしゃんは黄だしferinしゃんも黄になりそうなので,僕もちゃんとコンテストに出てレート上げないとね.明日から何やろう.

続きを読む