競プロ日記

プロコン参加記録とか解いた問題とか

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;
}