Codeforces 1000 ~ 1400 set 2

저번 셋을 통해 4문제 2시간이 은근 짧다고 느껴져서 2문제를 추가하여 돌렸다. 총평은 역시 그리디가 많고 언제나 어렵다...

[문제] Codeforces 1384 A

[문제 유형]

Greedy, Constructive algorithms

[시간복잡도]

$O(n)$

[풀이]

문자열 $S_{i}$와 $S_{i+1}$의 가장 긴 공통 접두사의 길이가 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;

char nextChar(char x){
    if(x == 'z')return 'a';
    return x + 1;
}

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

    int t;cin >> t;
    while(t--){
        int n; cin >> n;
        int ml = 1;
        vector<int> v;
        vector<string> ans;
        for(int i=0;i<n;i++){
            int x;cin >> x;
            v.push_back(x);
            ml = max(ml, x);
        }
        ans.resize(n+1);
        string cur;
        for(int j=0;j<ml;j++) cur += 'a';
        ans[0] = cur;
        for(int i=1;i<=n;i++){
            ans[i] = ans[i-1];
            ans[i][v[i-1]] = nextChar(ans[i][v[i-1]]);
        }
        for(auto &i: ans)cout << i << '\n';
    }

    return 0;
}

[문제] Codeforces 1382 B

[문제 유형]

DP, Game

[시간복잡도]

$O(n)$

[풀이]

님 게임....이다. 이게 왜 $1100$이냐 했는데 문제를 제대로 읽어보니깐 remove a positive number of stones from the first non-empty pile 이라는 문장이 있다. (하지만 게임이론은 항상 어렵다...) 왼쪽부터 하나씩 무조건 없애야하니깐 맨 처음 돌이 $1$개 있을 경우와 그보다 더 많이 있을 경우로 생각해보자. 만약 돌이 $2$개 이상 있다고 가정하면 먼저 시작하는 선수는 돌을 $1$개를 남기거나 다 없애는 두가지 전략을 선택할 수 있다. 그럼 만약 돌이 $1$개가 있다고 가정하면 시작하는 사람은 무조건 $1$개를 가지고 가야하므로 무조건 이길수가 있는 것은 아니다.

여기까지 정리해보면 처음 시작할 때 처음 시작할 때 돌이 $1$개짜리에 따라 순서를 정할 수 있다고 판단된다. (감으로 될 것 같다는 판단....) 또한 그 이후에 돌이 $2$개 이상 있는 더미에서 시작하는 사람이 주도권을 가지고 갈 수 있다. 만약에 모든 더미가 돌 $1$개가 있을 경우는 어떨까? 경우의 수를 나눠보자.

경우의 수 생각하는건 은근 간단했던 것 같다. 먼저 전체 더미가 돌 $1$개가 있을 경우를 생각해보자. 플레이어는 단 두명이기 때문에 홀수 짝수로 나누면 된다. 돌의 개수가 홀수 일 경우는 먼저 시작하는게 좋다. 짝수는 당연히 두번째로 시작하는 것이 좋다.

이제, 돌이 $2$개 이상 있는 더미가 있을 경우를 생각해보자. 이것도 비슷하게 할 수 있다. 돌이 $2$개 이상 있는 더미에서 먼저 시작하는 것이 이득이므로 돌이 $1$개인 더미가 홀수일 경우 두번째로 시작하고 짝수인 경우는 먼저 시작하는게 좋다.

쓰면서 부분 뺀 것도 있는데 혹시 이해 안될까봐 추가로 작성하면 돌의 개수가 $2$개 이상인 더미에서 먼저 시작해야 이길 수 있다. 그 더미 이후에 돌이 $1$개 나오던 $2$개 이상 나오던 신경 쓸 필요가 없다. 가장 핵심은 주도권을 잡는 것이라 생각한다.

그래도 게임이론은 어렵다;;

[소스코드]

#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;
        int idx=0;
        while(idx < n && v[idx] == 1)++idx;
        int answer = (idx == n) ^ (idx % 2);
        if(answer)cout << "Second\n";
        else cout << "First\n";
    }

    return 0;
}

[문제] Codeforces 1381 A1

[문제 유형]

Constructive algorithms

[시간복잡도]

$O(n^2)$

[풀이]

