프로그래밍

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

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

[풀이]
몇번 연산이 일어나든 같은 index 위치의 문자들끼리만 교환이 일어나므로
연산 후의 특정 index에 존재하는 a~z의 각 개수는 동일해야합니다.
이것을 이용하면 어떤 문자열이 사라졌는지 찾을 수 있습니다.

1. check[100001][26] 배열을 선언해 0~N-1 번째 위치에 a~z (0~25) 가 각 몇개씩 있는지를 저장해놓습니다.
(만약 i번 위치에 'c'가 있다면 check[i]['c'-'a]++ 를 통해 c 1개가 추가되었다는 것을 기록합니다.)
2. 그 다음에 주어지는 연산이 완료된 N-1개의 문자에 대해 i번 위치에 어떤 문자가 있으면 check[i]['문자'-'a']-- 연산을 통해 연산 뒤에도 해당 문자가 남아있음을 체크합니다.

3. 사라진 문자열의 i번 문자는 check[i][j] (j:0~25 (a~z index)) 중에 1인 문자가 됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N,M;
int check[100001][26];

void solve(){
    memset(check,0,sizeof(check));

    string s,ret;
    for(int i=0;i<N;i++){
        cin >> s;
        for(int j=0;j<M;j++){
            check[j][s[j]-'a']++;
        }
    }

    for(int i=0;i<N-1;i++){
        cin >> s;
        for(int j=0;j<M;j++){
            check[j][s[j]-'a']--;
        }
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<26;j++){
            if(check[i][j]>0){
                ret.push_back(j+'a');
            }
        }
    }
    cout << ret << '\n';
    cout << flush;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> tc;
    while(tc--){
        cin >> N >> M;
        solve();
    }
}

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

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

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

[풀이]
최대 100번의 연산 내에 A배열을 B배열로 만들어야 합니다.
각 루프에서 i:0~N-1 루프를 돌면서 A[i]-B[i]가 가장 작은 값과 큰 값을 찾아서 저장한 뒤
A[i]-B[i]가 작은 A[i]는 +1, 큰 A[i]는 -1 을 해주면
이것이 매 루프마다 정답에 가장 유리한 연산이 됩니다.

100번내에 A=B를 만들 수 있으면 정답을 출력합니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N,a[100],b[100],INF=987654321;

bool same(){
    for(int i=0;i<N;i++){
        if(a[i]!=b[i]) return false;
    }
    return true;
}
void prt(){
    for(int i=0;i<N;i++){
        printf("%d ",a[i]);
    }
    puts("");
}
void solve(){

    int it=100;
    vector<pair<int,int>> ans;
    while(it--){

        int minDiff=INF,minIdx=-1;
        int maxDiff=-INF,maxIdx=-1;
        bool ok=1;
        for(int i=0;i<N;i++){
            int d = a[i]-b[i];
            if(d!=0) ok=0;
            if(minDiff>d){
                minDiff=d;
                minIdx=i;
            }
            if(maxDiff<d){
                maxDiff=d;
                maxIdx=i;
            }
        }
        if(ok) break;

        a[minIdx]++;
        a[maxIdx]--;
        ans.push_back({maxIdx,minIdx});
    }
    if(same()){
        printf("%d\n",ans.size());
        for(auto p : ans){
            printf("%d %d\n",p.first+1,p.second+1);
        }
    }else{
        puts("-1");
    }
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        for(int i=0;i<N;i++) scanf("%d",&b[i]);
        solve();
    }
}

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

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

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

[풀이]
Greedy 문제입니다.

a,b 배열의 index를 aidx, bidx로 유지하면서 a[aidx],b[bidx]중 하나를 선택해
ans vector에 추가해주는 식으로 풉니다. 정답이 존재한다면 ans vector의 크기가 n+m이 되어야 합니다.

a[adix],b[bidx] 중에 고르는 기준은 다음과 같습니다..
1) 둘중 0이 있는 경우 무조건 선택한다. 새로운 라인을 추가하는 것은 어떤 경우에도 유리하기 때문
2) 0이 없을때는 k (현재 페이지의 총 라인수) 보다 작거나 같은 값이 있으면 선택한다. 라인을 수정하는 것은
아직 선택되지 않은 것들에 어떤 악영향도 미치지 않으므로

aidx==n , bidx==m이 될때까지 위 과정을 반복하면 ans vector에 최종 정답이 저장됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc;
int k,n,m,a[301],b[301];
 
void prt(){
    puts("a");
    for(int i=0;i<n;i++) printf("%d ",a[i]);
 
    puts("b");
    for(int i=0;i<m;i++) printf("%d ",b[i]);
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&k,&n,&m);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        vector<int> ans;
 
        int aidx=0,bidx=0;
        int it=m+n;
        while(it--){
            if(aidx<n){
                if(a[aidx]==0) {
                    k++;
                    aidx++;
                    ans.push_back(0);
                    continue;
                }
            }
            if(bidx<m){
                if(b[bidx]==0) {
                    k++;
                    bidx++;
                    ans.push_back(0);
                    continue;
                }
            }
 
            if(aidx<n){               
                if(k>=a[aidx]){
                    ans.push_back(a[aidx]);
                    aidx++;
 
                    continue;
                }
            }            
            if(bidx<m){
                if(k>=b[bidx]){
                    ans.push_back(b[bidx]);
                    bidx++;
                    continue;
                }
            }    
        }
        if(ans.size()<m+n) puts("-1");
        else{
            for(int a : ans) printf("%d ",a);
            puts("");
        }
    }
    
}

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

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

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

