2023.04.20 주간 회고록

뜬금 없지만 갑자기 다시 PS에 대한 욕심이 생겼습니다. ICPC WF진행하는거 보니까 뭔가 다시 한번 제대로 해볼까 하는 생각도 들더라고요. 이 글에서는 이번 한 주 동안 풀었던 문제들을 정리하려고 합니다. 그 전에 최근에 세운 몇가지 목표들을 정리하겠습니다.

solved.ac class 1~7 all solve
Codeforces Purple (1900)
Atcoder Blue (1600)
BOJ 2000 solve

사실 뭔가 최종 목표라기 보단 어떤 목적을 이루는 과정에서 중간 체크포인트 느낌으로 세운 도전 과제라고 보는게 맞긴 하겠습니다. 결국 최종적인 목표는 대회에서 좋은 성적을 거두는거고 다른건 다 그걸 이루기 위한 연습이죠. 마침 이번에 UCPC에 같이 나가게 될 팀원들도 다 실력이 너무 뛰어난 분들이라 같이 잘해서 후회 없이 마치고 싶네요.

아래 정리된 문제들은 특정 순서로 정렬되어 있지 않습니다.

BOJ

/<20303> 할로윈의 양아치

한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다는 조건은 친구 관계인 모든 아이를 하나의 집합으로 묶어주면 된다는 뜻입니다. 따라서 유니온 파인드를 사용해 아이들을 묶어서 집합들의 크기와 사탕수의 합을 구한 후 $K$ 명 이상의 아이들이 울면 안된다는 조건을 만족하게 집합들을 고르는건 배낭 용량이 $K$ 인 냅색으로 해결 가능합니다.

int n, m, k; 
int arr[30005]; int par[30005]; int sz[30005];

int fnd(int node){
    if(par[node] == node) return node;
    else return par[node] = fnd(par[node]);
}

bool uni(int node1, int node2){
    // 2 -> 1
    int p1 = fnd(node1), p2 = fnd(node2);
    if(p1 == p2) return false;
    else{
        par[p2] = p1; sz[p1] += sz[p2];
        arr[p1] += arr[p2];
        return true;
    }
}

vector<pii>v; int dp[30005];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    cin >> n >> m >> k;

    for(int i=1; i<=n; i++){
        par[i] = i; sz[i] = 1;
        cin >> arr[i];
    }

    while(m--){
        int u, v;
        cin >> u >> v;
        uni(u, v);
    }

    for(int i=1; i<=n; i++){
        if(par[i] == i){
            v.push_back({sz[i], arr[i]});
        }
    }

    int ss = v.size();
    for(int i=0; i<ss; i++){
        for(int j=k-1; j>=1; j--){
            if(j-v[i].fr >= 0){
                dp[j] = max(dp[j], dp[j-v[i].fr]+v[i].sc);
            }
        }
    }
    cout << dp[k-1];
}

/<27172> 수 나누기 게임

최근에 알게된 사실이 있는데 $\frac{N}{1} + \frac{N}{2} + \dots + \frac{N}{N-1} + \frac{N}{N}$ 은 $\mathcal{O}(N log N)$ 정도라고 합니다. 출처 : Harmonic series - Wikipedia

Harmonic series (mathematics) - Wikipedia

From Wikipedia, the free encyclopedia Divergent sum of all positive unit fractions In mathematics, the harmonic series is the infinite series formed by summing all positive unit fractions: ∑ n = 1 ∞ 1 n = 1 + 1 2 + 1 3 + 1 4 + 1 5 + ⋯ . {\displaystyl

en.wikipedia.org

이 점을 사용해 수열의 원소들의 100만 이하인 배수를 전부 확인해주면서 답을 계산해도 시간안에 충분히 해결 가능합니다.

bool occur[1000005];
int ans[1000005];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    int n; cin >> n; vector<int>v(n);
    for(int i=0; i<n; i++){
        cin >> v[i]; occur[v[i]] = 1;
    }
    for(int &k:v){
        int it = k+k;
        while(it <= 1000000){
            if(occur[it]) {ans[it]--; ans[k]++;}
            it += k;
        }
    }
    for(int &k:v){
        cout << ans[k] << ' ';
    }
}

/<17404> RGB거리 2

RGB거리의 원형 버전... 이라고 생각하기 쉽지만 사실은 그냥 가능한 색의 조합이 얼마 안된다는 점을 사용해 $1$ 번 집과 $N$ 번 집의 색을 정해둔 후 그냥 RGB거리랑 동일하게 해결 가능합니다.

