COFO::Round #609 ( div 2 )

• Link : COFO::609 ( div 2 )
• solved :
  • A : ( 00:25 )
  • B : ( 01:58 )
  • rank : 2906
  • score : 700
• B번에서만 5트정도 시도한 것 같습니다.
• 3트 이상 넘어갔는데 WA 이유를 찾지 못하겠다면, 문제를 다시 차근차근 읽어봐야할 것 같습니다.
• 이번에도 문제에서 얻은 힌트로 조금 더 안정적인 답을 출력할 수 있었고, B번을 버저비터로 넣은 것 같습니다.

Problem A : Equation

• level : 800
• tag : brute force, math
• time : 00:25
• 찝찝하지만, AC 받을 수도 있을 것 같은 코드를 제출했고, AC를 받았습니다.
• 찝찝한 이유는 증명을 하지 않아서 입니다.

Point

• 1이상 10^7 이하인 n이 주어집니다.
• a - b = n을 만족하는 a와 b를 출력합니다.
  • 2 <= a, b <= 10^9
  • a 와 b는 composite, 즉 소수가 아닌 수 이어야 합니다.

Design(x)

• 사람들 풀이도 정말 다양합니다.
  • 저처럼 복잡하게 푼 사람도 꽤 있는 것 같습니다.
    • 저는 2가지 경우의 수로 나누어서 풀이하였습니다.
      • a b n 에 대해서
      • 짝 짝 짝
        • 이 경우, 하나는 4로 출력하고 다른 하나는 n+4를 출력합니다.
        • 4이상의 짝수는 무조건 composite이기 때문입니다.
      • 짝 홀 홀
      • 홀 짝 홀
        • 위의 두가지에 대해서는, eratosThenes의 체를 이용하였습니다.
        • 즉, 둘 중 하나는 짝수이고 2를 제외한 모든 짝수는 가능합니다.
        • 따라서, a = n+ 2*x를 만족하는 x를 찾습니다.
        • 즉 2x 부분과 n+2x 두 부분으로 b와 a를 표현하는 것입니다.
    • 하지만 문제에서 나타낸 바와 같이 a와 b의 범위는 10^9 까지이고, 메모리가 충분하지 않습니다.
    • 분명히 어떤 규칙이 있을 것 같아서, 10^7까지로만 체를 구성하였고 제출하였습니다.
• editorial에는
  • “print 9n and 8n”이라고만 나와있습니다.
  • 맞는 말이네요
  • 둘의 차이가 n이고, 9와 8은 composite이므로,
  • 또한 9와 8을 곱해도 a와 b의 범위내에 들어오네요.

Big O(time)

