선린 가을맞이 알고리즘 챌린지 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;
}