void init(ll arr[][3], int n){
    for(int i=0; i<n; i++){
        fill(arr[i], arr[i]+3, INF);
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    int n; cin >> n; ll cost[n][3];
    for(int i=0; i<n; i++) cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    vector<int>p = {0, 1, 2};
    ll mn = INF;
    do{
        ll dp[n][3]; init(dp, n);
        int c1 = p[0], cn = p[1];
        dp[0][c1] = cost[0][c1];
        for(int i=1; i<n; i++){
            if(i!=n-1){
                dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
                dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
                dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
            }
            else{
                for(int k=0; k<3; k++){
                    if(k!=cn) continue;
                    for(int j=0; j<3; j++){
                        if(j==k) continue;
                        dp[i][k] = min(dp[i][k], dp[i-1][j] + cost[i][k]);
                    }
                }
            }
        }
        mn = min(mn, min({dp[n-1][0], dp[n-1][1], dp[n-1][2]}));
    }while(next_permutation(p.begin(), p.end()));
    cout << mn;
}

/<2143> 두 배열의 합

누적합을 전처리 해둔 후 B의 모든 구간합으로 가능한 것들이 몇번 등장하는지 map같은 자료구조에 저장해둔 후 A의 모든 구간합이 B에서 몇번 등장했는지 전부 더해주면 됩니다.

ll T; int n, m;

map<ll, ll>mp;
ll a[1005], b[1005], prea[1005], preb[1005];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    cin >> T; 
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i]; prea[i] = prea[i-1] + a[i];
    }
    cin >> m;
    for(int i=1; i<=m; i++){
        cin >> b[i]; preb[i] = preb[i-1] + b[i];
    }

    for(int i=1; i<=m; i++){
        for(int j=i; j<=m; j++){
            if(mp.find(preb[j]-preb[i-1])==mp.end()){
                mp[preb[j]-preb[i-1]] = 1;
            }
            else{
                mp[preb[j]-preb[i-1]] += 1;
            }
        }
    }
    ll ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            if(mp.find(T-(prea[j]-prea[i-1]))!=mp.end()){
                ans += mp[T-(prea[j]-prea[i-1])];
            }
        }
    }
    cout << ans;
}

/<2342> Dance Dance Revolution

DP의 상태를 정의하는데 좀 어려움을 겪었던 문제입니다. 결론적으로는 단순히 $i$ 번째 패턴을 처리 할 때 왼쪽 발이 $l$ 위치에 있고 오른쪽 발이 $r$ 위치에 있다고 가정을 하면 상태를 $(i, l, r)$ 의 길이 3의 튜플로 생각 할 수 있게 됩니다.

그러면 상태 전이는 단순히 모든 가능한 $(i-1, l, r)$ 에서 $(i, l, r)$ 로의 전이를 보면 됩니다.

int f(int i, int j){
    if(i > j) swap(i, j);
    if(i==0) return 2;
    if(i==1 && j==4) return 3;
    else{
        return 2 + j - i;
    }
}

int dp[100005][5][5];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    vector<int>v;
    while(1){
        int tmp; cin >> tmp; if(!tmp) break;
        v.push_back(tmp);
    }
    int n = v.size(); // [i][l][r]
    for(int i=0; i<=n; i++){
        for(int j=0; j<5; j++){
            for(int k=0; k<5; k++){
                dp[i][j][k] = INF;
            }
        }
    }
    dp[0][0][0] = 0;
    dp[1][0][v[0]] = 2; dp[1][v[0]][0] = 2;
    for(int i=2; i<=n; i++){
        int curstep = v[i-1];
        // r
        for(int j=0; j<5; j++){
            for(int k=0; k<5; k++){
                if(j==k) continue;
                dp[i][j][curstep] = min(dp[i][j][curstep],
                dp[i-1][j][k] + 
                (k == curstep ? 1 : f(k, curstep)));
            }
        }
        // l
        for(int j=0; j<5; j++){
            for(int k=0; k<5; k++){
                if(j==k) continue;
                dp[i][curstep][j] = min(dp[i][curstep][j],
                dp[i-1][k][j] + 
                (k == curstep ? 1 : f(k, curstep)));
            }
        }
    }
    
    int ans = INF;
    for(int j=0; j<5; j++){
        for(int k=0; k<5; k++){
            ans = min(ans, dp[n][j][k]);
        }
    }
    cout << ans;
}

/<2473> 세 용액

set으로 비비려다가 망했습니다. 결국 이진 탐색 써서 $\mathcal{O}(N^{2} log N)$ 에 해결했습니다. 상수 차이가 이렇게 무섭군요. 투 포인터 풀이도 있고 이 풀이가 오히려 더 아름다우니 이쪽을 찾아보시는거도 좋겠습니다.

int n;
vector<ll> arr;
set<ll>s;

ll diff = LLINF; vector<ll>ans;

void upd(ll x, ll y, ll z){
    ll tmp = abs(x + y + z);
    if(tmp < diff){
        diff = tmp;
        ans = {x, y, z};
    }
}

void solve(ll x, ll y, vector<ll>& a){
    auto it = lower_bound(a.begin(), a.end(), -x-y);
    if(it!=a.end() && *it!=x && *it!=y){
        upd(x, y, *it);
    }
    if(it!=a.begin()){
        auto prv = it; prv--;
        if(*prv != x && *prv != y) upd(x, y, *prv);
    }
    if(it!=a.end()){
        auto nxt = it; nxt++;
        if(*nxt != x && *nxt != y) upd(x, y, *nxt);
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    cin >> n; arr.resize(n);
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            if(i == j) continue;
            solve(arr[i], arr[j], arr);
        }
    }
    sort(ans.begin(), ans.end());
    for(auto i:ans) cout << i << ' ';
}

/<16724> 피리 부는 사나이

문제 상황을 생각해보면 이렇게 어떤 칸에 위치한 사람은 그 칸에 적힌 방향을 따라가다가 어떤 사이클 안에 갇히게 되는데 이 사이클에 있는 칸 어떤걸 골라도 SAFE ZONE이 됩니다. 따라서 이 개수를 세주면 되고 이는 유니온 파인드로 쉽게 가능합니다 (이미 합쳐져 있지 않은 모든 정점을 적힌 방향으로 전부 합쳐준 후 부모 == 자신인 정점의 수).

