AtCoder abc243 参加メモ

AtCoder Beginner Contest 243 - AtCoder の参加メモ

C - Collision 2

yが同値の座標同士で右向きのx最小値、左向きのx最大値を調べて、 右向きのx最小値 < 左向きのx最大値 になっていたら Yes

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
const int INF = 1e9+5;

int main() {
  int n; cin >> n;
  vector<int> x(n),y(n);
  REP(i,n) cin >> x[i] >> y[i];
  string s; cin >> s;

  map<int,pair<int,int>> mp;
  REP(i,n) mp[y[i]] = { INF, -INF };
  REP(i,n) {
    if (s[i] == 'R') mp[y[i]].first = min( mp[y[i]].first, x[i] );
    if (s[i] == 'L') mp[y[i]].second = max( mp[y[i]].second, x[i] );
  }

  bool ok = false;
  for(auto [k,v]: mp) ok |= (v.first < v.second);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

D - Moves on Binary Tree

愚直に計算するとlong longでもオーバーフローする、LU RU のときは、U の直前の文字を処理する必要がない。stackでそのような計算不要なパターンを取り除いた上で計算をする。

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

int main() {
  int n; ll x; string s;
  cin >> n >> x >> s;

  deque<int> dq;
  REP(i,n) {
    if (dq.size() && dq.back() != 'U' && s[i] == 'U') dq.pop_back();
    else dq.push_back(s[i]);
  }

  while(dq.size()) {
    char c = dq.front(); dq.pop_front();
    if (c == 'U') x = x >> 1;
    else x = (x << 1) + (c == 'R');
  }

  cout << x << endl;
  return 0;
}

E - Edge Deletion

全頂点間の最短移動コストを算出しておいて、m個の辺についてそれぞれ削除可能かどうか判定していく。辺a-bのコストがa-{x}-b のコスト以上であれば辺a-bを削除することができる。全頂点間の最短移動コストは、制約が $ N <= 300 $ なのでワーシャルフロイド(O(N³))で間に合う。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using ll = long long;
const ll LINF = 1e18+5;
struct Edge { int a; int b; int c; };

int main() {
  int n,m; cin >> n >> m;
  vector<Edge> edges(m);
  vector<vector<ll>> dp(n, vector<ll> (n, LINF));
  REP(i,m) {
    int a,b,c; cin >> a >> b >> c;
    a--; b--;
    dp[a][b] = dp[b][a] = c;
    edges[i] = {a,b,c};
  }

  REP(k,n) REP(i,n) REP(j,n) { // warshall_floyd
    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
  }

  int ans = 0;
  for(auto [a,b,c]: edges) {
    REP(i,n) if (dp[a][i] + dp[i][b] <= c) { ans++; break; }
  }
  cout << ans << endl;
  return 0;
}