[풀이]
'a'의 index를 찾고 왼쪽 index l 오른쪽 index r을 유지하면서
'b','c','d'..가 순서대로 l,r 둘중 하나에 존재하는지를 체크해줍니다.
만약 지금 나와야하는 알파벳이 l,r 둘중 하나에 없다면 NO를 출력해주고,
모든 알파벳을 찾을 수 있다면 YES를 출력합니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int tc;
string s;

bool solve(){
    int cur=-1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='a') {
            cur=i;
            break;
        }
    }
    if(cur==-1) return false;
    int l=cur,r=cur;

    int sz = s.size()-1;
    char target='b';
    while(sz--){

        if(l-1>=0){
            if(s[l-1]==target){
                l--;
                target++;
                continue;
            }
        }
        if(r+1<s.size()){
            if(s[r+1]==target){
                r++;
                target++;
                continue;
            }
        }
        return false;
    }
    return true;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        cin >> s;
        string ret = solve()?"YES":"NO";
        cout << ret << '\n';
    }

}

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

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

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

[풀이]
tc가 10^4인걸 생각 못하고 BFS로 풀었다가 TLE를 맞았습니다.
A,B,F가 모두 다른 점이므로 O(1)에 계산이 가능하다는 것을 파악해야합니다.
만약 A,B,F가 일직선상에 있지 않다면 최단거리가 여러 가지이므로 F에 의해 한 경로가 막힌다 하더라도
다른 경로를 이용하면 되므로 무조건 dist(A,B) 만큼이 최단 거리가 됩니다.

만약 A,B,F가 일직선 상에 있고 A,B 사이에 F가 있다면 유일한 최단 거리 dist(A,B)가 막힌 것이므로
F를 피해서 가는 이동 2를 더해줘야 하므로 dist(A,B)+2가 정답이 됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int tc,sy,sx,ey,ex,fy,fx;
bool visit[1001][1001];

bool same(int a,int b,int c){
    return (a==b&&b==c);
}
bool between(int a,int b,int c){
    if(a>c) swap(a,c);
    return (a<b&&b<c);
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d%d%d",&sx,&sy,&ex,&ey,&fx,&fy);
        int ans = abs(sx-ex)+abs(sy-ey);
        if(same(sx,fx,ex)&&between(sy,fy,ey) || same(sy,fy,ey)&&between(sx,fx,ex)){
            ans+=2;
        }
        printf("%d\n",ans);
    }
}

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

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

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

[풀이]
a[1]과 a[N]에 어떤 수가 들어있는지에 따라서 답을 구해야 한다.

최악의 경우는
a[1]에 N, a[N]에 1이 있는 경우, 이 경우에는 1~N-1을 sort -> 2~N을 sorting -> 1~N-1을 sorting 총 3번을 sorting 해야 한다.

이미 정렬이 되어있는 경우 0번

a[1]==1 이거나 a[N]==N인 경우 이것을 제외하고 1번만 정렬하면 되므로 1번

나머지 경우는 2번만 정렬해주면 된다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using ll = long long;
 
int t,N,a[51];
 
int solve(){
    bool ok=1;
    for(int i=1;i<=N;i++){
        if(a[i]!=i){
            ok=0;
            break;
        }
    }
    if(ok) return 0;
    
    if(a[1]==1 || a[N]==N) return 1;
    if(a[1]==N && a[N]==1) return 3;
 
    return 2;
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        printf("%d\n",solve());
    }
}

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

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

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

[풀이]
K와 100-K의 최대공약수를 구한 뒤 100을 최대공약수로 나눠주면 된다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using ll = long long;
 
int t,k;
 
int gcd(int a,int b){
    if(a>b) swap(a,b);
 
    while(a>0){
        int c = b%a;
        b=a;
        a=c;
    }
 
    return b;
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&k);
        if(k==100){
            puts("1");
            continue;
        }
 
        int a = k;
        int b = 100-k;
        int g = gcd(a,b);
        printf("%d\n",a/g+b/g);
    }
}

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

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

[난이도] Div.3
[유형] 이분탐색

[풀이]
x<=10^12로 x가 큰 숫자여도 a^3+b^3=x 이므로 a,b는 아무리 커도 10^4보다 작은 수이다.
1~10^4 범위의 a를 모두 검사하면서 이분탐색으로 a^3+b^3=x를 만족하는 b를 1~10^4 범위에서 찾으면 된다.

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
int tc;
ll x;
 
bool solve(){
 
    ll a = min(10000LL,(ll)sqrt(x));
 
    for(ll i=1;i<=a;i++){
 
 
        ll lo=0,hi=a+1;
        while(lo+1<hi){
 
            ll mid = (lo+hi)/2;
            
            ll v = i*i*i+mid*mid*mid;
            if(v==x) return true;
            if(v>x) hi = mid;
            else lo = mid;
 
        }
        //printf("i:%d, lo:%lld\n",i,lo);
    }
    return false;
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%lld",&x);
 
        if(solve()) puts("YES");
        else puts("NO");
    }
 
}

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