Codeforces Round #403 (Div. 2)

本番ではAしか通らなかった。反省。それ以外はEditorialを読みながら解く。

A

Problem - 782A - Codeforces

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> x(n, 0);
    int count = 0;
    int ans = 0;
    int t;
    REP(i, 2*n) {
        cin >> t;
        t--;
        if(x[t]==1) {
            x[t] = 0;
            count--;
        } else {
            count++;
            ans = max(ans, count);
            x[t] = 1;
        }
    }
    cout << ans << endl;
}

B

Problem - B - Codeforces

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> x(n), v(n);
    REP(i, n) cin >> x[i];
    REP(i, n) cin >> v[i];
    

    double lb = 0, ub = 1e9;;
    for(int i=0; i<100; ++i) {
        double t = (lb + ub) / 2.0;
        double L = -numeric_limits<double>::max();
        double R = numeric_limits<double>::max();
        REP(i, n) {
            L = max(x[i] - t * v[i], L);
            R = min(x[i] + t * v[i], R);
        }
        if(L <= R) ub = t;
        else lb = t;
    }
    printf("%.10f\n", lb);
}

• 二分探索は探索回数で抑えるべき。

C

Problem - A - Codeforces (div1ではA問題）

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

vector<vector<int>> G;
vector<int> C;
vector<set<int>> ban;
int ans = 1;

void dfs(int v, int c, int p) {
    C[v] = c;
    int t = 0;
    for(auto i : G[v]) {
        if(C[i] == -1) {
            do {t++;} while(t==c || t==p);
            dfs(i, t, c);
        }
    }
    ans = max(t, ans);
}

int main(void) {
    int n;
    scanf("%d", &n);
    G.resize(n);
    C.resize(n, -1);
    ban.resize(n);
    REP(i, n-1) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(0, 1, -1);
    cout << ans << endl;
    cout << C[0];
    for(int i=1; i<n; ++i) printf(" %d", C[i]);
    printf("\n");
}

• 方針は合っていたみたいだが実装が良くなかった。反省。