AtCoder ABC 266 풀이

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

Tasks - AtCoder Beginner Contest 266

 

A.

중간 글자를 출력하면 됩니다. 

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string s; cin >> s;
    cout << s[s.size()/2];
}

 

 

B. 

우선 N이 p로 나눠진다면 답은 0입니다. 

이제 4경우로 나눠줍니다. 

1) N>p인 경우 답은 N%p 입니다. 

2) 0<N<p인 경우 답은 p-N입니다.

3)-p<N<0인 경우 답은 p+N입니다.

4) N<-p인 경우 답은 N-N%p입니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    ll n; cin >> n;
    if (n % mod == 0) {
        cout << 0;
    }
    else if (n >= mod) {
        cout << n % mod;
    }
    else if (n > 0 && n < mod) {
        cout << mod - n;
    }
    else if (n <= 0 && n >= -mod) {
        cout << mod + n;
    }
    else if (n < -mod) {
        n *= -1;
        cout << mod - (n % mod);
    }
}

 

 

C. 

네 점을 줄때 볼록사각형인지 출력하는 문제입니다. 

4개의 CCW가 같은 부호면 됩니다. 세 점 일직선등 엣지케이스가 없어 쉬운 문제입니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define x first
#define y second

int ccw(pll a, pll b, pll c) {
    ll t = (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
    return (t > 0) - (t < 0);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    pll a, b, c, d;
    cin >> a.x >> a.y;
    cin >> b.x >> b.y;
    cin >> c.x >> c.y;
    cin >> d.x >> d.y;
    int mul = 1;
    mul *= ccw(a, b, c);
    mul *= ccw(b, c, d);
    mul *= ccw(c, d, a);
    mul *= ccw(d, a, b);
    cout << (mul == 1 ? "Yes" : "No");
}

 

 

 

D. 

dp[x][t]를 위치 x에 시간 t에 오는 경우 최댓값이라 정의합니다.

전이는 t-1에서 옵니다. 또한 x는 {x-1,x,x+1}에서 올 수 있습니다. 최대 1의 속도이므로 움직이지 않아도 

되는것에 유의합니다. 또한 dp[x][t]에서 점수 획득이 가능하다면 그 점수를 더해주면서 갱신하면 됩니다. 

dp[x][t]=max(dp[x-1][t-1], dp[x][t-1], dp[x+1][t-1])+C[x][t]가 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, T;
ll dp[5][100005], c[5][100005];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ll t, x, v;
        cin >> t >> x >> v;
        c[x][t] = v;
        if (i == n) T = t;
    }
    fill(&dp[0][0], &dp[4][T], -1e18);
    dp[0][0] = 0;
    for (int t = 1; t <= T; t++) {
        for (int x = 0; x < 5; x++) {
            dp[x][t] = dp[x][t - 1];
            if (x < 4) dp[x][t] = max(dp[x][t], dp[x + 1][t - 1]);
            if (x > 0) dp[x][t] = max(dp[x][t], dp[x - 1][t - 1]);
            dp[x][t] += c[x][t];
        }
    }
    ll ans = 0;
    for (int x = 0; x < 5; x++) {
        ans = max(ans, dp[x][T]);
    }
    cout << ans;
}

 

 

 

E.

dp[n]을 n번째 던질 때 점수의 기댓값이라 정의합니다. 

언제든 게임을 그만둘 수 있으므로, dp[n]보다 작은 값이 주사위에서 나오면 그만하면 됩니다.

따라서 매번 기댓값을 키울 수 있습니다. 

dp[n]=1/6*sigma(max(i,dp[n-1])) 임을 쉽게 알 수 있습니다. 

 

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;  cin >> n;
    vector<double> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 6; j++) {
            dp[i] += max(double(j), dp[i - 1]) / 6;
        }
    }
    cout<<fixed;
    cout.precision(8);
    cout << dp[n];
}

 

 

 

F. 

N개의 점에 N개의 변이 있습니다. 이러한 그래프는 트리에서 선분 1개를 추가하여 사이클이 만들어집니다. 

경로가 유일하려면 두 점이 모두 사이클에 도함되지 않으면 됩니다.  다만 예외적으로 사이클에 포함되는 점과

인접한 정점쌍까지는 가능합니다. 위상정렬을 하는 과정에서 사이클에 포함된 점들은 큐에 들어갈 수 없습니다.

따라서 위상정렬을 하면서 유니온파인드를 하고, 인접차수가 1이 된다면(양방향이므로 1일때 큐에 넣어야 함)

큐에 넣고 돌려주면 됩니다. 위상정렬에서 사이클을 찾을 때 성질을 사용하는 어려운 문제였습니다.

 

#include<bits/stdc++.h>
using namespace std;
int n, u, v, q, x, y;
vector<int>g[200005];
int par[200005], ind[200005];

int find(int x) {
    return !~par[x] ? x : par[x] = find(par[x]);
}

void uni(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) par[y] = x;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> u >> v;
        ind[u]++, ind[v]++;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(par, -1, sizeof(par));
    queue<int>que;
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 1) que.push(i);
    }
    while (que.size()) {
        int cur = que.front(); que.pop();
        for (int nxt : g[cur]) {
            if (--ind[nxt] == 1)que.push(nxt);
            uni(cur, nxt);
        }
    }
    cin >> q;
    while (q--) {
        cin >> x >> y;
        cout << (find(x) == find(y) ? "Yes" : "No") << '\n';
    }
}

 

 

 

G. 

아이디어성 문제입니다. R과 RG와 B를 먼저 칠한다고 가정합니다. 

그럼 R을 r-k개, RG를 k개, B를 b개 배치하는 경우의 수는 (r+b)!/(r-k)!k!b! 입니다. 

이제 G를 끼워넣어봅시다. 배치한 곳의 오른쪽에만 공간이 있다고 가정합니다. 

그럼 G는 R만 배치한 곳의 오른쪽에만 배치할 수 없고 나머지 공간에는 모두 배치할 수 있습니다. 

또한 미리 배치한 곳의 맨 앞에도 공간을 만들어 줍시다. (G가 맨앞에 배치되는 경우)

공간이 총 b+k+1개가 생깁니다. b+k+1개 공간에 중복을 허락하여 g-k개를 채우는 경우의 수는 

(b+k+1) H (g-k) = (b+g) C (g-k) 가 됩니다. 위와 곱해서 계산해주면 됩니다. 

곱하기 전에 식을 깔끔히 정리하면, gCk * b+gCg * b+rCr-k 가 됩니다.

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAX = 1000011, mod= 998244353;
ll r, g, b, k, fac[2*MAX];

void make_table() {
    fac[0] = 1;
    fac[1] = 1;
    for (int i = 2; i < 2 * MAX; 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 /= 2;
    }
    return ret;
}

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> r >> g >> b >> k;
    make_table();

    ll c1 = fac[g];
    c1 = (c1 * inv(fac[k])) % mod;
    c1 = (c1 * inv(fac[g - k])) % mod;

    ll c2 = fac[b + g];
    c2 = (c2 * inv(fac[b])) % mod;
    c2 = (c2 * inv(fac[g])) % mod;

    ll c3 = fac[b + r];
    c3 = (c3 * inv(fac[r - k])) % mod;
    c3 = (c3 * inv(fac[b + k])) % mod;

    ll ans = c1;
    ans = (ans * c2) % mod;
    ans = (ans * c3) % mod;

    cout << ans;
}