프로그래밍

https://codeforces.com/contest/1490/problem/B

[난이도] Div.3
[유형] 구현

[풀이]
크기 3짜리 배열에 나머지가 0,1,2인 숫자들의 개수를 각각 저장 뒤.
index 0,1,2 각각에서 시작해서 N/3만큼만 남기고 순차적으로 우측( a[(i+1)%3] ) 으로
밀어보는 시도를 한다.
최대 2회까지 밀어보고 나머지를 민 타겟의 위치가 N/3이 되게 되면 그때가 최적의 정답이다.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int tc,n,a[50];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int ans = 0;
        for(int i=1;i<n;i++){
            int p=a[i-1],q=a[i];
            if(p>q) swap(p,q);
            if(2*p>=q) continue;
            int cur=p;
 
            for(int cur=2*p;cur<q;cur*=2){
                ans++;
            }  
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round702-Div.3/B.cpp

https://codeforces.com/contest/1490/problem/A

[난이도] Div.3
[유형] Greedy

[풀이]
a[i]와 a[i+1]가 dense가 아니라면 둘중 작은 수에서 두배의 수를 더해가면서 배열에 추가해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int tc,n,a[50];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int ans = 0;
        for(int i=1;i<n;i++){
            int p=a[i-1],q=a[i];
            if(p>q) swap(p,q);
            if(2*p>=q) continue;
            int cur=p;
 
            for(int cur=2*p;cur<q;cur*=2){
                ans++;
            }  
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round702-Div.3/A.cpp

https://codeforces.com/contest/1485/problem/B

[난이도] Div.2
[유형] 구간합

[풀이]
쿼리가 l,r 일때,
a[l],a[l+1]...a[r] 부분수열을 고려해야 한다.
l,l+1,...r 중에 한개를 선택해서 바꿀 때, 그것을 대신해서 선택할 수 있는 수들의 합을 더하는 문제이다.
주석친 부분과 같이 일일이 더했을 때 시간초과가 발생하였다.
미리 부분합을 구해놓으면 query마다 O(1)로 해결할 수 있다.
부분합 dp[i] (i=l+1~r-1): l+1부터 i번 수를 한번씩 선택했을 때 만들 수 있는 수열의 개수.
query가 l,r 인 경우
답은 1. dp[r-1]-dp[l] (l+1,l+2...,r-1 을 선택했을 때 만들 수 있는 수열의 수)
2. a[l+1]-2 (l을 선택했을 때 만들 수 있는 수열의 수)
3. k-a[r-1]-1 (r을 선택했을 때 만들 수 있는 수열의 수)
위 세가지를 더한 값이 정답이다. (l과 r을 선택할 때는 방식이 다르므로 따로 계산해준다.)

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int tc;
int n,q,k,a[100003],dp[100003];
 
int main(){
    scanf("%d%d%d",&n,&q,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=2;i<n;i++){
        dp[i] = dp[i-1]+a[i+1]-a[i-1]-2;
    }
 
    while(q--){
        int l,r,ans=0;
        scanf("%d%d",&l,&r);
        if(l==r) ans=k-1;
        else{
            ans+=a[l+1]-2;
            ans+=k-a[r-1]-1;
            ans+=dp[r-1]-dp[l];
            // for(int i=l;i<=r;i++){
            //     int v;
            //     if(i==l) v = a[i+1]-2;
            //     else if(i==r) v = k-a[i-1]-1;
            //     else v = a[i+1]-a[i-1]-2;
            //     ans+=v;
            // }
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round701-Div.2/B.cpp

https://codeforces.com/contest/1485/problem/A

[난이도] Div.2
[유형] 수학

[풀이]
아이디어 : +와 / 연산을 사용할 때 +연산을 먼저 하는게 무조건 이득이다.

1. b,b+1,b+2,b+3...b+i 를 검사 (+를 몇개 쓸건지..)
2. '/'가 영향력이 더 크기때문에 +를 많이 써서 b를 크게 만들수록 연산의 횟수는 점점 줄어들 것이다.
그러나 일정 이상 b가 커지면 b를 더이상 증가시키는 것이 손해인 순간이 온다 (ex a=12,b=7 : a=12,b=8 의 결과는 동일하다.)

3. 그러므로 b를 증가시키는 것이 손해가 되는 순간이 i일 때,
정답은 i-1만큼 b를 증가시켰을때이다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int tc,a,b;
 
int sol(int a,int b){
    int ret=0;
    while(a!=0){
        a/=b;
        ret++;
    }
    return ret;
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        int ans=1e8;
 
        scanf("%d%d",&a,&b);
 
        int prev=1e8;
        for(int i=0;;i++){
            if(b+i==1) continue;
 
            int t = sol(a,b+i);
            t+=i;
            if(t>prev) break;
            prev=t;
        }
        printf("%d\n",prev);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round701-Div.2/A.cpp

https://codeforces.com/contest/1472/problem/D

[난이도] Div.3
[유형] Greedy

[풀이]
홀수, 짝수인 숫자를 따로 vector에 보관 후 정렬하고,
Alice 차례일때 현재 홀수중 최댓값이 짝수중 최댓값보다 크다면 홀수를 선택해서 Bob이 선택못하도록 하고,
짝수가 더크다면 짝수를 선택하는 방식으로 하는것이 Alice에게 최적이다.
Bob의 차례인 경우엔 그 반대로 하면 된다.

다른 풀이를 보고 알 수 있었는데
홀수,짝수 상관없이 정렬 후 큰 수부터 선택해도 Alice,Bob 모두 optimal 하므로 이 방식으로 풀어도 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int tc,N;
int main(){
    scanf("%d",&tc);
    
    while(tc--){
        scanf("%d",&N);
        vector<ll> odd,even;
        for(int i=0;i<N;i++){
            ll v;
            scanf("%lld",&v);
            if(v%2) odd.push_back(v);
            else even.push_back(v);
        }
        sort(odd.begin(),odd.end());
        sort(even.begin(),even.end());
        
        int curo=odd.size()-1,cure=even.size()-1;
        ll alice=0,bob=0;
        for(int i=0;;i++){
            if(curo<0&&cure<0) break;
            if(i%2==0){
                if(curo<0){
                    alice+=even[cure--];
                    continue;
                }
                if(cure<0){
                    curo--;
                    continue;
                }

                if(odd[curo] <= even[cure]){
                    alice+=even[cure--];
                }else{
                    curo--;
                }
            }else{
                if(curo<0){
                    cure--;
                    continue;
                }
                if(cure<0){
                    bob+=odd[curo--];
                    continue;
                }

                if(odd[curo] >= even[cure]){
                    bob+=odd[curo--];
                }else{
                    cure--;
                }
            }
        }
        if(alice>bob) puts("Alice");
        else if(alice<bob) puts("Bob");
        else puts("Tie");
        //printf("alice:%d, bob:%d\n",alice,bob);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/D.cpp

https://codeforces.com/contest/1472/problem/C

[난이도] Div.3
[유형] DP

[풀이]
DP(i) (1<=i<=N) : index i를 선택했을 얻을 수 있는 점수.
점화식 : DP(i) = A[i] + DP(i+A[i])

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int tc,N,a[200001],dp[200001];
int sol(int n){
    if(n > N) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret = a[n]+sol(n+a[n]);
    return ret;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        memset(dp,-1,sizeof(dp));
        int ans = 0;
        for(int i=1;i<=N;i++) ans = max(ans,sol(i));
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/C.cpp

https://codeforces.com/contest/1472/problem/A

[난이도] Div.3
[유형] 수학

[풀이]
2^(W가 2로 나눠지는 횟수) * 2^(H가 2로 나눠지는 횟수) 가 최대 자를 수 있는 조각임을 알 수 있다.

#include <cstdio>
using ll = long long;
int tc,H,W;
ll N;
int main(){
    scanf("%d",&tc);
    while(tc--){ 
        scanf("%d%d%lld",&W,&H,&N);
        int wc=1,hc=1;
        while(W%2==0){
            wc*=2;
            W/=2;
        }
        while(H%2==0){
            hc*=2;
            H/=2;
        }
        if(wc*hc >= N) puts("YES");
        else puts("NO");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/A.cpp

https://codeforces.com/contest/1367/problem/D

[난이도] Div.3
[유형] Greedy

[풀이]
b[i]가 0인 i에는 가장 큰 알파벳이 있다는 것을 문제의 조건을 통해 알 수 있다.
(더해줄 abs(i-j)가 없으므로).
1. 현재 배열 상태에서 b[i]가 0인 i들을 찾고 그곳에 사용할 수 있는 알파벳중 큰 순서대로 확인하면서
찾은 0의 개수보다 알파벳 개수가 크거나 같으면 그 알파벳으로 찾은 i위치에 할당한다.
2. 위에서 찾은 인덱스들은 다른 b[i]들에 영향을 주면 안되므로 거리만큼 빼줘서 영향을 제거해준다.

위 과정을 반복해서 m개를 모두 찾으면 정답 스트링을 출력한다.

#include <string>
#include <queue>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int tc,n,k,b[51],cnt[27];
int main(){
    scanf("%d",&tc);
    while(tc--){
        string s;
        cin >> s >> n;
        for(int i=0;i<n;i++) cin >> b[i];
        priority_queue<int> q;
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<s.size();i++){
            if(!cnt[s[i]-'a']) q.push(s[i]-'a');
            cnt[s[i]-'a']++;
        }
        string ans;
        ans.resize(n);
        int total=0;
        while(total<n){
            vector<int> t;
            for(int i=0;i<n;i++) {
                if(b[i]==0) {
                    b[i]=-1;
                    t.push_back(i);
                }
            }
            for(int i=0;i<n;i++) {
                if(b[i]==-1) continue; 
                for(auto k : t) b[i]-=abs(i-k);
            }
            while(!q.empty()){
                if(cnt[q.top()]>=t.size()){
                    for(auto k : t) ans[k]=q.top()+'a';
                    q.pop();
                    total+=t.size();
                    break;
                }
                q.pop();
            }
        }
        cout << ans << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/D.cpp