int n, m;
char grid[1005][1005];
pii par[1005][1005];

pii fnd(pii node){
    if(par[node.fr][node.sc] == node) return node;
    else return par[node.fr][node.sc] = fnd(par[node.fr][node.sc]);
}

bool uni(pii node1, pii node2){
    // 2 -> 1
    pii p1 = fnd(node1), p2 = fnd(node2);
    if(p1 == p2) return false;
    else{par[p2.fr][p2.sc] = p1; return true;}
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> grid[i][j];
            par[i][j] = {i, j};
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            pii n1 = {i, j}, n2;
            if(grid[i][j]=='U'){
                n2 = {i-1, j};
            }
            if(grid[i][j]=='L'){
                n2 = {i, j-1};
            }
            if(grid[i][j]=='R'){
                n2 = {i, j+1};
            }
            if(grid[i][j]=='D'){
                n2 = {i+1, j};
            }
            uni(n1, n2);
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(fnd({i, j}) == make_pair(i, j)){
                ans++;
            }
        }
    }
    cout << ans;
}

/<7670> Game Dice

공평한 4, 6, 8, 10, 12, 또는 20면의 주사위가 $d (d \le 13)$ 개 주어졌을때 합이 $x$ 가 되게 하는 확률을 구하는 문제입니다. 냅색 느낌의 DP로 간단하게 해결 가능합니다. $dp[i][j]$ 를 $i$ 번째까지 굴렸을때 합이 $j$ 가 되는 경우의 수라고 하면 단순히 $i$ 번째 주사위의 각 주사위 면에 대해 $j$ 를 $1$ 에서 $260$ (이거 보다 큰 합은 못 나오니까) 까지 봐주면서 $j - k$ (주사위 면에 적힌 수) 가 $0$ 보다 크면 $dp[i][j]$ 에 $dp[i-1][j-k]$ 를 더해주면 됩니다.

최종 답은 모든 주사위의 면의 수를 곱한걸 $D$ 라고 했을 때 $\frac{dp[d][x]}{D}$ 가 됩니다.

while(1){
        int d; cin >> d;
        if(!d) return 0;
        vector<ll>v;
        ll den = 1;
        for(int i=0; i<d; i++){
            char dd; cin >> dd;
            ll f; cin >> f;
            v.push_back(f); den *= f;
        }
        ll x; cin >> x;
        if(x == 0 || x > 260) {
            cout << "0.00000\n";
            continue;
        }
        ll dp[d][261];
        for(int i=0; i<d; i++){
            fill(dp[i], dp[i]+261, 0);
        }
        for(int k=1; k<=v[0]; k++) dp[0][k] = 1;
        for(int i=1; i<d; i++){
            for(ll j=1; j<=260; j++){
                for(ll k=1; k<=v[i]; k++){
                    if(j-k > 0 && dp[i-1][j-k]){
                        dp[i][j] += dp[i-1][j-k];
                    }
                }
            }
        }
        ll num = dp[d-1][x];
        cout << (ld)num/den << endl;
    }

/<1029> Hiking

단순 격자 다익스트라 문제입니다.

int T;

int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[8] = {1, -1, 1, -1, -1, 1, 0, 0};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    cin >> T;
    while(T--){
        int n, m; cin >> n >> m;
        ll dist[n][m]; ll h[n][m];
        int fx = 0, fy = 0, fh = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                char tmp; cin >> tmp;
                if(tmp == '#') h[i][j] = -1;
                else{
                    h[i][j] = tmp - '0';
                    if(h[i][j] > fh){
                        fx = i; fy = j; fh = h[i][j];
                    }
                }
                // cout << h[i][j] << ' ';
                dist[i][j] = INF;
            }
            // cout << endl;
        }
        int x, y; cin >> x >> y;
        priority_queue< pair<ll, pii>, vector< pair<ll, pii> >, greater<pair<ll, pii>> >pq;
        dist[x][y] = 0;
        pq.push({0, {x, y}});
        while(!pq.empty()){
            ll cdst = pq.top().fr;
            int cx = pq.top().sc.fr, cy = pq.top().sc.sc;
            pq.pop();
            if(cdst > dist[cx][cy]) continue;

            for(int dir=0; dir<8; dir++){
                int nx = cx + dx[dir], ny = cy + dy[dir];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(h[nx][ny] == -1) continue;
                ll cost = (h[nx][ny] == h[cx][cy] ? 1 : (abs(h[nx][ny]-h[cx][cy])+1)*(abs(h[nx][ny]-h[cx][cy])+1));
                // cout << cx << ' ' << cy << ' ' << nx << ' ' << ny << ' ' << cost << endl;
                ll ndst = cdst + cost;
                if(ndst >= dist[nx][ny]) continue;
                dist[nx][ny] = ndst;
                pq.push({ndst, {nx, ny}});
            }
        }
        if(dist[fx][fy] == INF) cout << "NO" << endl;
        else cout << dist[fx][fy] << endl;
    }
}

/<10722> Binary Mobile Tree