Big O(memory)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXN = 200 * 1000 * 1000 + 1;
using namespace std;
bool era[MAXN];
void precalc(){
    memset(era, true, sizeof(era));
    for(int i=2; i * i <= MAXN; i++){
        if(era[i]){
            for(int j = i+i; j <= MAXN; j+=i){
                era[j] = false;
            }
        }
    }
}
void process(){
    precalc();
    int n; cin >> n;
    if(n%2 == 0){
        if(n == 2) cout << "6 4" << endl;
        else cout << n+4<<" 4" << endl;
    }else{
        for(int a = n+4; a < MAXN; a += 2)
            if(!era[a]){
                cout << a << " " << a-n << endl;
                return;
            }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

Problem B : Modulo Equality

• level : 1500
• tag : brute force, sortings
• time : 01:58

Point

• digit으로만 이루어진 배열 2개를 입력받습니다.
• 또한, modulo 연산에 사용될 m도 입력받습니다.
• 배열 a 의 모든 원소에 x를 더한 후 모듈로 연산을 한 결과가 b가 되게 하고 싶습니다.
• 이때의 최소 x를 출력합니다.

Design(x)

• a와 b의 순서는 마음대로 섞을 수 있습니다.
• 따라서, 일단 map에 넣습니다.
• 그리고 시작점을 하나씩 밀어가면서 두 배열에 있는 원소의 갯수가 같은 지점을 찾습니다.
  • 각각의 원소가 같으면서, 모든 원소에 차를 더하고 모듈로 연산을 한 결과가 같다면,
  • 해당 x를 일단 ans리스트에 넣습니다.
• 결론적으로, ans 리스트에 있는 값중 가장 작은 값만 출력합니다.
• 5트 이상한 계기는, 위와 같이 ans리스트에 넣는 대신, 만족하는 x를 바로 출력하고 종료하였기 떄문입니다.

• 문제에도 나와있듯이, 가장 작은 x를 구하는 것이고, 제 로직상 바로 탈출하는 것이 가장 작은 x를 구하는 것이 아닌 경우가 있기 때문이라고 생각합니다.

• 다른 사람들 코드는 저와 다르고, 모두 비슷한 방법으로 풀었습니다.
• map을 사용하지 않고, b만 sort를 미리 진행합니다.
• 그리고 대조해보는 방법은 동일합니다.
• 하지만 동일하게, 만족하는 x를 찾자마자 종료하지 않고,
• 모두 탐색한 후 종료하였습니다.

Big O(time)

Big O(memory)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
//#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXN = 2000+1;
typedef long long ll;
using namespace std;

ll n, mod;
ll cnta, cntb;
map<ll,ll> mpa, mpb;
pair<ll,ll> pa[MAXN], pb[MAXN];
void input(){
    ll x;
    cin >> n >> mod;
    rep(i, 0, n){ cin >> x; mpa[x]++; }
    rep(i, 0, n){ cin >> x; mpb[x]++; }
    for(auto y : mpa) pa[cnta++] = {y.first, y.second};
    for(auto y : mpb) pb[cntb++] = {y.first, y.second};
}
void process(){
    input();
    vector<ll> ans;
    int sta = 0;
    for(int stb = 0; stb < cntb; stb++, sta = 0){
        int i = sta;
        int j = stb;
        bool found = true;
        for(int cnt = 0; cnt < cntb; cnt++){
            if(pa[i].second != pb[j].second){
                found = false;
                break;
            }
            i++; j = (j+1) % cntb;
        }
        if(found){
            int l = sta, k = stb;
            ll gap = (pb[stb].first - pa[sta].first + mod) %mod;
            for(int cnt = 0; cnt < cntb; cnt++){
                if((pa[l].first + gap) % mod != pb[k].first){
                    found = false;
                    break;
                }
                l++; k = (k+1) % cntb;
            }
            if(found){
                ans.push_back(gap);
//                cout << gap << endl;
//                return;
            }
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans[0] << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

Problem C : Long Beautiful Integer

• level : 1700
• tag : greedy, implementation
• COFO에는, 이처럼 사전순 관련 문제가 많이 나오는 것 같습니다.
  • ‘9’ 의 다음은 ‘0’이어야 한다는 사실을 유의해야겠습니다.

Point

• n 과 k가 주어집니다.
• 길이 n짜리 string이 주어집니다.
• string의 k번째 원소마다 모두 같은 값을 가지게 하려 합니다.
  • b1, b2, …, bm 일때 b_i = b_i+k (1<=i<=m-k)를 만족하도록 말입니다.
• 이때 가능하면 가장 작은 b를 찾아서 출력하는 문제입니다.

Design(x)

• 사전순으로 가장 작은 수를 찾아야하고,
• k개의 수가 반복됩니다.
• 따라서, 앞에 있는 k개를 제외하고 뒤는 신경쓸 필요가 없습니다.
• 또한, 가장 작은 수를 찾아야 하므로,
• k-1부터 0번지까지 순서로, 즉 뒤에서부터 앞으로 오는 순서로 탐색해야 합니다.
  • 탐색 과정중 ‘9’가 아닌 원소가 있다면 1증가시키고 종료
  • ‘9’라면 ‘0’으로 바꿔주기
  • 조금 어이없는 풀이이지만, 사전순이기에 가능합니다.
  • 이미 만족하지 않는 상태이므로,
    • 제일 작은 자리에 있는 수를 1증가시켜주면 됩니다.
    • 단, 해당 수가 9인 경우 1을 증가해서 0을 만들면 값이 더 작아지기 때문에 종료하면 안됩니다.
• 단, 처음부터 이미 조건을 만족하는 수를 만들 수 있는 경우는 미리 제외해줍니다.

Big O(time)

Big O(memory)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
using namespace std;
void process(){
    int n, k; cin >> n >> k;
    string a, ans; cin >> a;
    rep(i, 0, n) ans += a[i%k];
    if(a > ans){
        r_rep(i, k-1, -1){
            if(ans[i] < '9'){
                ans[i]++;
                break;
            }else ans[i] = '0';
        }
        rep(i, 0, n) ans[i] = ans[i%k];
    }
    cout << n << endl;
    cout << ans << endl;

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}