코드포스 - 실력이 안늘어 ㅠㅠ

codeforce round #823(div 2), #824(div 2) 업솔빙

Codeforces Round #823, #824 개요

최근 두 달간 코드포스 포스팅을 안올렸다. 그래도 꽤 열심히 참여했는데 822 때 한번 4솔하고 나머지는 또 2솔 수준이다. ㅠㅠ
살면서 머리가 나쁘다는 생각은 해본적이 없는데 이 쯤 되니 머리가 안따라주는 것 같다.(머리가 늙은건가)
내가 열심히만 하면 다 이겨라는 생각을 가지고 살았었는데 블루 가기가 이렇게 힘들다니 ㅠㅠ 알고리즘을 하면서 겸손을 배운다.
너무 대단한 사람들이 많다. 빨리 따라잡고 싶다.
824는 B번 풀다가 빡종해버렸다. 스트레스 때문에 문제를 볼 수가 없었다.
사실 떨어지면 떨어지나보다 라고 생각하는 것도 필요한데 한 문제 한 문제가 안풀릴때마다 너무 불안하다.
107점 시원하게 박았으니 다시 초심으로 돌아가서 열심히 풀어봐야겟다.

823 A. Planets(0:06)

C로 묶음으로 파괴할 수 있다. 그니까 행성의 개수가 C보다 많으면 C로 한번에 파괴하는게 이득이고, 아니면 하나씩 파괴하는게 이득이다.

int n, c; cin >> n >> c;
vector<int> a(n);
for(int i=0;i<n;i++){
    cin >> a[i];
    orbit[a[i]]++;
}
int res = 0;
for(int i=1;i<=100;i++){
    if(orbit[i]){
        if(orbit[i]>c) res += c;
        else res += orbit[i];
    }
}
cout << res << '\n';
memset(orbit, 0, sizeof(orbit));

823 B. Meeting on the Line(upsolving)

이번엔 B를 못풀었다.
사람들이 어려웠다고는 했지만 그 사람들은 풀었고 난 못 풀었다.
그냥 실력차가 어마무시하다 ㅠㅠ
이분탐색으로 풀거나 그리디하게 풀 수 있다.
이분탐색으로 푼다면 만나는 시간을 찾아서 거기서 부터 계산한다.
그리디로 푼다면 나오는 시간을 기준으로 가장 작은 것과 가장 큰 것의 중간에서 만나는 것으로 풀 수 있다.
그 중간꺼는 어짜피 가면서 같이 갈 수 있다.
핵심은 음수 일 수도 있으니 처음 시작 최대, 최소를 잘 설정해줘야하고 precision()은 필수다.

cout << fixed;
cout.precision(15);
int n; cin >> n;
vector<int> a(n), t(n);
for(int i=0;i<n;i++) cin >> a[i];
int mn = INF, mx = -INF;
for(int i=0;i<n;i++){
    cin >> t[i];
    mn = min(mn, a[i]-t[i]);
    mx = max(mx, a[i]+t[i]);
}
cout << double(mn+mx)/2.0 << '\n';

823 C. Minimum Notation(1:28)

B 박살나고 한번 와봤는데 좀 쉬워보였다.
그래서 열심히 구현했는데 몇번 틀렸다.

1은 걍 가만히 놔두는게 이득이다
자신보다 앞에 있는데 크면 내 뒤로 보내는게 이득이다.
작은 것부터 보면서 그 뒤에 나오는게 인덱스가 더 앞이면 +1 해서 뒤로 보내는 것이다.
min(9, 어쩌구)를 해줘야한다 (이것땜에 틀렸다 ㅠ)

bool compare(pii p1, pii p2){
    if(p1.first!=p2.first) return p1.first<p2.first;
    return p1.second > p2.second;
}
int main(){
    fast_io
    int tt; cin >> tt;
    while (tt--) {
        string str; cin >> str;
        vector<pii> X(str.length());
        for(int i=0;i<str.length();i++){
            X[i].first = str[i];
            X[i].second = i;
        }
        sort(X.begin(), X.end(), compare);
        int mi = 0;
        for(int i=0;i<str.length();i++){
            int temp = X[i].second;
            while(i<str.length()-1&&X[i].first==X[i+1].first){
                if(mi>X[i].second) cout << min('9', (char)(X[i].first+1));
                else cout << (char)X[i].first;
                i++;
            }
            if(mi>X[i].second) cout << min('9', (char)(X[i].first+1));
            else cout << (char)X[i].first;
            mi = max(mi, temp);
        }
        cout << '\n';
    }
}

823 D. Prefixes and Suffixes(upsolving)

문제 이해는 문장이 짧고 간결해서 매우 쉽다.