$n$이 $1000$이하이다. 그냥 구현하듯이 풀면 된다. 또한 문제에서 문자열 $a$에서 $b$로 변경하는데 $3n$이하로 가능하다고 알려줬다. 주어진 연산은 길이 $l$인 prefix를 잡고 비트를 반전시키고 그 prefix를 뒤집는 것이다. 간단하게 푸는 방법은 prefix를 연산하는 것이므로 맨 뒤에서부터 만들어가면 된다. 즉 $a[i] \ne b[i]$ 이면 연산을 적용해야한다. 더 확인해야하는 것은 뒤집는 연산이 있기 때문에 $a[0]$와 $b[i]$이 같다면 $a$의 $1$ 길이의 prefix를 연산하고 $i$ 길이의 prefix를 연산하면 된다. 다르다면 $i$ 길이의 prefix만 연산하면 된다.

[소스코드]

#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;

void operation(string &cur, int idx){
    string tmp; tmp.resize(idx);
    for(int i=0;i<idx;i++)
        tmp[i] = '1' + '0' - cur[i];
    for(int i=idx-1;i>=0;i--)
        cur[idx-1-i] = tmp[i];
}

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

    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        string a, b; cin >> a >> b;
        vector<int> ans;
        for(int i=n-1;i>=0;i--){
            if(a[i] == b[i])continue;
            if(a[0] == b[i]){
                ans.push_back(1);
                operation(a, 1);
            }
            ans.push_back(i+1);
            operation(a, i+1);
        }
        cout << ans.size();
        for(auto i: ans)cout << " " << i;
        cout << '\n';
    }

    return 0;
}

[문제] Codeforces 1380 C

[문제 유형]

DP, Greedy

[시간복잡도]

$O(n log n)$

[풀이]

정렬을 비내림차순으로 정렬 후 디피로 돌렸다. $DP[ i + nxt] = max(DP[i + nxt], DP[i] + 1)$ $( nxt = (x + a[i] - 1) \div a[i] )$
그리고 DP식으로 나온 값들 중 최대값이 답이다.

[소스코드]

#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--){
        ll n, x; cin >> n >> x;
        vector<ll> v(n);
        for(auto &i: v)cin >> i;
        sort(all(v));
        ll ans = 0;
        ll dp[100001] = {0};
        for(int i=0;i<n;i++){
            ll cur = (x + v[i] - 1) / v[i] + i;
            if(cur > n)continue;
            dp[cur] = max(dp[cur], dp[i] + 1);
        }
        for(int i=0;i<=n;i++) ans = max(ans, dp[i]);
        cout << ans << '\n';
    }

    return 0;
}

[문제] Codeforces 1380 B

[문제 유형]

Greedy

[시간복잡도]

$O(n)$

[풀이]

문제 풀때부터 뭔가 그리디인 냄새가 확 났다. 따라서 정확한 증명을 하지 않고 대충 감으로 맞추려고 했던 것 같다. bot이 낸 것들을 개수를 세고 가장 많이 낸 결과를 이기는 것을 $n$번 내면 된다.

[소스코드]

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
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--){
        string in, ans;
        cin >> in;
        ans.resize(siz(in));
        int R=0,S=0,P=0;
        for(int i=0;i<siz(in);i++){
            if(in[i] == 'R')R++;
            if(in[i] == 'S')S++;
            if(in[i] == 'P')P++;
        }
        int maxi = max({R,S,P});
        for(int i=0;i<siz(in);i++){
            if(R==maxi)ans[i]='P';
            if(S==maxi)ans[i]='R';
            if(P==maxi)ans[i]='S';
        }
        cout << ans << '\n';
    }

    return 0;
}

[문제] Codeforces 1375 C

[문제 유형]

Greedy

[시간복잡도]

$O(1)$

[풀이]

오늘 셋 중에서 가장 코드가 짧기도 하고 난이도는 가장 어려웠던 것 같다. 이것도 감으로 푼 것 같은데 실제 코포 할 때는 못풀었을꺼 같다. 일단 너무 당연하게도 $a[1] \gt a[n]$인 경우는 불가능하다고 생각이 들었다. $a[1] \lt a[n]$인 경우는 어떻게 해야할지 계속 고민을 했는데 $1 \sim n$ 사이를 잘 하면 다 될꺼 같다는 생각과 함께 그냥 제출해봤더니 맞아버렸다 ;; 버추얼 끝나고 에디토리얼 봤는데 $100%$ 이해는 안됬다.

[소스코드]

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
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;
        cout << (v[0]<v[n-1]?"YES":"NO") << '\n'; 
    }
    return 0;
}