ABC070 参加記録
ABCしかなかったのでABC070に参加しました。
100-200-300-400なので全完できた。
A - Palindromic Number
やるだけ。
int main() { string s; cin >> s; if(s[0] == s[2]) { puts("Yes"); } else { puts("No"); } return 0; }
B - Two Switches
場合分けしまくればO(1)でできるんだろうけどめんどくさいのでいもす法ぽくやった0(N)。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) int main() { int a,b,c,d; cin >> a >> b >> c >> d; int sw[111]; FOR(i,0,111) sw[i] = 0; sw[a]++;sw[b]--;sw[c]++;sw[d]--; FOR(i,1,111) sw[i] += sw[i-1]; int ans = 0; FOR(i,0,111) if(sw[i] == 2) ans++; cout << ans << endl; return 0; }
C - Multiple Clocks
次に全ての針が上むきで揃うのは全ての針の周期の最小公倍数秒後になる。
最小公倍数求めるライブラリ作っておくと良い。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) typedef long long ll; //最大公約数 ll gcd(ll a, ll b) { while (a && b) { if (a >= b) a %= b; else b %= a; } return a + b; } //最小公倍数 ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b;} int main() { int N; cin >> N; ll ans = 1; FOR(i,0,N) { ll in; cin >> in; ans = lcm(ans, in); } cout << ans << endl; return 0; }
D - Transit Tree Path
絶対にKを経由するのでKからそれぞれの頂点iまでの最短距離d[i]を求めておいてd[x]+d[y]を出力すればOK。
今回のグラフは木なので最短距離を求めるのはdfsでもダイクストラでもどっちでも良さそう。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) typedef long long ll; typedef pair<ll, ll> P; const ll inf = 1e15; struct edge{ ll to, cost; edge(ll t, ll c) { to = t, cost = c; } }; // Kからの距離を求めておく int N; vector<edge> G[100005]; ll d[100005]; void dijkstra(int s){ priority_queue<P, vector<P>, greater<P> >que; FOR(i,1,N+1) d[i] = inf; d[s] = 0; que.push(P(0, s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(auto &e : G[v]){ if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } int main() { cin >> N; FOR(i,0,N-1) { ll a, b, c; cin >> a >> b >> c; G[a].push_back(edge(b, c)); G[b].push_back(edge(a, c)); } int Q, K; cin >> Q >> K; // Kからの距離 dijkstra(K); FOR(i,0,Q) { int x, y; cin >> x >> y; cout << d[x] + d[y] << endl; } return 0; }