2024 SCPC 예선 1차 합격 후기

대회가 평일 부터 주말 사이에 열려서 일과시간 끝나고 잠깐 짬내서 3문제 풀고 나머지는 실력 부족으로 긁기만 하고 도망갔습니다. 1차도 제대로 못 푸는데 2차는 당연히 떨어질 것 같지만 전역하고 제대로 해보기 위해서 참가에 의의를 두고자 합니다!

 

A. A보다 B가 좋아

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    FASTIO;
	
	int t; cin >> t;
	for (int k = 1; k <= t; k++){
	    cout << "Case #" << k << '\n';
	    int n; cin >> n;
	    string s; cin >> s;
	    vector<int> v;
	    for (int i = 0; i < s.size(); i++){
	        if(s[i] == 'A') v.push_back(i);
	    }
	    
	    int res = 0;
	    for (int i = 1; i < v.size(); i++){
	        int cnt = v[i] - v[i - 1];
	        if (cnt <= 2) res += 3 - cnt;
	    }
	    cout << res << '\n';
	}
	return 0;
}

 

A의 인덱스를 넣고 차이가 2보다 작은 것들을 2 - cnt해서 다 더했습니다.

 

B. 배달

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

#define ll long long
const int MAXN = 300005;
ll arr[MAXN];

int main(){
    FASTIO;
	
	ll t; cin >> t;
	for (ll k = 1; k <= t; k++){
	    cout << "Case #" << k << endl;
	    ll n; cin >> n;
	    for (ll i = 0; i < n; i++) cin >> arr[i];
	    sort(arr, arr + n);
	    
	    ll res = 0;
	    for (int i = 0; i < n / 4; i++){
	        ll diff = n / 4;
	        ll a = arr[i];
	        ll b = arr[i + diff];
	        ll c = arr[i + 2 * diff];
	        ll d = arr[i + 3 * diff];
	        res += abs(d - c) + abs(c - b) + abs(b - a) + abs(a - d);
	    }
	    cout << res << endl;
	}
	return 0;
}

 

정렬을 하고 n / 4를 기준으로 뛰어 넘어가면서 수행합니다. 

 

C. 보안망 점검

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

#define ll long long
const int MAXN = 300005;
vector<ll> v[MAXN];
ll visited[MAXN];

void bfs(ll s, ll e){
    queue<ll> q;
    q.push(s);
    visited[s] = 1;
    
    while(!q.empty()){
        ll cur = q.front();
        q.pop();
        if (cur == 0) break;
        
        for (ll i = 0; i < v[cur].size(); i++){
            ll next = v[cur][i];
            if (!visited[next]) {
                q.push(next);
                visited[next] = visited[cur] + 1;
            }
        }
    }
}

int main(){
    FASTIO;
	
	ll t; cin >> t;
	for (ll k = 1; k <= t; k++){
	    cout << "Case #" << k << endl;
	    ll n; cin >> n;
	    for (ll i = 1; i <= n; i++) v[i].clear();
	    memset(visited, false, sizeof(visited));
	    
	    for (ll i = 0; i < n + 1; i++){
	        ll x, y;
	        cin >> x >> y;
	        v[x].push_back(y);
	        v[y].push_back(x);
	    }
	    
	    ll s = 0, e = 0;
	    for (ll i = 1; i <= n; i++){
	        if (v[i].size() == 3){
	            if (s == 0) s = i;
	            else e = i;
	        }
	    }
	    
	    for (ll i = 0; i < v[s].size(); i++)
	        if (v[s][i] == e){
	            v[s].erase(v[s].begin() + i);
	            break;
	        }
	    for (ll i = 0; i < v[e].size(); i++)
	        if (v[e][i] == s){
	            v[e].erase(v[e].begin() + i);
	            break;
	        }
	    bfs(s, e);
	    ll d = visited[e] - 1;
	    if (d < 2) cout << (n - d) * (n - d - 1) / 2 << endl;
	    else if (n - d < 2) cout << d * (d - 1) / 2 << endl;
	    else cout << d * (d - 1) / 2 + (n - d) * (n - d - 1) / 2 << endl;
	}
	return 0;
}

 

간선이 3개인 두 점을 찾고 두 점을 잇는 간선을 지운 후에 최단거리로 s에서 e로 이어지는 거리를 구합니다. 답은 dC2 + (n - d)C2입니다. 문제를 읽으면 직관적으로 보이긴 하는데 삽질을 많이했던 것 같습니다..

 

D번 백트래킹으로 Task1 긁었고 E번은 map에 넣는 식으로 Task1 긁었습니다.