Codeforces Round #403 (Div. 2)
本番ではAしか通らなかった。反省。それ以外はEditorialを読みながら解く。
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; 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
#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"); }
- 方針は合っていたみたいだが実装が良くなかった。反省。