AtCoder abc302 参加メモ

TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302) - AtCoder

B - Find snuke

8方向全部の処理をそれぞれ記述すると行数が増えてバグらせやすい。

共通部分を考えて行数をなるべく少なくするように心がける。

#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>;
const string snk = "snuke";
const vector<P> d = {{1,-1},{1,0},{1,1},{0,-1},{0,1},{-1,-1},{-1,0},{-1,1}};

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

  auto f = [&](int i, int j, P dir) {
    auto [di,dj] = dir;
    vector<P> ans;
    REP(k,5) {
      if (i < 0 || j < 0 || i >= h || j >= w) return;
      if (s[i][j] != snk[k]) return;
      ans.emplace_back(i,j);
      i += di, j += dj;
    }
    for(auto [x,y]: ans) cout << x+1 << " " << y+1 << endl;
  };

  REP(i,h) REP(j,w) REP(k,8) f(i,j,d[k]);
  return 0;
}

C - Almost Equal

N <= 8 の制約のため、順列を全列挙(8!)できる。全列挙してそれぞれの条件を満たすかどうかを確かめればよい

#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,m; cin >> n >> m;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  auto f = [&](vector<int>& b) {
    REP(i,n-1) {
      auto now = s[b[i]], nx = s[b[i+1]];
      int cnt = 0;
      REP(j,m) if (now[j] != nx[j]) cnt++;
      if (cnt > 1) return false;
    }
    return true;
  };

  vector<int> b(n);
  iota(b.begin(),b.end(),0);
  bool ok = 0;
  do { ok |= f(b); } while (next_permutation(b.begin(),b.end()));
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

D - Impartial Gift

高橋君か青木君どちらか片方の贈り物を決め打って、もう片方を二分探索で最大になる値を求める。

#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() {
  ll n,m,d; cin >> n >> m >> d;
  vector<ll> a(n),b(m);
  REP(i,n) cin >> a[i];
  REP(i,m) cin >> b[i];
  sort(b.begin(),b.end());

  ll ans = -1;
  REP(i,n) {
    ll now = a[i];
    int idx = upper_bound(b.begin(),b.end(),d+now) - b.begin() - 1;
    if (idx < 0) continue;
    if (abs(now-b[idx]) <= d) ans = max(ans, now+b[idx]);
  }
  cout << ans << endl;
  return 0;
}

E - Isolation

各頂点から接続している頂点を set で持って、それを増やしたり減らしたりする。

割りとそのままな実装でも制限時間に間に合う。

#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,q; cin >> n >> q;
  vector g(n,unordered_set<int>());
  int now = n;
  REP(i,q) {
    int t; cin >> t;
    if (t == 1) {
      int u,v; cin >> u >> v;
      u--; v--;
      g[u].insert(v); g[v].insert(u);
      if ((int)g[u].size() == 1) now--;
      if ((int)g[v].size() == 1) now--;
    } else {
      int v; cin >> v; v--;
      if (g[v].size()) {
        for(auto x: g[v]) {
          g[x].erase(v);
          if (g[x].size() == 0) now++;
        }
        g[v].clear(); now++;
      }
    }
    cout << now << endl;
  }
  return 0;
}