AtCoder Beginner Contest 075

時間ギリギリ 95 分弱でなんとか 4 問全部 AC できた．まあまあうれしい

レートは 200 ちょい上がって名前が緑色になった．

1200 まではビギナーで頑張ろうかなと思う(レギュラーで 1 完とかだと悲しいので…)

A - One out of Three

ある整数 n に対して n XOR n == 0 となるので， 配列に 2 つペアの組複数と 1 つの仲間外れがあるときは全要素の XOR をとると仲間外れがでてくる．

この問題なら A XOR B XOR C を出力しておわり

int problemA()
{
    int A, B, C;
    cin >> A >> B >> C;
 
    cout << (A ^ B ^ C) << endl;
 
    return 0;
}

B - Minesweeper

いつもの 8 方向ループだなと思ったけど脳のクロックが遅いので書くのに 10 分くらいかかった

const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
const int dy[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
 
int H, W;
vector<string> S;
 
void mine(int x, int y)
{
    if (S[y][x] == '#') return;
 
    int count = 0;
    for (int d = 0; d < 8; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
 
        if (nx < 0 || W <= nx || ny < 0 || H <= ny || S[ny][nx] != '#') continue;
 
        count++;
    }
    
    S[y][x] = (char)('0' + count);
}
 
int problemB()
{
    cin >> H >> W;
    
    string tmp;
    for (int i = 0; i < H; i++) {
        cin >> tmp;
        S.push_back(tmp);
    }
 
    for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
            mine(x, y);
        }
    }
 
    for (int i = 0; i < H; i++) cout << S[i] << endl;
 
    return 0;
}

C - Bridge

なんとなく Union Find とか使うんだろうなぁと思ったけど慣れてなかったので BFS でなんとかした

グラフの問題まあまあ苦手

typedef pair<int, int> edge;
vector<edge> edges;
 
int problemC()
{
    int N, M, ans = 0;
    cin >> N >> M;
 
    int v, w;
    for (int i = 0; i < M; i++) {
        cin >> v >> w;
        edges.push_back(edge(v, w));
    }
 
    // i : off にする辺
    for (int i = 0; i < M; i++) {
 
        vector<vector<int> > li(N + 1);
        // 辺 i を除いて隣接リストを作る
        for (int j = 0; j < M; j++) {
            if (j == i) continue;
            edge e = edges[j];
            li[e.first].push_back(e.second);
            li[e.second].push_back(e.first);
        }
 
        queue<int> qu;
        set<int> st;
 
        qu.push(1);
 
        // 頂点 1 とつながっている頂点の個数を数える
        while (!qu.empty()) {
            int v = qu.front();
            qu.pop();
            st.insert(v);
 
            for (int k = 0; k < li[v].size(); k++) {
                if (st.find(li[v][k]) == st.end()) qu.push(li[v][k]);
            }
        }
 
        // N でなければ連結成分が複数ある
        if (st.size() != N) ans++;
    }
 
    cout << ans << endl;
 
    return 0;
}

D - Axis-Parallel Rectangle

₅₀C_i (K <= i <= N) について一個一個調べてたら無理だよな～ということで

• x 座標で点 P[i] をソート
• 区間 [P[i].x, P[j].x] に点が K 個以上含まれるような (i, j) に対して
  • 横の長さ w = P[j].x - P[i].x とおく
  • P[i], P[i + 1], ..., P[j] の y 座標を Y[] に格納してソート
  • 区間 [Y[ii], Y[jj]] に点が K 個以上含まれるような (ii, jj) に対して
    • 縦の長さ h = Y[jj] - Y[ii] とおく
    • 面積 w * h で最小値を更新

この方針でいったら無事 AC した．O(N⁴) かな？

typedef long long lint
#define all(x) (x).begin(), (x).end()
#define INF ((lint)4000000000000000010)

typedef pair<lint, lint> pii;
 
int problemD()
{
    lint N, K;
    lint ans = INF;
    cin >> N >> K;
    vector<pii> ps;
 
    lint x, y;
    for (lint i = 0; i < N; i++) {
        cin >> x >> y;
        ps.push_back(pii(x, y));
    }
 
    sort(all(ps));
 
    // x : 間に K 個以上の点を含む 2 点を選択 [i, j]
    for (lint i = 0; i <= ps.size() - K; i++) {
        for (lint j = i + K - 1; j < ps.size(); j++) {
 
            // 横幅
            lint width = ps[j].first - ps[i].first;
            //cout << "width = " << width << endl;
 
            vector<lint> ys;
            for (int k = i; k <= j; k++) {
                ys.push_back(ps[k].second);
            }
 
            sort(all(ys));
 
            // y : 間に K 個以上の点を含む 2 点を選択
            for (lint ii = 0; ii <= ys.size() - K; ii++) {
                for (lint jj = ii + K - 1; jj < ys.size(); jj++) {
 
                    lint height = ys[jj] - ys[ii];
                    lint area = width * height;
 
                    if (ans > area) ans = area;
 
                }
            }
 
        }
    }
 
    cout << ans << endl;
 
    return 0;
}

最後焦ってたのでコードが雑