AtCoder Regular Contest 111

문제 링크

atcoder.jp/contests/arc111

 

 

A. Simple Math 2

문제

정수 N, M이 주어졌을 때 (|10^N / M|) % M 값을 구하는 문제입니다.

 1 <= N <= 10^18

 1 <= M <= 10000

풀이1

소스코드1

 

B. Reversible Cards

문제

1 ~ N까지 카드가 있습니다. 이때 카드의 앞 뒷면에 다른 색상의 Ai, Bi의 숫자가 적혀있습니다. 이때

각 카드에 대해 표시된 면을 선택할 수 있습니다. 표시되는 다른 색상의 최대 가능한 수를 찾는 문제입니다.

 1 <= N <= 200000

 1 <= Ai, Bi <= 400000

 

풀이1

일단 다양한 풀이가 있으리라 생각 되는 문제인데 제가 접근한 방법이 정해는 아닌 것 같습니다(dfs,bfs만으로 된다는것 같네요)

제가 접근한 방식은 이분매칭을 이용한 방법입니다. 비슷한 문제로 축사 배정이라고 유명한 문제가 있는데 그와 동일합니다.

이분매칭에 대해 짧게만 설명드리자면, 카드들의 리스트를 A라고 하고 모든 숫자들이 속하는 그룹을 B라고 하면 A에서 B로가는 간선들을 만듭니다.(해당 문제에서는 각 원소마다 두개의 간선이 나오겠네요)

그런다음 간선들을 골랐을때 각 간선의 양 끝 두 노드가 중복되어 선택되지 않게 최대의 경우를 뽑습니다

다시말해 간선 e1에 의해 a1과b1이 선택되면 a1과 b1이포함된 다른 간선들은 선택할 수 없는 것이죠..

이 방법을 모든 노드 V에 적용하면 노드마다 E번의 갱신이 일어나고 O(VE)의 시간에 최대 갯수를 구할 수 있습니다만... 하지만 이문제에는 노드와 간선수가 엄청크기 때문에 O(VE)로 제출했더니 TLE를 받았습니다.

 

그래서 hopcroft-karp알고리즘을 사용했는데 이건 자세히 설명하면 복잡해서 그냥 랭크란 개념으로 이분매칭을 최적화 하였다고 생각 하시면 됩니다.

hopcroft-karp의 시간복잡도는 O(sqrt(V)E)라서 계산을 해보면 얼추 시간안에 들어옴을 알 수 있습니다(호프크로프트는 실제 O(sqrt(V)E)보다도 평균적으로 빠르다고 알고있습니다,네트워크 그래프가 다 그렇다고 알고있어요)

 

소스코드1

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;
int n;
vector<int> adj[400005];
int B[400005];
bool vis[400005];
bool used[400005];
int level[400005];

void bfs(){
    queue<int> q;
    for(int i=0;i<n;i++){
        if(!used[i]){
            q.push(i);
            level[i] = 0;
        } else level[i] = INF;
    }
    while(!q.empty()){
        int& now = q.front();
        for(auto& i:adj[now]){
            if(B[i]!=-1&&level[B[i]]==INF){
                level[B[i]] = level[now]+1;
                q.push(B[i]);
            }
        }
        q.pop();
    }
}
bool Bipartite(int idx){
    for(auto& i : adj[idx]){
        if(B[i]==-1||level[B[i]]==level[idx]+1&&Bipartite(B[i])){
            used[idx] = 1;
            B[i] =idx;
            return true;
        }
    }
    return false;
}
int hopcroft(){
    memset(B,-1,sizeof(B));
    int total = 0;
    while(1){
        bfs();
        int argumentPath = 0;
        for(int i=0;i<n;i++){
            if(!used[i]&&Bipartite(i)) argumentPath++;
        }
        if(argumentPath==0) break;
        total+=argumentPath;
    }
    return total;
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i=0;i<n;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        adj[i].push_back(a);
        adj[i].push_back(b);
    }
    cout << hopcroft();
    return 0;
}

 

C. Too Heavy

문제

1번부터 N번까지의 사람들과 1번부터 N번까지의 짐이 있습니다.

각각 사람들의 무게와 짐들의 무게 그리고 각각의 사람들이 현재 가지고 있는 짐의 번호가 주어졌을때 아래 규칙을 통해 최종적으로 모든사람이 자신의 가방(k번사람이 k번째가방)을 가져가기를 원합니다.

원하는 결과를 얻기 위한 규칙을 적용하는 대상을 최소회수로 출력하고, 혹은 최종적으로 모든 사람이 자신의 가방을 가질 수 없으면 -1을 출력하는 문제입니다

 

규칙은 다음과 같습니다

- 사람 i와 j를 골라 두사람이 현재 가지고 있는 짐을 바꿉니다.

- 만약 자신의 무게 보다 더 크거나 같은 무게의 짐을 들게 되면 더 이상 그 사람은 짐을 교환하지 못합니다.

 

풀이1

사람의 무게 순으로 오름차순 정렬하면 해결 할 수 있습니다.

먼저 오름차순으로 정렬을 하고 앞에서 부터 읽어 나간다고 합시다. 현재 i번째로 작은 무게의 사람이전까지 모두가 자신의 가방을 가지고 있다라고 하면 i번째가 원하는 짐은 i번째~n번째 사람중에 갖고 있을것이고, 해당짐을 가지고온뒤 그사람에게 자신의 짐을 건넵니다.

i번째 사람은 본인의 짐을 찾았기 때문에 더이상 건들 필요가 없게되고 i번째사람이 들고있던 짐은 i가 들 수 있기때문에 i뒤에 오는 모든 사람들은 다 들 수 있습니다.

따라서 i번째 사람까지 모두 원하는 짐을 찾게 되고 이를 반복적으로 수행하면 끝까지 모두 자신이 원하는 가방을 취하게 됩니다.

대신 이 그리디스러운 알고리즘은 모든 사람이 자신보다 가벼운 짐을 들고 있다는 전제 하에 적용이 됩니다. 따라서 짐을 옮겨야 하는데 못옮기는 경우가 발생하면 어떤 수를 쓰더라도 최종적으로 올바르게 배치되지 않기 때문에 -1을 출력후 바로 종료해 주면 됩니다.

소스코드1

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
int person[200005];
int bag[200005];
int now[200005]; //person -> bag
int temp[200005]; //bag -> person

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    vector<pair<int,int>> v;
    for(int i=0;i<n;i++){
        cin >> person[i];
        v.push_back({person[i],i});
    }
    for(int i=0;i<n;i++){
        cin >> bag[i];
    }
    for(int i=0;i<n;i++){
        cin >> now[i];
        now[i]--;
        temp[now[i]] = i;
    }
    sort(v.begin(),v.end());
    vector<pair<int,int>> ans;
    for(auto& i : v){
        int& weight = i.first;
        int& idx = i.second;
        if(now[idx]==idx) continue;

        int dest = temp[idx];
        if(person[idx]<=bag[now[idx]]||person[dest]<=bag[now[dest]]){
            cout << -1;
            return 0;
        }
        ans.push_back({idx,dest});
        temp[now[idx]] = dest;
        temp[idx] = idx;
        swap(now[idx],now[dest]);
    }
    cout << ans.size() << '\n';
    for(auto& i : ans){
        cout << i.first+1 << " " << i.second+1 << '\n';
    }
    return 0;
}

D. Orientation

문제

풀이1

소스코드1