약간의 물리학 사전지식이 필요한 트리 dp문제입니다. 트리 dfs를 통해 각 막대가 평형을 이루려면 매달린 위치에서 얼마만큼 좌우로 위치를 옮겨야 하는지 계산한후 이를 토대로 전체 너비를 계산하면 됩니다. 왼쪽인지 오른쪽인지에 따른 처리가 조금 햇갈릴 수 있습니다.

int T; ld ansl = 0; ld ansr = 0;

// 0 = left, 1 = right
ll dfs(ll cur, int dir, vector<ll>& l, vector<ll>& r, vector<ll>& len, vector<pll> &dp){
    ll node = abs(cur);
    if(cur > 0){
        return cur;
    }
    if(cur == -1){
        ll cl = dfs(l[node], 0, l, r, len, dp);
        ll cr = dfs(r[node], 1, l, r, len, dp);

        dp[node] = {cl , cr};
        return cl + cr;
    }
    else{
        ll cl = dfs(l[node], dir, l, r, len, dp);
        ll cr = dfs(r[node], dir, l, r, len, dp);
        ld x = (ld)(cr*len[node])/(cl+cr);

        dp[node] = {cl , cr};
        return cl + cr;
    }
}

void ddfs(int cur, ld cst, vector<ll>& l, vector<ll>& r, vector<ll>& len, vector<pll> &dp){
    int node = abs(cur);
    if(cur > 0) return;
    ll cl = dp[node].fr, cr = dp[node].sc;
    ld x = (ld)(cr*len[node])/(cl+cr);
    ld y = (ld)len[node] - x;
    ansl = max(ansl, cst+x); ansr = min(ansr, cst-y);
    ddfs(l[node], cst + x, l, r, len, dp);
    ddfs(r[node], cst - y, l, r, len, dp);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<ll>left(n+1), right(n+1), len(n+1);
        vector<pll>dp(n+1, {0, 0});
        for(int i=1; i<=n; i++){
            cin >> len[i] >> left[i] >> right[i];
        }
        ansl = ansr = 0;
        dfs(-1, -1, left, right, len, dp);
        ddfs(-1, 0.0, left, right, len, dp);
        // cout << ansl << ' ' <<ansr << endl;
        cout << ansl - ansr << endl;
    }
}

/<1202> 보석 도둑

PBDS로 날먹했습니다. 끝. (정해는 PQ에 적당한 그리디를 섞는겁니다.)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
 
void m_erase(ordered_set &OS, int val){
    int index = OS.order_of_key(val);
    ordered_set::iterator it = OS.find_by_order(index);
    OS.erase(it);
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);
 
    int n, k; cin >> n >> k; vector<pll>v(n);
    for(int i=0; i<n; i++) cin >> v[i].sc >> v[i].fr;
    sort(v.begin(), v.end(), greater<pll>());

    ordered_set s;
    while(k--){
        ll c; cin >> c; s.insert(c);
    }

    ll ans = 0;
    for(int i=0; i<n; i++){
        int it = s.order_of_key(v[i].sc);
        if(it == (int)s.size()) continue;
        m_erase(s, *s.find_by_order(it)); ans += v[i].fr;
    }
    cout << ans;
}

/<16946> 벽 부수고 이동하기 4

옛날에 은근 까다롭다고 생각했던 문제인데 지금은 쉽게 풀리네요. 벽을 부수지 않은 상태로 이동 가능한 인접한 칸들을 유니온 파인드를 사용해 하나로 묶고 이 묶음의 크기를 저장해 둡니다. 그 후 각 벽에 대해서 인접한 묶음들의 크기를 더합니다.

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

pii par[1005][1005]; int sz[1005][1005], grid[1005][1005];

int ans[1005][1005];

pii fnd(pii node){
    if(par[node.fr][node.sc] == node) return node;
    else return par[node.fr][node.sc] = fnd(par[node.fr][node.sc]);
}

bool uni(pii n1, pii n2){
    pii p1 = fnd(n1), p2 = fnd(n2);
    if(p1 == p2) return false;
    else{
        sz[p1.fr][p1.sc] += sz[p2.fr][p2.sc];
        par[p2.fr][p2.sc] = p1;
        return true;
    }
}

void solve(int n, int m){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            char tmp; cin >> tmp;
            grid[i][j] = tmp-'0';
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            par[i][j] = {i, j}; 
            if(grid[i][j] == 0) sz[i][j] = 1;
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j] == 1) continue;
            for(int dir = 0; dir<4; dir++){
                int nx = i + dx[dir], ny = j + dy[dir];
                if(nx < 0  || nx >= n  || ny < 0 || ny >= m) continue;
                if(grid[nx][ny] == 1) continue;
                uni({i, j}, {nx, ny});
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j] == 0) {
                cout << 0;
                continue;
            }
            set<pii>s;
            for(int dir = 0; dir<4; dir++){
                int nx = i + dx[dir], ny = j + dy[dir];
                if(nx < 0  || nx >= n  || ny < 0 || ny >= m) continue;
                pii p = fnd({nx, ny});
                if(s.count(p)) continue;
                ans[i][j] += sz[p.fr][p.sc]; s.insert(p);
            }
            cout << (ans[i][j]+1) %10;
        }
        cout << endl;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int N, M; cin >> N >> M;
    solve(N, M);
}

/<18110> solved.ac

