[Codeforces] Round 929 (Div. 3) 후기

https://codeforces.com/contest/1986

Dashboard - Codeforces Round 954 (Div. 3) - Codeforces

https://codeforces.com/blog/entry/130762

Codeforces Round 954 (Div. 3) Editorial - Codeforces

 

---

2024.06.24

종강하고 첫 코포! 

코드포스가 라운드가 자주 열려서 좋긴 한데..

시간대가 너무 새벽이라 학교와 병행하기가 조금 어려워서 못하고 엣코더만 했었다.

사실 런타임때 안하고 버츄얼로 돌릴 수도 있었던건데... 머릿속으로만 해야지~해야지~ 하다가 결국 종강하는 동안 한번도 안해버린... 

시작하기 전에 오랜만에 코포를 돌리다보니 감을 잃진 않았을까.. 했는데, 다행히! 안정적으로 4솔에 민트퍼포가 나왔다! 조금 걸리긴 했지만.. 그래도 레이팅 올랐으니 만족 !

이번 방학동안에 알고리즘 동아리 사람들 몇명 모아서 ucpc, icpc 대비?겸 코포&엣코더 스터디를 하려고하는데, 개강하기 전까지 꼭 코포 블루 달고싶다! 더도말고 덜도말고 딱 블루!

 

---

A. X Axis (00:02)

숫자 세개가 주어질때, 임의의 정수 a와 각각의 세 숫자의 차이의 합의 최소값을 구하는 문제.

당연히? 숫자 셋중 중앙값이 a가 될것이고, 양 옆의 숫자와의 차를 구해주면 된다.

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){
        vector<int> v(3);
        rep(i,0,3) cin>>v[i];
        sort(all(v));
        cout<<(v[1]-v[0])+(v[2]-v[1])<<'\n';
    }

}

 

---

B. Matrix Stabilization (00:13)

n*n 배열에서, 주변보다 큰 값을 가진 칸이 존재하는 동안에 그 칸에 -1을 해주고, 최종 결과를 출력하는 문제.

문제에서 말하듯이 -1을 해주면 반드시 오래걸린다. -1이 아니라 적절히 최적화를 해주어야 하는데,

일단 주변보다 큰 값을 가진 칸을 찾고, 그 칸의 주변 4칸 중 가장 큰 값으로 변경해주면 끝!

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){
        int n,m; cin>>n>>m;
        vector<vector<int>> board(n,vector<int>(m,0));
        rep(i,0,n) rep(j,0,m) cin>>board[i][j];

        rep(i,0,n) rep(j,0,m){
            int mx = -1;
            bool flag = 1;
            for(int dir=0;dir<4;dir++){
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if(nx<0||nx>=n||ny<0||ny>=m) continue;
                if(board[i][j] <= board[nx][ny]){
                    flag = 0;
                }
                else mx = max(mx,board[nx][ny]);
            }
            if(flag) board[i][j]=mx;
        }
        rep(i,0,n){
            rep(j,0,m) cout<<board[i][j]<<' ';
            cout<<'\n';
        }
    }

}

 

---

C. Update Queries (00:34)

입력의 문자열 s를 배열 ind와 배열 c의 순서를 잘 바꿔서 s를 사전순으로 가장 작은 문자열로 만들어야된다. 

ind과 c가 독립적?이므로 그냥 각각 정렬해주고, 각 인덱스에 들어갈 수 있는 최소값을 넣어주면 된다. 

되게 간단하게 풀리는 문제였는데, 이상하게 구현하는데에 좀 걸렸다.. 

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){
        int n,m; cin>>n>>m; 
        string str; cin>>str;
        vector<int> v(m);
        rep(i,0,m) cin>>v[i];
        rep(i,0,m) v[i]--;
        string c; cin>>c;

        sort(all(v));
        sort(all(c));

        int bef=-1;
        int idx=0;
        rep(i,0,m){
            if(v[i]==bef){
                continue;
            }
            else{
                bef = v[i];
                str[v[i]] = c[idx];
                idx++;
            }
        }
        cout<<str<<'\n';
    }
}

 

---

D. Mathematical Problem (01:18)

길이 n의 숫자로된 string이 주어지고, 숫자 사이에 n-2개의 덧셈, 곱셈 연산자를 넣은 계산 결과의 최소값을 구하는 문제.

브루트포스+그리디? 느낌으로 풀었다.

일단 숫자 두개를 합치고 연산자를 n-1개 추가한다는 느낌으로 풀었다.

n은 최대 20이기 때문에, 연속된 숫자 두개를 합치는 경우의수는 최대 19가지고, 각각의 경우를 O(n)으로 처리한다면 문제를 해결할 수 있을 것이라고 생각했다.

또, string에 0이 있다면, n이 4 이상일때, 답이 무조건 0이 나올 수 밖에 없더라. 숫자 다 곱해버리면 0이니까..

그리고, 덧셈기호는 언제 사용할까? 생각했는데, 1이 아닌 숫자들을 더할때만 사용한다. 그 외엔 1과 곱하는게 최소를 만들 수 있다. 3*1 이 3+1보다 작으니까..

그래서 계산할때 1보다 큰 경우에만 더하도록 했는데, 여기서 또 예외처리를 해주어야 했다. 

string이 101일때, 위처럼 계산하면 0이 나와버려서.. 1의 개수를 또 세주고, 만약 계산결과가 0인데 문자열에 1이 있었다면 1을 추가로 더해주었다. 

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){
        int n; cin>>n;
        string str; cin>>str;
        int ans = 2e9;
        if(n==2){
            cout<<(str[0]-'0')*10 + (str[1]-'0')<<'\n';
            continue;
        }
        rep(i,0,n-1){ //i와 i+1을 이음
            int tot=0;
            vector<int> v; 
            rep(j,0,n){
                if(i==j) v.push_back((str[j]-'0')*10 + (str[++j]-'0'));
                else v.push_back(str[j]-'0');
            }

            int zero=0;
            rep(j,0,v.size()) zero+=(v[j]==0);
            if(zero) ans = 0;
            int one=0;
            rep(j,0,v.size()) one+=(v[j]==1);

            rep(j,0,v.size()){
                if(v[j]>1) tot+=v[j];
            }
            if(one&&!tot) tot++;
            ans = min(ans,tot);
        }
        cout<<ans<<'\n';


    }

}