후기

  • 더도 말고 덜도 말고 딱 오늘 시험만 같으면 좋겠다.
  • 이번 virtual participation에서는 2100점 받았다.
  • 이정도면 아마 떨어지지는 않을것 같다 ㅎㅎ

사진

A. Good ol’ Numbers Coloring

문제 링크

  • 빨리 풀어보려했으나 그냥 생각이 좀 필요했던 문제였다.
  • 이 문제는 두 수의 최대 공약수가 1이라면 FINITE를 출력하도록 하면 되는 문제이다.
#include <cstdio>
#include <algorithm>
using namespace std;
int t, a, b;
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &a, &b);
        int m = min(a, b), infinite = 0;
        for(int i = 2; i <= m; i++){
            if(a % i == 0 && b % i == 0){
                infinite = 1;
                break;
            }
        }
        if(infinite)printf("Infinite\n");
        else printf("Finite\n");
    } }

B. Restricted RPS

문제 링크

  • dp로 접근하면 좋겠다 생각을 해서 dp[rock][scissors][paper]로 해서 풀었다.
  • 묵, 찌, 빠 순으로 들어오는 줄 알고 코드짰는데 처음에 주어지는 값이 rock-paper-scissors였다….
  • 복사 두번 붙여넣기 해서 compile error한번 나고 묵찌빠 순 잘못해서 submission 하나 날렸다…ㅎㅎ 바보다…
  • 각 상황별로 가장좋았던 경우를 ans에 저장해서 출력해줬다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t, dp[101][101][101], ans[101][101][101], n, arr[3];
char s[101];

int find(int r, int c, int p, int t){
    if(t == n)return 0;
    int &ret = dp[r][c][p];
    if(ret != -1)return ret;
    int t1 = -1, t2 = -1, t3 = -1;
    if(r != 0)t1 = find(r - 1, c, p, t + 1);
    if(c != 0)t2 = find(r, c - 1, p, t + 1);
    if(p != 0)t3 = find(r, c, p - 1, t + 1);

    if(s[t] == 'R' && t3 != - 1)t3++;
    else if(s[t] == 'S' && t1 != - 1)t1++;
    else if(s[t] == 'P' && t2 != - 1)t2++;
    if(t1 >= t2 && t1 >= t3)ans[r][c][p] = 0;
    else if(t2 >= t1 && t2 >= t3)ans[r][c][p] = 1;
    else if(t3 >= t1 && t3 >= t2)ans[r][c][p] = 2;
    return ret = max(t1, max(t2, t3));
}

void check(int x, int y, int z, int t){
    if(t == n)return;
    int &ret = ans[x][y][z];
    if(ret == 0){
        printf("R");
        check(x - 1, y, z, t + 1);
    }
    else if(ret == 1){
        printf("S");
        check(x, y - 1, z, t + 1);
    }
    else if(ret == 2){
        printf("P");
        check(x, y, z - 1, t + 1);
    }
}

int main(){
    scanf("%d", &t);
    while(t--){
        memset(dp, -1, sizeof(dp));
        memset(ans, -1, sizeof(ans));
        scanf("%d %d %d %d %s", &n, &arr[0], &arr[2], &arr[1], s);
        int cnt = find(arr[0], arr[1], arr[2], 0);
        int x = n % 2 ? n / 2 + 1 : n / 2;
        if(cnt >= x){
            printf("YES\n");
            check(arr[0], arr[1], arr[2], 0);
            printf("\n");
        }
        else printf("NO\n");

    }
}

C. Constanze’s Machine

  • 이 문제도 dp인데 쉬운 dp 같아 보였다.
  • n이나 u인데 바로 전 값이 같은 애면 dp[i - 1] + dp[i - 2]로 해주고 다른 경우는 그냥 dp[i - 1]로 해준다.
  • 헷갈리는게 예외케이스가 있었다. m, w가 있으면 inscribe이 불가능하기 때문에 0으로 해줘야한다.
  • 나는 0번 위치에 m이나 w가 있으면 처리가 되게 해주는거 안해줘서 submission낭비를 또했다.
#include <cstdio>
char s[100001];
long long dp[100001], n, valid = 1;
int main(){
    scanf("%s", s);
    if(s[0] == 'm' || s[0] == 'w')valid = 0;
    dp[0] = 1, dp[1] = 1;
    for(int i = 2; s[i - 1] != '\0'; i++){
        if(s[i - 1] == 'u' && s[i - 2] == 'u')dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        else if(s[i - 1] == 'n' && s[i - 2] == 'n')dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        else dp[i] = dp[i - 1];
        n = i;
        if(s[i - 1] == 'm' || s[i - 1] == 'w'){
            valid = 0;
            break;
        }
    }
    if(valid)printf("%lld", dp[n]);
    else printf("0");
}

D. Shichikuji and Power Grid

  • editorial을 참고하다가 prims로 접근할 수 있다는 말을 듣고 방법이 하나 떠올랐다.
  • 0번을 새로 만들어서 power plant를 짓는비용을 0번에서 부터의 비용으로 치자.
  • 위의 0번부터의 비용을 priority queue에 다 넣어주고
  • 빌때까지 top을 구하고 새로운 위치에서 connection을 만드는 비용도 pq에 넣어준다.
  • top으로 나온 위치는 다시 가지 못하도록 visited를 1로 바꿔준다.
  • 이 때 top에 들어온 값의 시작점이 0이라면 plant가 된 애들이므로 해당하는 vector에 넣어주고
  • 아닌 경우는 시작점과 전달된 위치의 index를 담는 vector에 넣어준다.
  • 그리고 출력..! 그럼 끝이다!!! 이문제를 이렇게 풀어내다니… 만족스럽다.
#include <cstdio>
#include <vector>
#include <queue>
#define ll long long
#define pii pair<ll, ll>
#define pip pair<ll, pii>
using namespace std;
ll ans, n, x[2001], y[2001], c[2001], k[2001], visited[2001];
vector<pii> elist;
vector<ll> clist;
int main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)scanf("%lld %lld", &x[i], &y[i]);
    for(int i = 1; i <= n; i++)scanf("%lld", &c[i]);
    for(int i = 1; i <= n; i++)scanf("%lld", &k[i]);
    priority_queue<pip> pq;
    for(int i = 1; i <= n; i++)pq.push(pip(-c[i], pii(0, i)));
    while(!pq.empty()){
        pip top = pq.top(); pq.pop();
        long long cur = top.second.second;
        if(visited[cur])continue;
        visited[cur] = 1;
        if(top.second.first == 0)clist.push_back(cur);
        else elist.push_back(pii(top.second.first, cur));
        ans += -top.first;
        for(int i = 1; i <= n; i++){
            if(cur == i || visited[i])continue;
            long long d = abs(x[cur] - x[i]) + abs(y[cur] - y[i]);
            pq.push(pip(-d * (k[cur] +k[i]), pii(cur, i)));
        }
    }
    printf("%lld\n", ans);
    printf("%lu\n", clist.size());
    for(int i = 0; i < clist.size(); i++)printf("%lld ", clist[i]);
    printf("\n%lu\n", elist.size());
    for(int i = 0; i < elist.size(); i++)printf("%lld %lld\n", elist[i].first, elist[i].second);
}

느낀점

  • d를 풀면 진짜 이건 완벽한데 거기는 좀 힘들 것 같았다.
  • 내일 시험은 여기서 submission만 좀 덜하고 빨리 풀 수 있으면 좋겠다 ㅎㅎ