SUAPC 연습

2월 11일 문제풀이

2023 겨울 SUPAC 나가려고 연습했떤 문제 해설을 적어보았따. 이제는 노션을 이용하여 markdown을 만드려고 하기 때문에 형태가 조금은 변할 수 있다. 노션에서 markdown언어로 변환하는 프로그램을 만들면 좋겠다고 생각했는데 그냥 노션 그자체에 있을 줄은 몰랐다…. 어쨋든 그래서 2023 겨울 대회는 5솔인가? 4솔인가 하고 학교 2등상, 전체 16등인가? 15등인가 했다….ㅋㅋㅋ 사실 내가 잘했어야 했는데 m번에서 엄청 말려서 망했다. 그리고 게임dp 연습했던거라 충분히 풀수 있었는데 그것마저 실패한게 너무 아쉬웠따.

A. 튜터-튜티 관계의 수

dfs로 연결되어 있는 정점들을 모두 곱하면 답이다

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
#define xx first
#define yy second

const int MAX = 2e5+1;
const int MOD = 1e9+7;
int n, m;
vector<int> adj[MAX];
ll dp[MAX][2];
bool visited[MAX];

int dfs(ll here){
    visited[here] = true;
    int ret = 1;
    for(ll next : adj[here]){
        if(!visited[next]){
            ret += dfs(next);
        }
    }
    return ret;
}

int main(){
    fast_io
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ll res = 1;
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            res *= dfs(i);
            res %= MOD;
        }
    }
    cout << res;
}

C. 카카오뷰 큐레이팅 효용성 분석

단순 구현

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
#define xx first
#define yy second

int main(){
    fast_io
    int n; cin >> n;
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    ll sum= 0, res = 0;
    for(int i=0;i<n;i++){
        sum += a[i];
        if(!b[i]) res += a[i];
    }
    cout << sum << '\n';
    cout << res << '\n';
}

D. Y

Y를 만드려면 각 정점에서 뻗어나가서 끝까지 가는거의 길이들을 알아둬야한다.

E. 도로 정보

상태를 27(T가 나온횟수%3)+9(G가 나온횟수%3)+3*(F가 나온횟수%3)+(P가나온횟수%3)으로 나타내면

i에서의 상태와 j에서의 상태가 같다면 i+1~부터 j까지가 흥미로운 구간이다 라고 생각할 수 있다.

따라서 dp[81]에 (81이 모든 경우의 수임) 상태가 나오면 그 상태가 이전에 나온 만큼 정답에 더해주고

+1을 해준다.

1~n까지 보면 정답 처음꺼는 dp[0] = 1에서 시작한다.

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
#define xx first
#define yy second

const int MAX = 1e5+1;
int dp[81], state[MAX], T, G, F, P;

int main(){
    fast_io
    int n; cin >> n;
    string s; cin >> s;
    dp[0] = 1;
    ll res = 0;
    for(int i=0;i<s.size();i++){
        T += (s[i]=='T');
        G += (s[i]=='G');
        F += (s[i]=='F');
        P += (s[i]=='P');
        int k = 27*(T%3)+9*(G%3)+3*(F%3)+(P%3);
        res += dp[k];
        dp[k]++;
    }
    cout << res;
}

J. 일이 너무 많아..

11, 111 등을 약수로 하는 수를 포함배제 원리를 이용하여 구한다

import sys
import math
input = sys.stdin.readline

n = int(input())

def solve(X) :
    p = []
    k = 11
    while k <= X:
        p.append(k)
        k *= 10
        k += 1
    ret = 0
    sz = len(p) 
    for i in range(1, 1<<sz):
        L = 1
        cnt = -1
        for j in range (sz):
            if(i&(1<<j)) :
                cnt *= -1
                L = math.lcm(L, p[j])
                if(L>n) :
                    L = X+1
                    break
        ret += cnt*(X//L)
    return ret

print(solve(n))

K. 올바른 괄호

누적합을 이용하는데

ps[i] : (를 1, )를 -1이라고 했을 때 누적합

pn[i] : 처음부터 i까지 최솟값

sn[i] : 끝에서부터 i까지 최솟값

일단 ps[n]은 무조건 1또는 -1이다. 1이면 (를 빼야하고 , -1이면 )를 빼야한다.

근데 i자리에 있는 괄호를 빼고 싶으면 i의 앞은 0보다 커야하고, i의 뒤는 (를 빼면 1보다, )를 빼면 -1보다 커야한다.

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
#define xx first
#define yy second

int main(){
    fast_io
    string s; cin >> s;
    int n = s.size();
    vector<int> a(n+1), ps(n+1);
    for(int i=1;i<=n;i++){
        a[i] = (s[i-1]=='(') ? 1 : -1;
        ps[i] = ps[i-1]+a[i];
    }
    int res = 0;
    vector<int> pn(n+1), sn(n+1);
    pn[1] = ps[1];
    for(int i=2;i<=n;i++){
        pn[i] = min(pn[i-1], ps[i]);
    }
    sn[n] = ps[n];
    for(int i=n-1;i>0;i--){
        sn[i] = min(sn[i+1], ps[i]);
    }
    for(int i=1;i<=n;i++){
        if(ps[n]==1&&a[i]==1&&pn[i-1]>=0&&sn[i]==1) res++;
        if(ps[n]==-1&&a[i]==-1&&pn[i-1]>=0&&sn[i]==-1) res++;
    }
    cout << res;
}

L. 팰린드롬 게임

1의 자리는 무조건 팰린드롬 수 따라서 어떤 수가 있더라도 10의 배수를 만들 수 있다.

A의 차례에 10의 배수가 아닌 수가 있으면 무조건 10의 배수로 만들 수 있다.

10의 배수라면 다음 턴에 무조건 10의 배수가 아닌 수로밖에 못만든다. (팰린드롬 수는 마지막이 0일 수 없어서)

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
#define xx first
#define yy second

int main(){
    fast_io
    int tt; cin >> tt;
    while(tt--){
        ll n; cin >> n;
        if(!n||!(n%10)) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}