Codeforces 1000 ~ 1400 set 1

백준에서 알고리즘 풀다가 최근에 다시 코드포스를 참가하면서 느낀점은 CP 실력이 더더욱 나빠졌다는 것이다.

따라서 실력을 상승시키기 위해 난이도를 정해놓고 빠른 시간에 풀 수 있도록 연습을 하려 한다.

처음은 간단하게 난이도 1000 ~ 1400 정도의 문제를 2시간 제한시간을 주고 풀기 시작하고 점차 너무 쉽거나 난이도를 올려도 될때는 문제 수를 늘리거나 난이도를 상향하여 계속 진행할 것 같다.

[문제] Codeforces 1385 C

[문제 유형]

Greedy

[시간복잡도]

$O(n)$

[풀이]

배열 A에서 A의 접미사 ( $1 \le i \le n, ; [ a_{i} , a_{i+1} , ... , a_{n}]$ ) 중
$a_{i} \le a_{i+1} ... a_{i+k} \ge a_{i+k+1} \ge a_{n}$ 를 만족하거나 $a_{i} \le a_{i+1} ... a_{n-1} \le a_{n}$ 를 만족하는 것을 찾으면 된다.

[소스코드]

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MOD = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        vector<int> v(n);
        for(auto &i: v)cin >> i;
        bool le=false, ge=false; // < > 
        int ans = 0;
        for(int i=n-1;i;i--){
            if(v[i-1]==v[i])continue;
            if(v[i-1]>v[i]){
                if(le){
                    ans = i;
                    break; 
                }
                ge=true;
            }
            else{
                le=true;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

[문제] Codeforces 1388 B

[문제 유형]

Greedy

[시간복잡도]

$O(n)$

[풀이]

$n$ 자리 10진수를 $X$라 하자. $X$를 이진수로 변경한 수 맨 오른쪽 $n$비트를 삭제 했을 때 만들어지는 수를 $K$로 하자. $K$ 중 최대 값을 만드는 $X$중 가장 작은 값을 찾으면 된다. $n$자리를 $9$로 채운 후 오른쪽부터 $n$ 비트가 해당하는 부분의 (10진) 수를 $8$로 변경하면 된다.

$0 \sim 7$는 비트의 길이가 3이하이기 때문에 $8, 9$로만 구성해야 $X$를 최대로 만들 수 있다.

[소스코드]

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MOD = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int t;cin >> t;
    while(t--){
        int n; cin >> n;
        string str(n, '9');
        int idx=n-1;
        while(n > 0){
            str[idx]='8';
            idx--;
            n -= 4;
        }
        cout<<str<<'\n';
    }

    return 0;
}

[문제] Codeforces 1393 B

[문제 유형]

Greedy, Implementation

[시간복잡도]

$O(Q)$

[풀이]

판자를 이용하여 정사각형, 직사각형 각각 한 개를 만드려고 한다. 한 변을 만들 때 판자는 단 하나만 사용가능하다. 구현하기는 좀 귀찮지만 천천히 구현하면 된다.

[소스코드]

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MOD = 1e9 + 7;

vector<int> v;
int cnt[100001], group[10];

bool solve(){
    if(group[8])return true;
    int sq=0,rt=0;
    for(int i=7;i>=2;i--){
        if(!group[i])continue;
        if(i >= 4){
            if(group[i] >= 2)sq=1, rt=2;
            else{
                if(sq)rt+=2;
                else {
                    if(i >= 6)rt++;
                    sq++;
                }
            }
        }
        else {
            if(group[i] >= 2)rt+=2;
            else rt++;
        }
    }
    return sq && rt >= 2;
}

inline int idx(int c){ return c >= 8 ? 8 : c; }

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for(int i=0;i<n;i++){
        int x;cin >> x;
        v.push_back(x);
        if(cnt[x])group[cnt[x]]--;
        group[idx(++cnt[x])]++;
    }
    int t;cin >> t;
    while(t--){
        string s; int x;cin >> s >> x;
        if(!s.compare("+")){
            if(cnt[x])group[idx(cnt[x])]--;
            group[idx(++cnt[x])]++;
        }
        else{
            group[idx(cnt[x])]--;
            if(--cnt[x])group[idx(cnt[x])]++;
        }
        if(solve())cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

[문제] Codeforces 1399 C

[문제 유형]

Brute force

[시간복잡도]

$O(n^3)$

[풀이]

$a_{i} + a_{j} (i \ne j) = k$를 만족하게 그룹을 나눌때 최대 몇 그룹으로 나뉘는지 찾으면 되는 문제이다.
$n$이 최대 50밖에 안된다. 그냥 돌리자.

[소스코드]

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MOD = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int t;cin >> t;
    while(t--){
        int n; cin>>n;
        vector<int> v(n);
        vector<int> cnt(51, 0);
        for(auto &i: v){
            cin >> i;
            cnt[i]++;
        }
        sort(all(v));
        int ans = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int siz = v[i] + v[j];
                int cur = 1;
                vector<int> tmp=cnt; 
                tmp[v[i]]--;
                tmp[v[j]]--;
                for(int k=0;k<n;k++){
                    if(k == i || k == j)continue;
                    if(tmp[v[k]] == 0)continue;
                    int nxt = siz - v[k];
                    if(0 > nxt || nxt > 50)continue;
                    if(tmp[nxt] == 0)continue;
                    if(v[k] == nxt && tmp[nxt] < 2)continue;
                    tmp[nxt]--;
                    tmp[v[k]]--;
                    cur++;
                }
                ans=max(ans, cur);
            }
        }
        cout << ans << '\n';
    }

    return 0;
}