주어진 조건을 구현. Division by zero 주의.

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    ll n; cin >> n; vector<int>v(n);
    if(n==0){
        cout << 0; return 0;
    }
    for(int i=0; i<n; i++) cin >> v[i];
    int k = (15 * n)/100 + (((15*n)/10)%10 < 5 ? 0 : 1);
    sort(v.begin(), v.end());
    ll sum = 0;
    for(int i=k; i<n-k; i++){
        sum += v[i];
    }
    cout << round((ld)(sum)/(ld)(n-2*k));
}

/<20529> 가장 가까운 세 사람의 심리적 거리

map으로 각 mbti가 몇번 등장 했는지를 저장해둔 후 가능한 모든 $16^3$ 개의 mbti조합중 가능한거에 대해서 답을 브루트포스 하면 됩니다. 태그에 비둘기집 원리가 있던데 왜 있는지 모르겠습니다.

nt dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

vector<string>mbti = {"ISTJ", "ISFJ", "INFJ", "INTJ", "ISTP", "ISFP", "INFP", "INTP", "ESTP", "ESFP", "ENFP", "ENTP", "ESTJ", "ESFJ", "ENFJ", "ENTJ"};

int get(string a, string b, string c){
    int ret = 0;
    for(int i=0; i<4; i++){
        if(a[i] != b[i]) ret++;
        if(b[i] != c[i]) ret++;
        if(c[i] != a[i]) ret++;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int T; cin >> T;
    while(T--){
        int N; cin >> N;
        map<string, int>mp;
        for(int i=0; i<N; i++){
            string s; cin >> s;
            if(mp.find(s) == mp.end()) mp[s] = 1;
            else mp[s]++;
        }

        int ans = 20;
        for(int i=0; i<16; i++){
            for(int j=0; j<16; j++){
                for(int k=0; k<16; k++){
                    string a = mbti[i], b = mbti[j], c = mbti[k];
                    if(mp.find(a) == mp.end() || mp.find(b) == mp.end() || mp.find(c) == mp.end()) continue;
                    int ta = mp[a], tb = mp[b], tc = mp[c];
                    mp[a]--; mp[b]--; mp[c]--;
                    if(mp[a] < 0 || mp[b] < 0 || mp[c] < 0){
                        mp[a] = ta, mp[b] = tb, mp[c] = tc;
                        continue;
                    }
                    ans = min(ans, get(a, b, c));
                    mp[a] = ta, mp[b] = tb, mp[c] = tc;
                }
            }
        }
        cout << ans << endl;
    }
}

/<14940> 쉬운 최단거리

단순 격자 BFS.

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int N, M; cin >> N >> M; int grid[N][M], dist[N][M], vis[N][M]; queue<pii>q;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> grid[i][j];
            dist[i][j] = -1; vis[i][j] = 0;
            if(grid[i][j] == 2) {q.push({i, j}); dist[i][j] = 0; vis[i][j] = 1;}
        }
    }
    
    while(!q.empty()){
        int x = q.front().fr, y = q.front().sc; q.pop();
        for(int dir=0; dir<4; dir++){
            int nx = x + dx[dir], ny = y + dy[dir];
            if(nx < 0 || nx >=N || ny < 0 || ny >= M) continue;
            if(vis[nx][ny] || grid[nx][ny] == 0) continue;
            vis[nx][ny] = 1; dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cout << (grid[i][j] == 0 ? 0 : dist[i][j]) << ' ';
        }
        cout << endl;
    }
}

/<6064> 카잉 달력

CRT밖에 안 떠오르던데... 태그 보면 다른 풀이가 있나 봅니다. 저는 CRT 썼습니다.

/ ax + by = __gcd(a, b) // returns __gcd(a, b)
ll extended_euclid(ll a, ll b, ll &x, ll &y) {
  ll xx = y = 0;
  ll yy = x = 1;
  while (b) {
    ll q = a / b;
    ll t = b; b = a % b; a = t;
    t = xx; xx = x - q * xx; x = t;
    t = yy; yy = y - q * yy; y = t;
  }
  return a;
}
// finds x such that x % m1 = a1, x % m2 = a2. m1 and m2 may not be coprime
// here, x is unique modulo m = lcm(m1, m2). returns (x, m). on failure, m = -1.
pair<ll, ll> CRT(ll a1, ll m1, ll a2, ll m2) {
  ll p, q; ll g = extended_euclid(m1, m2, p, q);
  if (a1 % g != a2 % g) return make_pair(0, -1);
  ll m = m1 / g * m2;
  p = (p % m + m) % m;
  q = (q % m + m) % m;
  return make_pair((p * a2 % m * (m1 / g) % m + q * a1 % m * (m2 / g) % m) %  m, m);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int t; cin >> t;
    while(t--){
        int M, N, x, y; cin >> M >> N >> x >> y;
        
        auto ans = CRT(x-1, M, y-1, N);
        cout << (ans.sc == -1 ? -1 : ans.fr + 1) << endl;
    }
}

/<21736> 헌내기는 친구가 필요해

