ChangHyeon Nam's Blog notes and thoughts

Codeforce Round#734 (Div. 3)

Comments

virtual round 참가했다. A, B1만 풀었다. (B2에서 못넘어갔다.) 못 푼 문제들은 tutorial을 참고하여 읽고서 구현해볼 예정이다. (매번 못풀고 그냥 넘겼는데, 해설이라도 보고 공부해야겠다!) 아자아자.

Codeforces Round #734 (Div. 3)

A - Polycarp and Coins

$c_1+2*c_2=n$ 을 만족하는 $c_1,c_2$에 대해서 두수의 차이가 최소인 쌍을 구하는 문제였다. n을 3으로 나눈 나머지와 몫을 계산한다. 나머지가 2일 경우엔 c2에 1을 더해주고 나머지가 1일때는 c1에 더해 주었다.

code 
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include<queue>
#define endl '\n'
#define INF 1e9
#define LINF 2e15

using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

vector<vector<pi>> v;
priority_queue<pi,vector<pi>,greater<pi>> q;
ll t,n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t;
    while(t--){
        cin>>n;
        ll c1,c2,tmp,tmp1;
        tmp = n%3;
        tmp1 =n/3;
        c1 = tmp+tmp1;
        c2 = tmp1;
        if(tmp==2){
            c1 = tmp1;
            c2 = tmp1+1;
        }
        cout<<c1<<" "<<c2<<endl;
    }
}

B1 - Wonderful Coloring - 1

map을 이용하여 같은 값에 대한 개수를 세주었다. 색칠되는 문자의 총 개수를 세준 후에 2로 나눠 답을 구했다. 개수가 2개 이상인 문자는 count+=2를 하여 3번째 부터는 고려하지 않도록 해주었다.

code 
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include<queue>
#include<map>
#define endl '\n'
#define INF 1e9
#define LINF 2e15

using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

vector<vector<pi>> v;
priority_queue<pi,vector<pi>,greater<pi>> q;
int t;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t;
    while(t--){
        string s;
        map<char,int> m;
        cin>>s;
        int count=0;
        for(int i=0;i<s.size();i++){
            m[s[i]]++;
        }
        for(auto[i,j]:m){
            if(j==1)
                count+=1;
            else if(j>=2)
                count+=2;
        }
        cout<<count/2<<endl;
    }
}

B2 - Wonderful Coloring - 2

같은 색깔에는 같은 숫자가 있으면 안되고, 같은 숫자들은 서로 색깔이 모두 달라야 할때, 최대한 많이 색칠하는 문제였다. sequence의 길이 n과 색깔의 개수 k가 주어진다.

풀이의 핵심 아이디어는 다음과 같다. 어떠한 숫자도 최대로 칠해질 수 있는 개수가 k개이다. 즉, 어떤 숫자 x가 나온 횟수가 k 이상이라면, k개까지만 서로다른 색깔로 칠해진다. 나머지는 모두 0(=칠하지 않는다.)을 대입한다.

k개 미만의 숫자들에 대한 index는 새로운 vector에 모은다. k개의 색깔을 순환하면서 k개의 배수만큼만 칠하고, 나머지는 칠하지 않는다. 예를 들어 설명하겠다.

n=10, k=3이고, 3은 2개, 1은 4개, 10은 3개, 2는 2개이다. 먼저 1은 4개이므로 앞선 3개를 1,2,3으로 칠하고 나머지 하나는 칠하지 않는다. 10은 3개이므로 3개 모두 1,2,3으로 칠한다. 그리고 k개 미만인 수인 3과 2에 대한 인덱스를 새로운 vector에 넣어준다. (vector의 size / k )번 만큼 1,2,3을 순환하며 색칠해준다.

code 
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define endl '\n'
#define INF 1e9
#define LINF 2e15

using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

const int MAX_N = 200 * 1000 + 13;

int ans[MAX_N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        memset(ans,0,(n+1) * sizeof(ans[0]));
        vector<vector<int>>v;
        v.resize(n+1);
        for(int i=1;i<=n;i++){
            int a;
            ans[i]=0;
            cin>>a;
            v[a].push_back(i);
        }
        vector<int>temp;

        for(int i=1;i<=n;i++){
            if(v[i].size()>=k){
                for(int j=0;j<k;j++){
                    ans[v[i][j]]=j+1;
                }
            }
            else if(v[i].size()<k&&v[i].size()>=1)
            {
                for(auto j:v[i])
                    temp.push_back(j);
            }
        }

        int group = temp.size()/k;
        int color = 1;
        int countgroup =0;
        for(auto i:temp){
            if(countgroup==group)
                break;
            ans[i]=color;
            if(color==k)
            {
                countgroup+=1;
            }
            color+=1;
            if(color==k+1)
            {
                color = 1;
            }
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
        cout<<endl;

    }
    return 0;
}

C - Interesting Story

a,b,c,d,e로만 이루어진 n개의 문장이 주어지고, 각 문장이 interesting stroy에 포함되려면 되려면 가장 많은 알파벳의 개수가 나머지의 개수보다 많아야 한다. 그리고 그런 interesting story가되는 문장의 최대개수를 구하는 것이 문제였다.

scnt[n][5] : n개의 문장에 대해, 각 알파벳이 interesting story가 되기위한 영향에 대해 해당 알파벳이라면 +1, 아니라면 -1을 더하여 나타낸 값이다. 가령 “aabc”라고 하면 scnt[‘a’]= 1+1-1-1 = 0, scnt[‘b’] =-1+-1+1-1=-2 이다.

이렇게 나타낸후 n개의 문장에 대해 각 alphabet에 대해 scnt값을 내림차순으로 sort를 한후, n개의 문장에 대해 누적값이 0보다 크면 문장의개수 +1, 아니면 종료를 한다. (정말 설명을 못한다.)

code 
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include<queue>
#define endl '\n'
#define INF 1e9
#define LINF 2e15

using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,pair<int,int>> pii;

//vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;

int t;
bool cmp(const int a, const int b){
    return a>b;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t;
    while(t--){
        int n;
        int ans =0;
        cin>>n;
        int scnt[200001][5];
        memset(scnt,0,sizeof(scnt));
        for(int i=0;i<n;i++){
            string str;
            cin>>str;
            for(auto j:str){
                if(j=='a')
                    scnt[i][0]++;
                if(j=='b')
                    scnt[i][1]++;
                if(j=='c')
                    scnt[i][2]++;
                if(j=='d')
                    scnt[i][3]++;
                if(j=='e')
                    scnt[i][4]++;
            }
            for(int j=0;j<5;j++){
                int tmp = scnt[i][j];
                scnt[i][j]=2*tmp-str.size();
            }
        }
        vector<vector<int>>V;
        V.resize(5);
        for(int j=0;j<5;j++){
            for(int i=0;i<n;i++){
                V[j].push_back(scnt[i][j]);
            }
        }
        for(int i=0;i<5;i++){
            sort(V[i].begin(),V[i].end(),cmp);
            int count =0;
            int tans =0;
            for(auto k:V[i])
            {
                if((count+k)>0){
                    count += k;
                    tans+=1;
                }
            }
            ans = max(ans,tans);
        }
        cout<<ans<<endl;

    }
    return 0;
}

내일 이어서!