ABC075参加記録

100-200-300-400だったので全完できた!

実装がいつものABCより重い気がした。

A - One out of Three

A - One out of Three

A == BならCを出力
B == CならAを出力
C == AならBを出力

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,c; cin >> a >> b >> c;
  if(a == b) cout << c << endl;
  if(b == c) cout << a << endl;
  if(a == c) cout << b << endl;
  return 0;
}

B - Minesweeper

B - Minesweeper

'.'の周りの8マスの'#'の個数を数える。

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, W; cin >> H >> W;
  vector<string> vs(H);
  FOR(i,0,H) cin >> vs[i];
  int vy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
  int vx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  FOR(h,0,H) {
    FOR(w,0,W) {
      if(vs[h][w] == '.') {
        int cnt = 0;
        FOR(i,0,8) {
          int y = h + vy[i];
          int x = w + vx[i];
          if(y >= 0 && y < H && x >= 0 && x < W && vs[y][x] == '#') cnt++;
        }
        vs[h][w] = char('0' + cnt);
      }
    }
  }
  FOR(i,0,H) cout << vs[i] << endl;
  return 0;
}

C - Bridge

C - Bridge

辺を1本ずつ取り除いてワーシャルフロイドを使った。

ある辺を取り除いてワーシャルフロイドし、全ての頂点間で移動可能かどうか判定し、不可能な頂点の組みがあったらans++する。

const int inf = 1e9;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ワーシャルフロイド
  int n,m;// 頂点、辺
  cin >> n >> m;
  int a[100], b[100], c[100], dist[100][100];
  CLR(a);CLR(b);CLR(c);
  FOR(i,0,m){
    cin >> a[i] >> b[i];
    a[i]--;b[i]--;
    c[i] = 1;
  }
  int ans = 0;
  FOR(t,0,m) {
    FOR(i,0,n){
      FOR(j,0,n){
        if(i==j) dist[i][j] = 0;
        else dist[i][j] = inf;
      }
    }
    // 連結してるとこはcを代入
    FOR(i,0,m){
      if(i == t) continue;
      dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i]);
      dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i]);
    }
    FOR(k,0,n) FOR(i,0,n) FOR(j,0,n) {
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
    bool brk = false;
    FOR(i,0,n) {
      FOR(j,0,n) {
        if(dist[i][j] == inf) {
          ans++;
          brk = true;
          break;
        }
      }
      if(brk) break;
    }
  }
  cout << ans << endl;
  return 0;
}

普通にDFSで到達可能か調べればよかった。

D - Axis-Parallel Rectangle

D - Axis-Parallel Rectangle

長方形は無限に作れるが、同じ点を含む長方形で面積が一番小さい長方形は、4辺に点がある(角に点がある場合は2辺に点があると考える)長方形である。よって考える長方形は4辺に点がある長方形だけで良い。

x軸に平行な辺上の2点と、y軸に平行な辺上の2点を全探索。

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K; cin >> N >> K;
  ll x[N], y[N];
  FOR(i,0,N) cin >> x[i] >> y[i];
  ll ans = 4e18;
  // x方向2つの点
  FOR(i,0,N) {
    FOR(j,0,N) {
      if(i == j || x[i] >= x[j]) continue;
      // y方向2つの点
      FOR(k,0,N) {
        FOR(l,0,N) {
          if(k == l || y[k] <= y[l]) continue; 
          if(x[i] <= x[k] && x[j] >= x[k] && x[i] <= x[l] && x[j] >= x[l]) {
            if(y[i] <= y[k] && y[i] >= y[l] && y[j] <= y[k] && y[j] >= y[l]) {
              int cnt = 0;
              FOR(c,0,N) {
                if(x[c] >= x[i] && x[c] <= x[j] && y[c] <= y[k] && y[c] >= y[l]) cnt++;
              }
              if(cnt >= K) {
                ans = min(ans, (x[j] - x[i]) * (y[k] - y[l]));
              }
            }
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}