단순 격자 BFS 2.

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int N, M; cin >> N >> M; char g[N][M]; bool vis[N][M]; queue<pii>q;
    for(int i=0; i<N; i++){
      for(int j=0; j<M; j++){
        cin >> g[i][j]; vis[i][j] = 0;
        if(g[i][j] == 'I') {q.push({i, j}); vis[i][j] = 1;}
      }
    }
    
    int ans = 0;

    while(!q.empty()){
      int x = q.front().fr, y = q.front().sc; q.pop();
      for(int dir=0; dir<4; dir++){
        int nx = x + dx[dir], ny = y + dy[dir];
        if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
        if(vis[nx][ny] || g[nx][ny] == 'X') continue;
        if(g[nx][ny] == 'P') ans++;
        vis[nx][ny] = 1; q.push({nx, ny});
      }
    }
    if(ans) cout << ans;
    else cout << "TT";
}

/<27312> 운영진에게 설정 짜기는 어려워

생각보다 까다로웠던 애드혹 문제입니다. 첫 단추를 잘못 꾀면 못 빠져나오는 느낌? 풀이 자체는 간단한데 $M \le Q \le N$ 이라는 점을 이용해 $i$ 번째 캐릭터의 $i$ 번째 특성을 물어본후 각각 돌아온 결과 외에 특성을 아무거나 출력해줍니다. 이러면 각 캐릭터마다 겹치지 않는 특성이 한개 씩 생기니 문제를 해결 할 수 있습니다.

이런걸 칸토어의 대각 논법이라 부른다던데 뭔지 모르겠습니다. 또 나만 모르는 웰노운인듯.

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int M, N, Q; cin >> M >> N >> Q;
    vector<int>v(N); for(int i=0; i<N; i++) cin >> v[i];
    vector<int>ans;
    for(int i=1; i<=M; i++){
        cout << "? " << i << ' ' << i << endl;
        int ch; cin >> ch;
        if(ch == 1) ans.push_back(v[i-1]);
        else ans.push_back(ch-1);
    }
    for(int i=M+1; i<=N; i++){
        ans.push_back(v[i-1]);
    }
    cout << "! ";
    for(auto i:ans) cout << i << ' ';
    cout << endl;
    return 0;
}

/<1918> 후위 표기식

어려웠습니다. 결국 풀이를 찾아서 공부하면서 풀었습니다.

