AtCoder Regular Contest 063 review

Link

• ARC 063 top page
• Editorial

C – 一次元リバーシ / 1D Reversi

• Problem

/*
 * AC	6 ms	512 KB
 */
#include <cstdio>
#include <iostream>

using namespace std;

int main(){
    //freopen("c.in", "r", stdin);
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < s.size() - 1; ++i) {
        if (s[i] != s[i+1]) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

D – 高橋君と見えざる手 / An Invisible Hand

• Problem

I didn’t notice that there is a restriction that each \(A_i\) is different. So it took time for implementation.

/*
 * AC	15 ms	640 KB
 */
#include <cstdio>
#include <iostream>

using namespace std;

#define INF 1e9;

int a[100005];
int N, T;
int maxDiff = 0;

int main(){
    //freopen("d3.in", "r", stdin);

    scanf("%d %d", &N, &T);
    int tmpmin = INF;
    for (int i = 0; i < N; ++i) {
        scanf("%d", &a[i]);
        if (tmpmin > a[i]) tmpmin = a[i];
        int diff = a[i] - tmpmin;
        if (diff > maxDiff) maxDiff = diff;
    }

    int minCount = 0, maxCount = 0;
    tmpmin = INF;
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (tmpmin + maxDiff == a[i]) maxCount++;
        if (tmpmin == a[i]) {
            minCount++;
        } else if (tmpmin > a[i]) {
            // update
            tmpmin = a[i];
            ans += min(minCount, maxCount);
            // re-init
            minCount = 1;
            maxCount = 0;
        }
    }
    ans += min(minCount, maxCount);
    printf("%d\n", ans);
    return 0;
}

E – 木と整数 / Integers on a Tree

• Problem

Follow editorial.

/*
 * AC	78 ms	14208 KB
 */
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

#define INF 1e9

int N, K;
vector<int> edge[100005]; // edge[i] connect from i to edge[i][j].
int v[100005];   // v[i] is written in vertex i
int par[100005]; // vertex i's parent is par[i]
int lb[100005], ub[100005];  // Range [lb[i], ub[i]] is allowed at vertex i, v[i] must be in [lb[i], ub[i]]

int root;

void dfs(int vertex) {
    for (int i = 0; i < edge[vertex].size(); ++i) {
        int nextVertex = edge[vertex][i];
        if (nextVertex != par[vertex]) {
            par[nextVertex] = vertex;
            dfs(nextVertex);
        } else {
            // skip this
        }
    }

    for (int i = 0; i < edge[vertex].size(); ++i) {
        int nextVertex = edge[vertex][i];
        lb[vertex] = max(lb[vertex], lb[nextVertex] - 1);
        ub[vertex] = min(ub[vertex], ub[nextVertex] + 1);
    }
}

// Decide the example of v[i]
void dfs2(int vertex) {
    for (int i = 0; i < edge[vertex].size(); ++i) {
        int nextVertex = edge[vertex][i];
        if (nextVertex != par[vertex]) {
            par[nextVertex] = vertex;
            int tmp;
            tmp = v[vertex] + 1;
            if (lb[nextVertex] <= tmp && tmp <= ub[nextVertex]) {
                v[nextVertex] = tmp;
            } else {
                tmp = v[vertex] - 1;
                if (lb[nextVertex] <= tmp && tmp <= ub[nextVertex]) {
                    v[nextVertex] = tmp;
                } else {
                    // Error, impossible
                    lb[root] = INF;
                    ub[root] = -INF;
                    return;
                }
            }
            dfs2(nextVertex);
        } else {
            // skip this
        }
    }
}

int main(){
    //freopen("e3.in", "r", stdin);
    scanf("%d", &N);
    int a, b;
    for (int i = 0; i < N-1; ++i) {
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        edge[b].push_back(a);

    }
    // init
    for (int i = 1; i <= N; ++i) {
        v[i] = INF;
        lb[i] = -INF;
        ub[i] = INF;
    }

    scanf("%d", &K);
    for (int i = 0; i < K; ++i) {
        int vertex, p;
        scanf("%d %d", &vertex, &p);
        v[vertex] = p;
        lb[vertex] = ub[vertex] = p;
        root = vertex;
    }
    par[root] = root;
    dfs(root);
    dfs2(root);

    if (lb[root] == v[root] && ub[root] == v[root]) {
        // possible
        printf("Yes\n");
        for (int i = 1; i <=N; ++i) {
            printf("%d\n", v[i]);
        }
    } else {
        printf("No\n");
    }



    return 0;
}