바꿀 덩어리 크기를 고른다 k
s1의 앞에서 k, s2의 뒤에서 k를 바꾼다. s1==s2인 상태를 만들 수 있는가? 없는가? 일단 s2를 뒤집어서 t를 만든다 그러면 각 대응 되는 쌍은 서로 뒤바꿀 수 있다.
이들을 움직여서 똑같이 만든다는 것은 s1이 팰린드롬이면 된다.
abc 와 pqr을 바꾼다고 하면 rqp cba 로 바뀐다. 이렇게 바뀌는 것을 이용하면 쌍만 적절히 있으면 무조건 팰린드롬을 만들 수 있다는 것이다.
그래서 문제가 팰린드롬을 만들 수 있는가 없는가로 바뀌게 된다.
따라서 쌍의 개수가 짝수면 양옆으로 흩뿌리면 되니까 ok고 쌍이 홀수면 두 문자가 같은 경우는 가운데 박으면 되니까 하나 정도는 있어도 된다.
이를 이용하면 코드는 아래와 같다.
```
int n; cin >> n;
string s, t;
cin >> s >> t;
reverse(t.begin(), t.end());
map<pii, int> m;
for(int i=0;i<n;i++){
if(s[i]>t[i]) swap(s[i], t[i]);
m[make_pair(s[i], t[i])]++;
}
map<pii, int> ::iterator it;
it = m.begin();
int cnt = 0;
while (it!=m.end()) {
if(it->second%2){
    cnt += 1 +(it->first.first!=it->first.second);
}
it++;
}
cout << ((cnt<=1) ? "YES\n" : "NO\n");
```

824 A. Working Week(0:11)

은근히 빡셌다. 그리고 이게 이번 셋에서 처음이자 마지막으로 풀게된 문제일지도 몰랐다. ㅋㅋㅋ

int n; cin >> n;
if(n<9) cout << 0 << '\n';
else{
    n -= 3;
    cout << (n/3)-1 << '\n';
}

3개의 구간으로 나누는게 중요하니까 이런식으로 나눌 수 있다.
벽세우는거 -3하고 3구간으로 쪼갰을 때 그 중 젤 작은건 균일하게 쪼개고 동일한거에서 -1한거다.

824 B. Tea with Tangerines(upsolving)

쉬운줄 알았는데 8틀을 박았다.
진짜 너무 화나서 이것만 풀고 끝낸다라고 생각하고 하다가 걍 던져버렸다.
지금 이순간에도 왜 틀렸는지 솔직히 모르겠다.(그냥 에디토리얼 보러갔다옴)
아, 보고 왔는데 비슷하게 한 것 같은데 그냥 틀려버렸다 ㄷㄷ. 반례를 찾는게 진짜 어렵다 ㅠㅠ
먼가 off-by-one 처럼 아슬아슬하게 빗나가는게 있나보다… 경계값도 다해봤는데 허무하다.
이것땜에 107점 떨궜다..하…
나는 하나를 못풀면 못넘어가겠다 ㅠ 계속 생각나서 뒤에 것도 못푼다.
나의 문제풀이 방식을 좀 바꿀 필요도 있겠다.

int main(){
    fast_io
    int tt; cin >> tt;
    while (tt--) {
        int n; cin >> n;
        vector<ll> a(n);
        for(int i=0;i<n;i++) cin >> a[i];
        ll res = 0;
        for(int i=0;i<n;i++){
            res += (a[i]-1)/(2*a[0]-1);
        }
        cout << res << '\n';
    }
}

824 C. Phase Shift(upsolving)

여기부터는 안풀었었다.(B 때문에 스트레스 받아서)
그래도 이 문제는 읽어는 봤다. 뭔가 짜증나보여서 걍 B에 올인한것이였다.
문제이해가 잘 안됐다. 대충은 알겠는데 조건이 좀 잡다해서 일단 이해한건 다음과 같다.

문자가 대응되는데 같은 문자로 대응되면 안된다.
대응되고 나서 그 문자로만 순환(시계처럼)되면 안된다.
뭔가 말이 애매한데….그건 내가 이해를 잘 못해서 그렇다.
그래서 하나씩 매치해나가고
```
bool check(int x, int j){
 bool ok = true;
 int cnt = 0;
 while (E[j]!=-1) {
     j = E[j];
     cnt++;
     if(j==x&&cnt!=25){
         ok = false;
         break;
     }
 }
 return ok;
}
```
위 처럼 쭉 따라갔을 때 일부만으로 원이 만들어지면 false를 준다.
cnt가 25라는 것은 원을 모든 알파벳을 이용하여 만든거니까 가능하다.

823 D. Meta-set(upsolving)

왜케 문제가 이해가 안되는지 모르겠다. 천천히 읽어봤는데 C도 그렇고 해석이 안된다 ㄷㄷ.
파파고 돌렸는데 더 모르겠다 ㅋㅋㅋ
문제를 정확히 이해하는 것도 중요한데 B번 풀었어도 C, D 이해 안되어서 못풀었을 것 같다. ㅠㅠ
수업시간에 열심히 보면서 겨우 이해했다.
3개의 세트는 무조건 포함을 해야한다. 그리고 나머지 2개는 상관없다.
그러니 한 세트 별로 그 세트를 제외한 나머지 부분에서 몇개를 고를 수 있는지 체크하면 된다.
모든 세트일때를 구해두고 정답을 구할 땐 문제에서 주어진 set에서만 계산하면 된다.

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, k;

int main(){
    fast_io
    cin >> n >> k;
    vector<vector<int> > V(n);
    for(int i=0;i<n;i++){
        vector<int> inV(k);
        for(int j=0;j<k;j++) cin >> inV[j];
        V[i] = inV;
    }
    map<vector<int> , int> m;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            vector<int> tmp(k);
            for(int p=0;p<k;p++){
                tmp[p] = (6-V[i][p]-V[j][p])%3;
            }
            m[tmp]++;
        }
    }
    ll res = 0;
    for(int i=0;i<n;i++){
        ll X = m[V[i]];
        res += X*(X-1)/2;
    }
    cout << res;
}