빈 스택과 빈 후위 표기식을 만들어줍니다.
주어진 중위 표기식을 앞에서부터 훑으면서 다음을 반복합니다.
- 현재 보는 문자가 피연산자라면 후위 표기식에 이어 붙입니다.
- 현재 보는 문자가 연산자라면 스택이 비어있거나 우선순위가 더 낮은 연산자나 괄호가 나올때 까지 스택의 맨위 원소를 제거해서 후위 표기식에 이어 붙입니다. 그 후 스택에 연산자를 넣어줍니다.
- 현재 보는 문자가 ( 라면 이를 스택에 넣어줍니다.
- 현재 보는 문자가 ) 라면 ( 가 나올때까지 스택의 맨위 원소를 제거해서 후위 표기식에 이어 붙입니다. ( 도 스택에서 지워줍니다.

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    string ex; cin >> ex;
    map<char,int>pr; 
    pr['+'] = pr['-'] = 1; pr['*'] = pr['/'] = 2;
    stack<char>st; string ret = "";
    for(char& c:ex){
        if(pr.find(c) == pr.end() && c != '(' && c != ')'){
            ret += c;
        }
        else if(pr.find(c) != pr.end()){
            while(!st.empty() && st.top() != '(' && pr[st.top()] >= pr[c]){
                ret += st.top(); st.pop();
            }
            st.push(c);
        }
        else{
            if(c == '(') st.push(c);
            else{
                while(!st.empty() && st.top() != '('){
                    ret += st.top(); st.pop();
                }
                if(!st.empty() && st.top() == '(') st.pop();
            }
        }
    }
    while(!st.empty()){
        ret += st.top(); st.pop();
    }
    cout << ret;
}

Codeforces

1805C - Place for a Selfie

$ax^2 + bx + c = kx$ 가 해가 없어지는 $k$ 를 찾으면 되는 문제입니다. $k$ 값을 정렬하고 중복값을 제거한 후 $(b-k)^2 - 4ac$ 가 최소가 되는 $k$ 를 찾은 후 이때 $(b-k)^2 - 4ac < 0$ 을 만족하는지 확인하면 됩니다. 저는 삼분탐색을 활용했습니다.

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

#define endl '\n'

#define PRECISION 0

#define fr first
#define sc second

#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll MOD = 1e9+7;
const ll INF = 4'500'000'000'000'000'000;

int t;

ll get(ll a, ll b, ll c, ll idx, vector<ll>& v){
    return (b-v[idx])*(b-v[idx]) - 4LL*a*c;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    cin >> t;
    while(t--){
        int n, m; cin >> n >> m;
        vector<ll>li(n);
        for(int i=0; i<n; i++) cin >> li[i];
        compress(li);

        for(int i=0; i<m; i++){
            ll a, b, c; cin >> a >> b >> c;
            int lo = 0, hi = n - 1;
            while(hi-lo>=3){
                int p = (lo+lo+hi)/3, q = (lo+hi+hi)/3;
                if(get(a, b, c, p, li) <= get(a, b, c, q, li)){
                    hi = q;
                } else lo = p;
            }
            bool flg = false;
            for(int i=lo; i<=hi; i++){
                if(get(a, b, c, i, li) < 0){
                    cout << "YES" << endl;
                    cout << li[i] << endl;
                    flg = true;
                    break;
                }
            }
            if(!flg) cout << "NO" << endl;
        }
        cout << endl;
    }
}

1805D - A Wide, Wide Graph

우선 $G$ 에 모든 정점은 서로 연결되어 있을 겁니다. 그러고 가까운 정점들 사이의 연결부터 하나씩 끊어지게 되는 형태를 이루게 되겠죠. 그러면 어떤 정점 $u$ 가 연결된 컴포넌트에서 분리되는 시점은 $k$ 가 $u$ 에서 가장 멀리 떨어진 정점까지의 거리보다 커지는 시점이 됩니다 (그 이전 시점까지는 어떻게든 다른 정점과 연결이 되어 있을거니까). 그리고 이 가장 멀리 떨어진 정점은 트리의 지름에 속해있는 두 정점중 더 멀리 떨어진 정점이 됩니다 (그렇지 않다면 지름일 수가 없기 때문). 따라서 트리의 정점을 구한 후 양 끝 정점에서 다른 모든 정점들까지의 거리를 구해주면 각 $k$ 에 대해서 몇개의 정점이 떨어져 나가게 되는지 구할 수 있습니다. 답이 $N$ 보다 커질수는 없음에 주의합시다.

제가 처음에 생각하지 못했던 부분은 다음 두가지 입니다.

지름의 후보가 여러개 일수는 있지만 결국 그러면 더 멀리 떨어진 정점까지 거리가 지름을 이루니 따로 처리해줄 필요가 없다.
둘 중 더 멀리 떨어진걸 저장해야 한다. (저는 실수로 더 가까운걸 저장했습니다.)

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

#define endl '\n'

#define PRECISION 0

#define fr first
#define sc second

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll MOD = 1e9+7;
const ll INF = 4'500'000'000'000'000'000;

int n;
int dist[100005];
vector<int>edges[100005];

int dinode = 1 , di1 = 1, di2 = 1, mxdist = 0;
void dfs1(int cur, int par, int d){
    dist[cur] = d;
    if(d >= mxdist){
        mxdist = d;
        dinode = cur;
    }
    for(auto nxt:edges[cur]){
        if(nxt==par) continue;
        dfs1(nxt, cur, d+1);
    }
}

void dfs2(int cur, int par, int d, vector<int>&dst){
    dst[cur] = d;
    for(auto nxt:edges[cur]){
        if(nxt == par) continue;
        dfs2(nxt, cur, d+1, dst);
    }
}

int removedat[100005]; int dp[100005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    cin >> n;
    for(int i=1; i<n; i++){
        int u, v; cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs1(1, -1, 0); di1 = dinode;
    dfs1(dinode, -1, 0); di2 = dinode;
    vector<int>dd1(n+1, 0), dd2(n+1, 0);
    dfs2(di1, -1, 0, dd1); dfs2(di2, -1, 0, dd2);

    for(int i=1; i<=n; i++){
        dd1[i] = max(dd1[i], dd2[i]);
        removedat[dd1[i]]++;
    }

    int ans = 1;
    for(int i=1; i<=n; i++){
        cout << min(n, ans) << ' ';
        ans += removedat[i];
    }
}

1942D - Learning to Paint

우선 처음 해봤던 생각은 다음과 같습니다.

$k$ 개의 가장 큰거만 중간 과정에 저장하는 DP로 해결할 수 있지 않을까?
어떤 원소 $a_{i,j}$ 를 합에 더하려면 이전 구간이 $i-2$ 전에는 끝나야 하는구나.
안 더하는 경우까지 고려를 해줘야 하는구나.

이 점들을 사용해서 DP를 사용 할 수 있을거 같았는데 결국 구체적인건 못 떠올리고 에디토리얼을 봤습니다. 풀이는 다음과 같습니다.

$dp[i]$ 가 $i$ 에서 끝나는 모든 구간들까지 고려 했을때 가장 큰 $min(k, 2^i)$ 개의 합들을 저장한 리스트라고 합시다. 그렇다면 결국 $dp[i]$ 를 구하는건 $dp[1], dp[2], \dots, dp[i-1]$ 안에 있는 원소나 그 중 $j \le i-2$ 인 $dp[j]$ 의 원소들에 $a_{j+2, i}$ 를 더한 값 중 가장 큰 $k$ 개를 구하는 문제가 됩니다. 이때 애초에 리스트에 더하는 순서를 큰거부터 넣어준 다면 정렬 순서를 유지할 수 있으니 기본적으로 각 $dp[i]$ 에 대해서 $dp[i][0]$ 가 가장 큰 원소임을 보장 할 수 있게 됩니다. 따라서 $dp[i]$ 를 구하는 과정은 다음과 같아집니다.

값, 리스트 번호, 리스트 내에서의 위치이 3가지 정보를 저장하는 PQ를 만듭시다. 그 후 PQ에 $0 \le j \le i-1$ 인 $j$ 에 대해

$j = i-1$ 이면 $(dp[i-1][0], i-1, 0)$ 을 넣어줍니다.
$j \le i-2$ 이면 $(dp[j][0] + a_{j+2, i}, j, 0)$ 을 넣어줍니다.
$dp[0]$ 은 ${0}$ 으로 정의합니다.
그냥 단순히 $a_{1, i}$ 를 넣는거 까지 고려해서 이 또한 넣어줍니다. 이 때 $j$ 는 편의상 $-1$ 로 정합니다.

그 후 PQ가 비거나 $dp[i]$ 의 크기가 $k$ 가 될때 까지 다음을 반복합니다.

PQ의 맨위에서 $(val, j, idx)$ 를 뽑아줍니다. 그 후 $val$ 을 $dp[i]$ 에 넣어줍니다.
$j < 0$ 또는 $idx = len(dp[j])-1$ 이라면 아래 과정은 건너뜁니다.
$j = i-1$ 이라면 $a_{j+2, i}$ 를 더해줄 수 없으니 단순히 $j$ 번째 리스트의 다음으로 큰 원소를 넣어줍니다 $(dp[i-1][idx+1], i-1, idx+1)$ .
$j \le i-2$ 이라면 $a_{j+2, i}$ 를 더해줄 수 있으니 $j$ 번째 리스트의 다음으로 큰 원소에 그 값을 더해서 넣어줍니다 $(dp[j][idx+1] + a_{j+2, i}, i-1, idx+1)$ .

위 과정을 $1 \dots i$ 까지 반복해주면 $dp[n]$ 에 남아있는 $k$ 개의 원소가 답이 됩니다.

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

#define endl '\n'

#define PRECISION 0

#define fr first
#define sc second

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll MOD = 1e9+7;
const ll LLINF = 4'500'000'000'000'000'000;
const int INF = 1'000'000'007;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int t; cin >> t;
    while(t--) {
        int n, k; cin >> n >> k;
        vector<ll>dp[n+1]; ll arr[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=i; j<=n; j++){
                cin >> arr[i][j];
            }
        }
        dp[0].push_back(0);

        for(int i=1; i<=n; i++){
            // val, from-j, idx-in-list-j
            priority_queue<pair<ll, pll> > pq;

            pq.push({dp[i-1][0], {i-1, 0}});

            // to add interval, must be at least 2 apart
            for(int j=i-2; j>=0; j--){
                if(j > 0) pq.push({dp[j][0] + arr[j+2][i], {j, 0}});
                else{
                    pq.push({arr[j+2][i], {j, 0}});
                }
            }pq.push({arr[1][i], {-1, 0}});

            while(!pq.empty() && dp[i].size() < k){
                ll val = pq.top().fr; int j = pq.top().sc.fr, idx = pq.top().sc.sc; pq.pop();
                dp[i].push_back(val);

                if(j < 0 || idx == (int)dp[j].size()-1) continue;

                if(j == i-1){
                    pq.push({dp[i-1][idx+1], {i-1, idx+1}});
                }
                else{
                    pq.push({dp[j][idx+1] + arr[j+2][i], {j, idx+1}});
                }
            }
        }

        for(auto i : dp[n]) cout << i << ' ';
        cout << endl;
    }
}

