선린 가을맞이 알고리즘 챌린지 Solution

안녕하세요 선린인터넷고등학교 정보보호과 2학년으로 재학중인 김채완입니다.

선린 가을맞이 알고리즘 챌린지의 문제 중 제가 출제한 것은  E, F, G, J이며 이 문제들의 풀이를 작성하려합니다. 

---

E. 구름 다리 2

Tag : Greedy

 

인접한 것들은 서로 다른 색을 칠할 때 사전순으로 가장 앞서는 색 조합을 구하는 문제이다.

번호가 작은 것부터 가능한 가장 작은 수를 배치하는 것이 항상 최적이다.

 

현재 정점을 \(X\)라 하면 \(X\)와 인접한 것들 중 \(X\)보다 작은 것들만 고려한 \(mex\)를 구하면된다. 

\(mex\)는 주어진 집합에 속하지 않는 가장 작은 음이 아닌 정수를 의미한다.

 

이 문제에서는 색이 1부터 시작하는 점을 주의해야한다.

 

시간복잡도 : \(O((N + M)logM)\)

 

전체 코드

#include "bits/stdc++.h"
#define all(x) ((x).begin()), ((x).end())

using namespace std;
using ll = long long;

int N, M;
vector<int> g[101010];
int color[101010];
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin >> N >> M;
    for(int i=1; i<=M; i++){
        int x, y; cin >> x >> y;
        if(x > y) swap(x,y);
        g[y].push_back(x);
    }
    for(int i=1; i<=N; i++){
        set<int> st;
        for(auto &j : g[i]){
            if(color[j]) st.insert(color[j]);
        }
        int mex = 1;
        while(st.size()){
            if(*st.begin() == mex){
                st.erase(mex);
                mex++;
            } else break;
        }
        color[i] = mex;
    }
    for(int i=1; i<=N; i++) cout << color[i] << ' ';
}

---

F. 성인 게임

Tag : combinatorics, dp

 

\(1 \times 1\)과 \(2 \times 1\) 타일로 다음과 같이 구성된 타일을 채우는 경우의 수를 구하는 문제이다.

\(dp\)풀이를 의도하고 출제한 문제이며 \(f\)의 정의는 우측 상단 또는 좌측 하단을 채우는 경우의 수, 

\(g\)의 정의는 오른쪽 위를 향하는 대각선 두칸을 채우는 경우의 수이다. 

 

잘 정리하면 \(f(n) = 5f(n-1) - 2f(n-2)\)를 얻을 수 있다. 

 

+행렬 멱법을 사용한 \(O(logN)\) 풀이가 존재한다.

 

시간복잡도 : \(O(N)\)

 

전체 코드 

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

ll D[1010101][2];
const ll MOD = 1e9 + 7;

void init(){
    D[0][0] = 1;
    D[1][0] = 1;
    D[0][1] = 1;
    D[1][1] = 3;
    for(int i=2; i<=1000010; i++){
        D[i][0] = ((D[i-1][1] + D[i-2][1] * 2 % MOD) % MOD + D[i-1][0] * 2 % MOD) % MOD;
        D[i][1] = (D[i-1][1] * 2 % MOD + D[i][0]) % MOD;
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
 
    init();
    int tc = 1; cin >> tc;
    while(tc--){
        int N; cin >> N;
        cout << D[N+1][0] << endl;
    }
}

---

G. 비트코인은 신이고 나는 무적이다

Tag : knapsack dp

 

\(N\)개의 자연수를 받고 이 중 중복을 허용한 \(M\)개를 선택해 bitwise xor할 때 이 값의 최대를 구하는 문제이다.

냅색을 사용하면 된다. 

\(dp[i][j] = i\)개를 골라 \(j\)를 만들 수 있는지 여부

 

시간복잡도 : \(O(1024 \times NM) \)

 

전체 코드

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

int N, M;
int v[1010];
int dp[1010][2020];
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin >> N >> M;
    for(int i=1; i<=N; i++){
        cin >> v[i]; v[i]=abs(v[i]);
        dp[1][v[i]] = 1;
    }
    for(int i=2; i<=M; i++)
        for(int j=1; j<=N; j++)
            for(int k=0; k<1024; k++)
                dp[i][k^v[j]] |= dp[i-1][k];
    for(int i=1023; i>=0; i--){
        if(dp[M][i]) {
            cout << i << "\n";
            return 0;
        }
    }
}

---

J. 최대공약수가 뭔데

Tag : Möbius function, Combinatorics

 

\(gcd\)가 1이 되는 수열을 만들 수 있는 경우의 수를 구하는 문제다.

수열에서의 \(gcd\)의 정의는 문제에 설명해두었다. 

"\(f(x) = x\)의 배수로 수열을 만드는 경우의 수" 라고 정의 할때

 

답은 \(f(1) - f(2) - f(3) ..... + f(6) + f(10) .... \) 가 된다. 

답을 f(x)들의 합으로 나타낸다면 x가 제곱수를 인수로 가진다면 f(x)는 답에 포함되지 않으며 

소인수가 홀수개인 것은 -f(x), 짝수개인 것은 +f(x)만큼 더해진다는 것을 포함배제의 원리로 이해할 수 있다.

이는 뫼비우스 함수의 정의와 일치하기 때문에 뫼비우스 함수를 구현함으로써 해결할 수 있다.

 

+ 그냥 포함배제 하는 방법도 있다.

 

시간복잡도 : \(O(10^6 + 10^6 log 10^6) \)

 

전체 코드 

#include "bits/stdc++.h"
#define all(x) ((x).begin()), ((x).end())

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
ll factorial[1010101], inverse[1010101];
ll  mu[1010101];
bool isPrime[1010101];
vector<ll> prime;

ll fpow(ll a, ll m) {
    if (m == 0) return 1ll;
    ll next = fpow(a, m / 2);
    next = next * next % mod;
    if (m % 2) return next * a % mod;
    else return next;
}

ll nCr(int n, int k) { 
    if(n < k) return 0;
    return (factorial[n] * inverse[n - k] % mod) * inverse[k] % mod; 
}

void init(){
    factorial[0] = 1;
    for (int i = 1; i <= 1000000ll; i++) factorial[i] = factorial[i - 1] * i % mod;
    inverse[1000000] = fpow(factorial[1000000], mod - 2);
    for (int i = 999999; i >= 0; i--) inverse[i] = inverse[i + 1] * (i + 1) % mod;
    fill(isPrime, isPrime+1000000+1, true);
    fill(mu, mu+1000000+1, -1);
    mu[1] = 1;
    for(ll i=2;i<=1000000ll;i++)
    {
        if(isPrime[i]) prime.push_back(i);
        for(ll& p : prime) {
            if(i*p > 1000000ll) break;
            isPrime[i*p] = false;
            if(i%p == 0) {
                mu[i*p] = 0;
                break;
            }
            mu[i*p] = mu[i]*mu[p];
        }
    }
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    init();
    ll N, K; cin >> N >> K;
    vector<int> cnt(1010101);
    for(int i=1; i<=N; i++) {
        ll x; cin >> x;
        cnt[x]++;
    }
    ll ans = 0;
    for(int i=1; i<=1000000ll; i++){
        ll c = 0;
        for(int j=i; j<=1000000ll; j+=i) c += cnt[j];
        ll t = mu[i] * nCr(c, K) % mod;
        ans = (ans + t) % mod;
        ans = (ans + mod) % mod;
        assert(ans >= 0);
    }
    cout << ans << endl;
}