[Codeforces] Round 928 (Div. 4) 후기

Problem Solving/Codeforces

[Codeforces] Round 928 (Div. 4) 후기

5-ms 2024. 2. 20. 16:03

https://codeforces.com/contest/1926

Dashboard - Codeforces Round 928 (Div. 4) - Codeforces

codeforces.com

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

Codeforces Round 928 (Div. 4) Editorial - Codeforces

codeforces.com

2024.02.19

간만의 div4.

이전 div3에서 4솔을 했으니까 이번 div4에서는 5솔은 하지않을까? 기대하며 풀었지만...

div3와 마찬가지로 ABCD 4솔로 마무리했다..

그래도 뭐 퍼포를 떨구진 않았으니 다행이라고 생각하는중..

A. Vlad and the Best of Five (00:01)

단순히 A,B 중에서 많이 나온 알파벳 출력하는 문제였다.

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


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        string str; cin>>str;
        ll a=0,b=0;
        rep(i,0,5){
            if(str[i]=='A') a++;
            else b++;
        }
        if(a>b) cout<<"A\n";
        else cout<<"B\n";
    }
}

B. Vlad and Shapes (00:07)

삼각형이 위로뾰족, 아래로 뾰족 둘 중 하나니까..

각 행마다 1의 개수를 구하고, 개수가 다르다면 TRIANGLE, 같다면 SQUARE을 출력한다.

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


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        ll n; cin>>n;
        vector<string> v(n);
        rep(i,0,n) cin>>v[i];
        ll cnt = -1;


        bool flag = 0;
        rep(i,0,n){
            ll tmp = 0;
            rep(j,0,n){
                if(v[i][j]=='1') tmp++;
            }
            if(tmp==0) continue;
            
            if(tmp!=0){
                if(cnt==-1){
                    cnt = tmp;
                }
                else{
                    if(cnt!=tmp){
                        flag = 1;
                        break;
                    }
                }
            }
        }
        if(flag) cout<<"TRIANGLE\n";
        else cout<<"SQUARE\n";
    }
}

C. Vlad and a Sum of Sum of Digits (00:19)

매 입력때마다 1부터 n까지 반복문을 돌리면 시간초과가 난다.n이 최대 200,000이므로 전처리를 통해 정답을 다 구해놓은 다음, 입력에 맞게 출력하였다.

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

int dp[200'001];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    rep(i,1,200'001){
        string str = to_string(i);
        ll sum = 0;
        rep(j,0,str.length()){
            sum += str[j]-'0';
        }
        dp[i] = dp[i-1] + sum;
    }
    while(t--){
        ll n; cin>>n;
        cout<<dp[n]<<'\n';
    }
}

D. Vlad and Division (00:59)

2^32-1 과 입력은 xor 연산하면 0과 1이 반전된 숫자를 구할 수 있다.

multiset을 이용해서 정답을 구했는데.. 에디토리얼은 map으로 더 간단하게 했네...ㅎ

처음에 map으로 했다가 정답이 자꾸 이상하게 나오길래 multiset으로 했는데.... 쩝

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        ll n; cin>>n;
        multiset<int> s;
        ll cnt = 0;
        rep(i,0,n){
            int a; cin>>a;
            int tmp = 2147483647^a;
            if(!s.empty() && s.find(a)!=s.end()){
                auto it = s.find(a);
                s.erase(it);
                cnt++;
            }
            else{
                s.insert(tmp);
            }
        }
        cout<<s.size()+cnt<<'\n';

    }
}

E. Vlad and an Odd Ordering

O(n^2) 코드를 짜긴 했는데.. 최적화를 어떻게 해야될지 모르겠어서 못풀었다...

에디토리얼 보고 겨우 풀었네;

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void func(){
    ll n,k; cin>>n>>k;
    vector<int> v;
    while(n){
        v.push_back((n+1)/2); //단계별 개수
        n/=2;
    }
    int i=0, pow=1;
    for(int x:v){
        if(i<k && k<=i+x){
            cout<<pow*(2*(k-i)-1)<<'\n';
            return;
        }
        i += x;
        pow *= 2;
    }
    return;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        func();
    }
}