일부러 문제를 읽어본 사람이 읽는다고 가정하고 풀이를 좀 짧게 짧게 적어봤습니다. 제가 개인적으로 복습하고 싶은 부분이 있는 문제들은 조금 더 힘을 줬고요. 앞으로도 얼마나 꾸준히 작성할지는 모르지만 주간 회고록은 이런 형식으로 적어 보도록 하겠습니다.

감사합니다.

'PS' 카테고리의 다른 글

딱히 주간은 아닌 회고록 (0)	2024.05.28

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

seonah@nox.katena

2023.04.20 주간 회고록

BOJ

/<20303> 할로윈의 양아치

/<27172> 수 나누기 게임

/<17404> RGB거리 2

/<2143> 두 배열의 합

/<2342> Dance Dance Revolution

/<2473> 세 용액

/<16724> 피리 부는 사나이

/<7670> Game Dice

/<1029> Hiking

/<10722> Binary Mobile Tree

/<1202> 보석 도둑

/<16946> 벽 부수고 이동하기 4

/<18110> solved.ac

/<20529> 가장 가까운 세 사람의 심리적 거리

/<14940> 쉬운 최단거리

/<6064> 카잉 달력

/<21736> 헌내기는 친구가 필요해

/<27312> 운영진에게 설정 짜기는 어려워

/<1918> 후위 표기식

Codeforces

1805C - Place for a Selfie

1805D - A Wide, Wide Graph

1942D - Learning to Paint

'PS' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

2023.04.20 주간 회고록

BOJ

/<20303> 할로윈의 양아치

/<27172> 수 나누기 게임

/<17404> RGB거리 2

/<2143> 두 배열의 합

/<2342> Dance Dance Revolution

/<2473> 세 용액

/<16724> 피리 부는 사나이

/<7670> Game Dice

/<1029> Hiking

/<10722> Binary Mobile Tree

/<1202> 보석 도둑

/<16946> 벽 부수고 이동하기 4

/<18110> solved.ac

/<20529> 가장 가까운 세 사람의 심리적 거리

/<14940> 쉬운 최단거리

/<6064> 카잉 달력

/<21736> 헌내기는 친구가 필요해

/<27312> 운영진에게 설정 짜기는 어려워

/<1918> 후위 표기식

Codeforces

1805C - Place for a Selfie

1805D - A Wide, Wide Graph

1942D - Learning to Paint

'PS' 카테고리의 다른 글

'PS' Related Articles

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역