Do Something

AtCoder abc305 参加メモ

BFS 二分探索累積和 AtCoder

KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305） - AtCoder

B - ABCDEFG

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

int main() {
  char p,q; cin >> p >> q;
  const int n = 7;
  vector<int> a = {0,3,1,4,1,5,9};
  vector<int> s(n+1);
  REP(i,n) s[i+1] = s[i] + a[i];
  cout << abs(s[p-'A'+1] - s[q-'A'+1]) << endl;
  return 0;
}

長方形の上下左右の端は必ず存在するのでそれを探す。見つけたらその境界内を探索してクッキーが置かれていないところが答え

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

int main() {
  int h,w; cin >> h >> w;
  vector<string> s(h);
  REP(i,h) cin >> s[i];

  // l: 左端, r: 右端, b: 下端, t: 上端
  int l = 1e9, r = 0;
  int b = 0, t = 1e9;
  REP(i,h) REP(j,w) {
    if (s[i][j] != '#') continue;
    l = min(l,j);
    r = max(r,j);
    t = min(t,i);
    b = max(b,i);
  }

  for(int i = t; i <= b; i++) for(int j = l; j <= r; j++) {
    if (s[i][j] == '#') continue;
    cout << i+1 << " " << j+1 << endl;
    return 0;
  }
}

D - Sleep Log

二分探索 + 累積和 + α。

クエリの L と R で二分探索して累積和でざっくり寝ていた時間が求まる。そこから、L/R 両端の半端な部分を足し引きして正確な時間を求める。

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

int main() {
  int n; cin >> n;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];
  vector<ll> s(n); // 寝ていた時間の累積和
  for(int i = 2; i < n; i++) {
    s[i] += s[i-1];
    if (i % 2 == 0) s[i] += a[i] - a[i-1];
  }

  int q; cin >> q;
  REP(_,q) {
    ll l,r; cin >> l >> r;
    auto idxl = lower_bound(a.begin(),a.end(),l) - a.begin();
    auto idxr = upper_bound(a.begin(),a.end(),r) - a.begin() - 1;
    ll ans = s[idxr] - s[idxl];
    if (idxl % 2 == 0) ans += a[idxl] - l;
    if (idxr % 2 == 1) ans += r - a[idxr];
    cout << ans << endl;
  }
  return 0;
}

E - Art Gallery on Graph

体力の多い警備員がいる頂点から、その警備員の体力 h 分の距離までを探索していく。訪問した頂点が警備員の体力 h - 距離より大きい値で訪問済みの場合は探索する必要がないので打ち切ってよい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<int,int>;

int main() {
  int n,m,k; cin >> n >> m >> k;
  vector g(n,vector<int>());
  REP(i,m) {
    int a,b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<P> pa(k);
  REP(i,k) {
    int p,h; cin >> p >> h;
    p--;
    pa[i] = {h,p};
  }
  sort(pa.rbegin(),pa.rend()); // h の多い順にソート
  vector<int> mx(n,-1); // mx[i] := 頂点 i に訪問したときの 「警備員の体力 h - 頂点 i までの距離」 の最大値

  auto bfs = [&](int h, int i) -> void {
    queue<P> q;
    q.emplace(i,h);
    while(q.size()) {
      auto [ni,nh] = q.front(); q.pop();
      if (mx[ni] >= nh) continue;
      mx[ni] = nh;
      for(auto nv: g[ni]) q.emplace(nv,nh-1);
    }
  };

  for(auto [h,p]: pa) bfs(h,p);
  vector<int> ans;
  REP(i,n) if (mx[i] != -1) ans.push_back(i+1);
  cout << ans.size() << endl;
  for(int v: ans) cout << v << " ";
  return 0;
}