AtCoder abc264 参加メモ

freee Programming Contest 2022(AtCoder Beginner Contest 264) - AtCoder

B - Nice Grid

  • 法則性を数式にうまく落とし込めなかったので、15x15マスを実際に書いた。
  • 解説にある方法ではチェビシェフ距離(チェス盤距離)で考えると $ max \lbrace |R-8|,|L-8| \rbrace $ の偶奇で判定できるのでそちらのほうが賢い
#include <bits/stdc++.h>
using namespace std;

const vector<string> s = {
  "xxxxxxxxxxxxxxx",
  "x.............x",
  "x.xxxxxxxxxxx.x",
  "x.x.........x.x",
  "x.x.xxxxxxx.x.x",
  "x.x.x.....x.x.x",
  "x.x.x.xxx.x.x.x",
  "x.x.x.x.x.x.x.x",
  "x.x.x.xxx.x.x.x",
  "x.x.x.....x.x.x",
  "x.x.xxxxxxx.x.x",
  "x.x.........x.x",
  "x.xxxxxxxxxxx.x",
  "x.............x",
  "xxxxxxxxxxxxxxx"
};

int main() {
  int r,c;
  cin >> r >> c;
  r--; c--;

  cout << (s[r][c] == 'x' ? "black" : "white") << endl;
  return 0;
}

C - Matrix Reducing

  • $ H <= 10, W <= 10 $ と制約が小さいのでbit全探索することが可能
  • 行と列でそれぞれbit探索する
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'

int main() {
  int h1,w1; cin >> h1 >> w1;
  vector a(h1,vector<int>(w1));
  REP(i,h1) REP(j,w1) cin >> a[i][j];

  int h2,w2; cin >> h2 >> w2;
  vector b(h2,vector<int>(w2));
  REP(i,h2) REP(j,w2) cin >> b[i][j];

  bool ok = false;
  REP(bith, 1<<h1) {
    if (__builtin_popcount(bith) != h2) continue;
    REP(bitw,1<<w1) {
      if (__builtin_popcount(bitw) != w2) continue;
      vector<int> is,js;
      REP(i,h1) if (bith >> i & 1) is.push_back(i);
      REP(j,w1) if (bitw >> j & 1) js.push_back(j);
      vector c(h2, vector<int>(w2));
      REP(i,h2) REP(j,w2) c[i][j] = a[is[i]][js[j]];

      if (b == c) ok = true;
    }
  }

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

D - "redocta".swap(i,i+1)

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

const string atc = "atcoder";
const int n = 7;

int main() {
  string s; cin >> s;
  int ans = 0;
  REP(i,n) {
    int ni = -1;
    for(int j = i; j < n; j++) if (atc[i] == s[j]) ni = j;

    while(i != ni) {
      swap(s[ni],s[ni-1]);
      ans++;
      ni--;
    }
  }
  cout << ans << endl;
  return 0;
}

E - Blackout 2

  • union find で発電所と都市が繋がっているかどうかを管理する
  • 都市はどの発電所に繋がっていても良いのでひとまとめにして考える
  • 辺を削除する操作は難しいので、全て削除した状態から追加する操作(逆操作)で考える
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'

int main() {
  int n,m,e; cin >> n >> m >> e;
  vector<int> u(e),v(e);
  REP(i,e) { cin >> u[i] >> v[i]; u[i]--; v[i]--; }

  int q; cin >> q;
  vector<int> x(q);
  vector<bool> dis(e);
  REP(i,q) {
    cin >> x[i]; x[i]--;
    dis[x[i]] = true;
  }
  reverse(x.begin(),x.end());

  dsu d(n+m);
  // 発電所は全てつなげておく
  REP(i,m) d.merge(n,n+i);
  // q個の操作を全て終えた状態(q個切断した状態)から見ていく
  REP(i,e) if (!dis[i]) d.merge(u[i],v[i]);
  vector<int> ans(q);
  // q個切断した状態の電気が通っている都市数を求めておく
  REP(i,n) if (d.same(i,n)) ans[0]++;

  // 各操作で電気が通るようになる都市数の差分を求めていく
  for(int i = 1; i < q; i++) {
    ans[i] = ans[i-1];
    int nu = u[x[i-1]];
    int nv = v[x[i-1]];
    bool nus = d.same(nu,n);
    bool nvs = d.same(nv,n);
    if (!nus && nvs) ans[i] += d.size(nu);
    if (nus && !nvs) ans[i] += d.size(nv);
    d.merge(nu,nv);
  }

  reverse(ans.begin(),ans.end());
  for(int v: ans) cout << v << endl;
  return 0;
}