AtCoder Grand Contest 005

[TakefumiYamamura]

http://agc005.contest.atcoder.jp/

[TakefumiYamamura]

A - STring

Time limit : 1sec / Memory limit : 256MB

Score : 300 points

Problem Statement

We have a string X, which has an even number of characters. Half the characters are S, and the other half are T.

Takahashi, who hates the string ST, will perform the following operation 1010000 times:

Among the occurrences of ST in X as (contiguous) substrings, remove the leftmost one. If there is no occurrence, do nothing. Find the eventual length of X.

Constraints

2≦|X|≦200,000 The length of X is even. Half the characters in X are S, and the other half are T.

Partial Scores

In test cases worth 200 points, |X|≦200.

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

using namespace std;

int main(){
    string words;
    cin >> words;
    int len = words.size();
    for (int i = 1; i < len; ++i)
    {
        if(words[i-1] == 'S' && words[i] == 'T'){
            words.erase(words.begin() + i);
            words.erase(words.begin() + i - 1);
            i -= 2;
            len -= 2;
        }
    }
    cout << words.size() << endl;
}

note

In c++ language, there is a difference between 'a' and "a". The former is char type and the latter one is string type.

[TakefumiYamamura]

B - Minimum Sum

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

One day, Snuke was given a permutation of length N, a1,a2,…,aN, from his friend.

Find the following:

Constraints

1≦N≦200,000 (a1,a2,…,aN) is a permutation of (1,2,…,N).

Note

• self-balancing binary search tree
• http://pekempey.hatenablog.com/entry/2016/10/02/042213

Following example is a stupid. This computation time is N*N so I can't overcome the limitation.

#include <iostream>

using namespace std;

int main(){
    long long int sum = 0;
    int n;
    int a[200001];

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    for (int l = 0; l < n; ++l)
    {
        int min = 200001;
        for (int r = l; r < n; ++r)
        {
            if(min > a[r]) min = a[r];
            sum += min;
        }
    }
    cout << sum << endl;

}

correct version

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main(){
    long  sum = 0;
    int n;
    int a[200001];
    int pos[200001];
    set<int> data;

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }

    data.insert(0);
    data.insert(n+1);

    for (int i = 1; i <= n; ++i)
    {
        int l, r;
        data.insert(pos[i]);
        set<int>::iterator it = data.find(pos[i]);
        r = *(++it) - pos[i];
        --it;
        l = pos[i] - *(--it);
        sum += (long)i * r * l;
    }
    cout << sum << endl;
}

[TakefumiYamamura]

C - Tree Restoring

Time limit : 2sec / Memory limit : 256MB

Score : 700 points

Problem Statement

Aoki loves numerical sequences and trees.

One day, Takahashi gave him an integer sequence of length N, a1,a2,…,aN, which made him want to construct a tree.

Aoki wants to construct a tree with N vertices numbered 1 through N, such that for each i=1,2,…,N, the distance between vertex i and the farthest vertex from it is ai, assuming that the length of each edge is 1.

Determine whether such a tree exists.

Constraints

2≦N≦100 1≦ai≦N−1

#include <iostream>

using namespace std;

int check_max(int n, int a[]){
    int max = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
    }
    return max;
}

int main(){
    int n;
    int a[101];
    int check[101] = {0};
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    int max = check_max(n, a);
    int lower_limit;
    if(max % 2 == 0){
        lower_limit =  max / 2;
    } else {
        lower_limit = max / 2 + 1;
    }

    int lowest_num_count = 0;
    for (int i = 0; i < n; ++i)
    {
        if(check[a[i]] == false) {
            check[a[i]] = true;
        }
        if(lower_limit == a[i]){
            lowest_num_count++;
            if (lowest_num_count == 2 && (max%2 ==0))
            {
                cout << "Impossible" << endl;
                return 0;
            }

            if (lowest_num_count == 3 && (max%2 ==1))
            {
                cout << "Impossible" << endl;
                return 0;
            }
        }
        if(lower_limit > a[i]){
            cout << "Impossible" << endl;
            return 0;
        }
    }

    for (int i = lower_limit; i <= max; ++i)
    {
        if (check[i] == false)
        {
            cout << "Impossible" << endl;
            return 0; 
        }
    }

    cout << "Possible" << endl;
    return 0;

}