Codeforces Round #686 (Div. 3) 풀이

A. Special Permutation

문제: codeforces.com/contest/1454/problem/A

• 2부터 n까지 출력하고, 마지막에 1 넣어주면 됨 ez

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string.h>
using namespace std;


int tc,n;

int main() {

    cin >> tc;

    while (tc--) {
        cin >> n;
       
        for (int i = 2; i <= n; i++) {
            cout << i << " ";
        }
        cout << "1\n";
    }

    return 0;
}

 

B. Unique Bid Auction

문제: codeforces.com/contest/1454/problem/B

• 중복 체크를 위해 정수형 visit 배열을 이용
• 지금껏 나오지 않았던 값들만 vector<pair<int,int>>에 넣음
• vector 정렬
• 앞에서부터 보면서 중복된 값이면 패스하고, 다음으로 작은 값 출력
• 다음으로 작은 값이 없으면 "-1" 출력

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string.h>
#include <queue>
#define INF 200001
using namespace std;


typedef pair<int, int> PI;

int tc,n;
int visit[INF];
//priority_queue<PI,vector<PI>,greater<PI>> participants;
vector<PI> participants;
int main() {

    cin >> tc;
    
    while (tc--) {
        cin >> n;

        memset(visit, 0, sizeof(visit));
        participants.clear();

        for (int i = 1; i <= n; i++) {
            int a;
            cin >> a;
            visit[a]++;
            if (visit[a] > 1) continue;
            participants.push_back({ a,i });
        }
        sort(participants.begin(), participants.end());

        bool isWinner = false;
        for (int i = 0; i < participants.size(); i++) {
            int val = participants[i].first;
            if (visit[val]>1) continue;

            cout << participants[i].second << '\n';
            isWinner = true;
            break;
        }
        if(!isWinner) cout << "-1\n";
    }

    return 0;
}

 

C. Sequence Transformation

문제: codeforces.com/contest/1454/problem/C

• 각 정수의 덩어리 개수를 셀 것이다.
• 예: 1 2 2 3 2 1 
  • 여기서 1 덩어리의 개수는 2
  • 2 덩어리의 개수는 2이다.
  • 즉, 스캔하면서 이전 값과 다른 경우 경우 패스하고 아니면 해당 값을 인덱스로 갖는 배열 값을 ++해준다.
  • 양 끝단에 위치하는 경우에는 -- 해준다.
• 양 끝단에 위치하는 경우 무시하는 이유
  • 덩어리 개수가 가장 작은 값을 x라고 해보자.
    • ~x~x~ => 결과: 3
    • x~x~ => 결과: 2
    • x~x => 결과: 1
    • 일반화: 결과 = (덩어리 개수+1) - (끝에 위치한 것 개수) 
• sequence 길이가 1인 경우는 따로 예외처리 해줬다.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string.h>
#include <queue>
#define INF 200001
using namespace std;


typedef pair<int, int> PI;

int tc,n;
map<int, int> cluster;


int main() {

    cin >> tc;
    while (tc--) {
        cin >> n;
        cluster.clear();
        int pre = -1,cur;
        for (int i = 0; i < n; i++) {
            cin >> cur;
            if (pre != cur) cluster[cur]++;
            if (i == 0 || i == n - 1) cluster[cur]--;
            pre = cur;
        }
        if (n == 1) cout << "0\n";
        else {
            int answer = n;
            for (auto& p : cluster) {
                answer = min(answer, p.second + 1);
            }
            cout << answer << '\n';
        }
    }
    
    return 0;
}

 

D. Number into Sequence

문제: codeforces.com/contest/1454/problem/D

• n을 소인수 분해한다. 
• 각 factor의 인자 값이 가장 큰 것의 인자값이 K(sequence의 길이)가 된다.
• K size 배열을 통해 출력할 sequence를 계산한다.
• 각 factor를 뒤에서부터 인자만큼 곱한다.
• 예: n=360
  • n = 360 = $2^3$x$3^2$x$5$
  • K = 3  <- 인자 값 중 3이 제일 큼
  • a = {1,1,1}로 초기화 <- K size 배열을 1로 초기화
  • 2가 3개 -> 뒤에서부터 2를 곱함(index: K, K-1, K-2)
    • a = {2, 2, 2}
  • 3이 2개
    • a = {2, 6, 6}
  • 5가 1개
    • a = {2, 6, 30}
  • 최종 결과: K=3, a={2, 6, 30}

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string.h>
using namespace std;


typedef long long ll;

int tc, K;
ll n,answerSeq[41];
map<ll, int> factors;

void factorize() {
    ll tmp = n;
    ll factor = 2;

    while (tmp > 1 && factor<=sqrt(tmp)) {
        if (tmp % factor == 0) {
            factors[factor]++;
            K = max(K, factors[factor]);
            tmp /= factor;
        }
        else factor++;
    }
    if (tmp > 1) {
        factors[tmp]++;
        K = max(K, factors[factor]);
    }
}

void createSeq() {
    //init
    K = 1;
    factors.clear();
    
    factorize();
    fill(answerSeq, answerSeq + K + 1, 1);

    for (auto &p : factors) {
        for (int i = K; i > K - p.second; i--) {
            answerSeq[i] *= p.first;
        }
    }
}
int main() {

    cin >> tc;
    while (tc--) {
        cin >> n;
        createSeq();
        cout << K << '\n';
        for (int i = 1; i <= K; i++) {
            cout << answerSeq[i] << " ";
        }
        cout << '\n';
    }

    return 0;
}

 

 

E. Number of Simple Paths

문제: codeforces.com/contest/1454/problem/E

 

 

 

 

 

 

ㅇ