AtCoder ABC 262 풀이

https://atcoder.jp/contests/abc262/tasks

Tasks - AtCoder Beginner Contest 262

 

A.

나머지 분류후 적절히 4k+2꼴로 만들어주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    if (n % 4 == 0) {
        cout << n + 2;
    }
    if (n % 4 == 1) {
        cout << n + 1;
    }
    if (n % 4 == 2) {
        cout << n;
    }
    if (n % 4 == 3) {
        cout << n + 3;
    }
}

 

B.

n<=100이라 3중문으로 처리해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int n, m, u, v;
bool g[101][101];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    while (m--) {
        cin >> u >> v;
        g[u][v] = 1;
        g[v][u] = 1;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (g[i][j] && g[j][k] && g[k][i]) {
                    cnt++;
                }
            }
        }
    }
    cout << cnt;
}

 

 

C.

두 쌍은 a[i]=i & a[j]=j 또는 a[i]=j && a[j]=i 를 만족해야 합니다.

i<j이므로 2개가 중복되는 경우는 없습니다. a[i]=i인 i들을 모두 센 후에 그 중 2개를 뽑아주면 

첫번째 쌍을 셀 수 있습니다. 2번째 쌍은 a[i]=j , a[j]=i 는 a[a[i]]=i 와 같습니다. 또한 i<j는 i<a[i]와 같습니다. 

따라서 O(N)에 이것또한 갱신시킬 수 있습니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, a[500005], cnt[500005];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    ll ans = 0, cnt1 = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == i) {
            ans += cnt1++;
        }
        else if (a[i] > i && a[a[i]] == i) {
            ans++;
        }
    }
    cout << ans;
}

 

 

 

D.

딱봐도 dp입니다. 우선 n<=100입니다. 4중dp까진 가능합니다. 

우선 m개를 고른다고 고정합니다. 그럼 이제 a1~an 중 잘 뽑아서 m의 배수가 되면 됩니다. 

dp[i][j][k]를 i번째를 볼 것이고 지금까지  j개를 골랐고 그 합이 k인 것의 개수라고 정의합시다. 

i번을 안고른 경우 (i,j,k)는 (i+1,j,k)로 전이됩니다. 

i번을 고른 경우 (i, j, k)는 (i+1, j+1, (k+a[i])%m )으로 전이됩니다. 

답은 dp[n][m][0]들을 모두 더해주면 됩니다. 이걸 모든 m마다 해주면 시간은 O(N^4)이 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod= 998244353;
ll n, a[111], dp[111][111][111];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i];
    ll ans = 0;
    for (int m = 1; m <= n; m++) {
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k < m; k++) {
                    dp[i + 1][j][k] += dp[i][j][k];
                    dp[i + 1][j][k] %= mod;
                    dp[i + 1][j + 1][(k + a[i]) % m] += dp[i][j][k];
                    dp[i + 1][j + 1][(k + a[i]) % m] %= mod;
                }
            }
        }
        ans = (ans + dp[n][m][0]) % mod;
    }
    cout << ans;
}

 

 

E.

DAG가 아닌 일반적인 그래프에서 dp등의 갱신은 어려우므로 그래프의 자체의 성질에

주목하면 쉽게 풀 수 있습니다.  점과 선등의 카운팅 문제에선 차수가 특히 자주 쓰입니다. 

두 정점 색이 다른 선분이 짝수개있어야 합니다. 선분은 1색인 선분과 2색인 선분으로 나뉩니다. 

이 때, 2색 선분이 짝수개 있다면 R,B의 차수는 모두 짝수가 됩니다. 

따라서 R을 k개 골라줄 때, 차수의 합이 짝수가 되게 골라주면 됩니다. 

우선 차수가 홀수인 것의 개수를 세줍니다. 그 후 홀수개수에서 2i개를 고르고 나머지 k-2i개는 짝수

개수에서 골라주면 됩니다. 답은 sigma(oddC2i * evenCk-2i)가 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll n, m, k, u, v, ind[200005];
ll fac[200005];

void make_table() {
    fac[0] = 1;
    fac[1] = 1;
    for (ll i = 2; i <= n; i++) {
        fac[i] = (i * fac[i - 1]) % mod;
    }
}

ll Pow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

ll inv(ll x) {
    return Pow(x, mod - 2);
}

ll combin(ll n, ll k) {
    if (n < k) return 0;
    ll ret = fac[n];
    ret = (ret * inv(fac[k])) % mod;
    ret = (ret * inv(fac[n - k])) % mod;
    return ret;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    make_table();
    while (m--) {
        cin >> u >> v;
        ind[u]++;
        ind[v]++;
    }
    ll odd = 0;
    for (int i = 1; i <= n; i++) {
        if (ind[i] & 1) odd++;
    }
    ll even = n - odd;
    ll ans = 0;
    for (ll j = 0; 2ll * j <= k; j++) {
        ll mul = combin(odd, 2 * j);
        mul = (mul * combin(even, k - 2 * j)) % mod;
        ans = (ans + mul) % mod;
    }
    cout << ans;
}

 

 

F.

풀이 예정

 

G. 

풀이 예정