odan さんと omurice さんと出ていました.
僕はコーディングをしていなかったので, 懇親会を抜けだした後 indeed なうを解いた後書いて見ました.
とりあえずコードだけ.
#include <bits/stdc++.h> #define rep(i, n) for(int i = 0; i < (n); ++i) #define repsz(i, v) rep(i, (v).size()) #define all(v) begin(v), end(v) #define eb emplace_back typedef long long ll; using namespace std; template<typename C> inline int size(const C &c){ return c.size(); } template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;} template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;} signed main(){ cout << std::fixed << std::setprecision(10); int n; cin >> n; vector<int> f(n), a(n), t(n), x(n), y(n); rep(i, n) cin >> f[i] >> a[i] >> t[i] >> x[i] >> y[i]; vector<int> res_len(2, -1), res_time(2, 1<<10); rep(i, n-1) if(t[i] == t[i+1] and a[i] != a[i+1]){ int dx = x[i] - x[i+1], dy = y[i] - y[i+1]; int d = dx*dx + dy*dy; if(chmax(res_len[t[i]], d)) res_time[t[i]] = f[i+1] - f[i]; if(res_len[t[i]] == d) chmin(res_time[t[i]], f[i+1] - f[i]); } rep(i, 2){ if(res_len[i] == -1) cout << "-1 -1" << endl; else cout << sqrt(res_len[i]) << " " << res_time[i]/60.0 << endl; } return 0; }
以下, テンプレは略.
signed main(){ int n; cin >> n; vector<ll> a(n); rep(i, n) cin >> a[i]; sort(all(a)); vector<ll> s(n+1); rep(i, n) s[i+1] = s[i] + a[i]; int m; cin >> m; vector<ll> b(m), c(m); rep(i, m) cin >> b[i]; rep(i, m) cin >> c[i]; rep(i, m){ int t = upper_bound(all(a), b[i]) - begin(a); cout << (s[t] >= c[i] ? "Yes" : "No") << endl; } return 0; }
struct UF{ vector<int> p, min; UF(int n) : p(n, -1), min(n, 1<<29) {} int find(int i){ return p[i] < 0 ? i : p[i] = find(p[i]); } bool unite(int i, int j){ if((i = find(i)) == (j = find(j))) return false; if(p[i] > p[j]) swap(i, j); p[i] += p[j]; chmin(min[i], min[j]); p[j] = i; return true; } }; signed main(){ int n; cin >> n; map<string, int> zip; UF uf(n); rep(i, n){ string name; int cost; cin >> name >> cost; int id = size(zip); if(zip.count(name)) id = zip[name]; zip[name] = id; uf.min[id] = cost; } int m; cin >> m; rep(_, m){ string s, t; cin >> s >> t; uf.unite(zip[s], zip[t]); } ll res = 0; repsz(i, zip) res += uf.min[uf.find(i)]; cout << res << endl; return 0; }
const int mod = 1000 * 1000 * 1000 + 7; signed main(){ int n, l; cin >> n >> l; vector<int> x(n), a(n); rep(i, n) cin >> x[i]; rep(i, n) cin >> a[i]; for(auto &t : x) ++t; vector<int> dp(l+1); dp[0] = 1; rep(i, n){ vector<int> s(l+2); rep(p, l+1) s[p+1] = (s[p] + dp[p]) % mod; rep(p, l+1){ int ok = x[i] == p; ok |= a[i] != 0 and x[i] <= p and (p - x[i]) % a[i] == 0; dp[p] = s[p] * ok; } } cout << accumulate(all(dp), 0LL) % mod << endl; return 0; }
const int INF = 1<<29; signed main(){ int n, M, E, S, T, R; cin >> n >> M >> E >> S >> T >> R; vector<vector<vector<int>>> dist(1<<E, vector<vector<int>>(n, vector<int>(n, INF))); { auto &d = dist[0]; rep(u, n) d[u][u] = 0; rep(_, M){ int s, t; cin >> s >> t; d[s][t] = d[t][s] = 1; } rep(k, n) rep(i, n) rep(j, n) chmin(d[i][j], d[i][k] + d[k][j]); } vector<int> ea(E), eb(E), ec(E); rep(i, E) cin >> ea[i] >> eb[i] >> ec[i]; rep(A, 1<<E) if(A){ rep(i, E) if(A>>i&1){ int B = A ^ (1<<i); auto &d = dist[A]; d = dist[B]; rep(u, n) rep(v, n) chmin(d[u][v], d[u][ea[i]] + 1 + d[eb[i]][v]); rep(u, n) rep(v, n) chmin(d[u][v], d[u][eb[i]] + 1 + d[ea[i]][v]); break; } } int res = INF; vector<int> event(E); rep(i, E) event[i] = i; do{ vector<int> dp(R+1, 0); int u = S; int A = 0; event.eb(-1); for(auto &i : event){ auto &d = dist[A]; rep(r, R+1){ if(r >= d[u][T]) chmin(res, dp[r] + d[u][T]); if(R >= d[S][T]) chmin(res, dp[r] + 1 + d[S][T]); } if(i == -1) break; vector<int> qb(R+1, INF); int v = ec[i]; rep(r, R+1){ if(r >= d[u][v]) chmin(qb[r - d[u][v]], dp[r] + d[u][v]); if(R >= d[S][v]) chmin(qb[R - d[S][v]], dp[r] + 1 + d[S][v]); } u = v; A |= 1<<i; swap(dp, qb); } event.pop_back(); }while(next_permutation(all(event))); if(res == INF) res = -1; cout << res << endl; return 0; }