Tasks - Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）

B - Farthest Point

max 値とその index を管理しながら全探索する

#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; cin >> n;
  vector<int> x(n),y(n);
  REP(i,n) cin >> x[i] >> y[i];

  REP(i,n) {
    P mx = {-1,-1};
    REP(j,n) {
      int dx = x[i]-x[j], dy = y[i]-y[j];
      int now = dx*dx+dy*dy;
      if (now > mx.first) mx = {now,j};
    }
    cout << mx.second+1 << endl;
  }
  return 0;
}

C - Colorful Beans

問題文がやや難解に思えた。ビーンズの色が最大 10⁹ と大きいため、map で色毎のおいしさの最小値を持って、その中から最大のおいしさの値が答え

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

int main() {
  int n; cin >> n;
  unordered_map<int,int> mp;
  REP(i,n) {
    int a,c; cin >> a >> c; c--;
    mp[c] = mp.find(c) == mp.end() ? a : min(mp[c],a);
  }
  int ans = -1;
  for(auto [k,v]: mp) ans = max(ans,v);
  cout << ans << endl;
  return 0;
}

D - Medicines on Grid

迷路探索。実際に嵌ったポイントが２つあった。

一度通った道をもう一度通ることがあるか

最短経路ではなく寄り道して薬を取得するのが最適なケースもあるため、一度通った道を通ることはある

薬をどのように使うか

よく考えると薬は今のエネルギーより大きくなる場合、必ず使うのが最適であり薬を使うかどうかの分岐は必要ないことがわかる。

優先度付きキューで最大のエネルギー値の頂点から BFS すると高速に解けた。

#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>;
using P2 = pair<int,P>;
const vector<P> moves = { {-1,0},{0,1},{1,0},{0,-1} };

int main() {
  int h,w; cin >> h >> w;
  vector<string> a(h);
  REP(i,h) cin >> a[i];
  int n; cin >> n;
  vector item(h,vector<int>(w));
  REP(i,n) {
    int r,c,e; cin >> r >> c >> e;
    r--; c--;
    item[r][c] = e;
  }

  auto bfs = [&]() {
    vector dist(h,vector<int>(w,-1));
    // エネルギー値の降順に取り出すキュー
    // P2 := { エネルギー, 位置(i,j) }
    priority_queue<P2, vector<P2>, less<P2>> q;
    // スタート地点をキューへ
    REP(i,h) REP(j,w) if (a[i][j] == 'S') q.emplace(0,P(i,j));

    while(q.size()) {
      auto [e,pa] = q.top(); q.pop();
      auto [i,j] = pa;
      if (a[i][j] == 'T') return true; // goal

      // アイテムは貪欲に使って良い
      e = max(e,item[i][j]);
      if (e <= 0 || dist[i][j] >= e) continue;
      dist[i][j] = e;
      for(auto [di,dj]: moves) {
        int ni = i+di, nj = j+dj;
        if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
        if (a[ni][nj] == '#') continue;
        q.emplace(e-1,P(ni,nj));
      }
    }
    return false;
  };

  cout << (bfs() ? "Yes" : "No") << endl;
  return 0;
}

雑感

D問題で DFS で薬の分岐まで考慮して何度も WA を出してしまった。計算量をぱっと見積もれないのは良くない。

Do Something

AtCoder abc348 参加メモ