ABC075 A~D問題 - ドイツ大学院生日記

A問題

解説

これは解説省略します。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

int main(void){
    int a, b, c;
    string s;
    cin >> a >> b >> c;
    if(a == b){
        cout << c << endl;
    }else if(b == c){
        cout << a << endl;
    }else if(a == c){
        cout << b << endl;
    }
    return 0;
}

B問題

B - Minesweeper

解説

全ての' . 'に関して8方向に#がいくつあるかをカウントしていけば良いです。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

int main(void){
    int h, w;
    char field[55][55];
    cin >> h >> w;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> field[i][j]; 
        }
    }
    int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(field[i][j] == '.'){
                int cnt = 0;
                for(int k=0; k<8; k++){
                    int nx = j + dx[k], ny = i + dy[k];
                    if(nx >= 0 && nx < w && ny >= 0 && ny < h && field[ny][nx] == '#'){
                        cnt++;
                    }
                }
                cout << cnt;
            }else{
                cout << "#";
            }
        }
        cout << endl;
    }
    return 0;
}

C問題

C - Bridge

解説

全ての辺に関して、その辺がないものとしてDFSし、全ての頂点を訪れることができるかどうかを調べていきます。
訪れていない頂点があればその辺は橋であり、全ての頂点を訪れることができればその辺は橋ではありません。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

typedef pair<int, int> P;

int n, m;
bool visited[100];
bool AList[100][100];

void dfs(int u){
    visited[u] = true;
    for(int i=0; i<n; i++){
        if(AList[u][i] && !(visited[i]) ){
            dfs(i);
        }
    }
    return;
}

int main(void){
    int ans = 0;

    queue<pair<int, int> > que; 
    cin >> n >> m;

    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        AList[x][y] = true;
        AList[y][x] = true;
        que.push(P(x, y));
    }

    for(int i=0; i<m; i++){

        bool flag = true;
        fill(visited, visited+n, false);

        P p = que.front();
        que.pop();
        AList[p.first][p.second] = false;
        AList[p.second][p.first] = false;

        dfs(0);
        for(int j=0; j<n; j++){
            if(!(visited[j])){
                flag = false;
            }
        }

        if(!(flag) ){
            ans++;
        }

        AList[p.first][p.second] = true;
        AList[p.second][p.first] = true;
    }
    cout << ans << endl;

    return 0;
}

D問題

D - Axis-Parallel Rectangle

解説

ある長方形の区間にいくつ点が含まれているかを数え、それがkを超えている、かつ面積が最小である。この時の最小の面積を出力すれば良いので、長方形の区間をどのようにして決定させるか問題になります。そこで長方形の横の区間を決定付ける値を求めていきます。それは左右の辺には必ず頂点が含まれているため頂点のx座標が左右の端の座標の候補になります。同様にして上下の区間もy座標が候補になるので全て全探索して、その区間に含まれる頂点の個数を数えてあげ面積を保持しながら求めていけば解くことができます。

コード

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int inf = 1e9;
const int mod = 1e9+7;

typedef pair<int, int> P;

int main(void){
    int n, k;
    long long surface = 4e18;
    cin >> n >> k;
    vector<int> vecx, vecy;
    vector<P> vec;
    for(int i=0; i<n; i++){
        int x, y;
        cin >> x >> y;
        vecx.push_back(x);
        vecy.push_back(y);
        vec.push_back(P(x, y));
    }
    sort(vecx.begin(), vecx.end());
    sort(vecy.begin(), vecy.end());
    for(int xi=0; xi<n; xi++){
        for(int xj=xi+1; xj<n; xj++){
            for(int yi=0; yi<n; yi++){
                for(int yj=yi+1; yj<n; yj++){
                    int cnt=0;
                    long long tmp = (long long)(vecx[xj]-vecx[xi])*(vecy[yj]-vecy[yi]);
                    for(int i=0; i<n; i++){
                        P p = vec[i];
                        if(vecx[xi] <= p.first && p.first <= vecx[xj] && vecy[yi] <= p.second && p.second <= vecy[yj] ){
                            cnt++;
                        }
                    }
                    if(cnt >= k && surface > tmp){
                        surface = tmp;
                    }
                }
            }
        }
    }
    cout << surface << endl;
    
    return 0;
}