ABC075参加記録
100-200-300-400だったので全完できた!
実装がいつものABCより重い気がした。
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
'.'の周りの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
辺を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
長方形は無限に作れるが、同じ点を含む長方形で面積が一番小さい長方形は、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; }