Codeforces Round 686 (Div.3)

A. Special Permutation

$p_i=i$가 되지 않게 하는 순열을 출력하는 문제 ($1$ ≤ $i$ ≤ $n$)

그냥 2부터 $n$까지 출력한 후 마지막에 1을 출력하면 된다.

#include <iostream>
using namespace std;

int main() {
  int t;
  cin>>t;
  while(t--) {
    int n;
    cin>>n;
    for(int i=2;i<=n;i++) cout<<i<<' ';
    cout<<1<<endl;
  }

  return 0;
}

---

B. Unique Bid Auction

유일하고 가장 작은 번호를 선택한 $i$번째 참가자의 인덱스를 출력하는 문제

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int t;
  cin>>t;
  while(t--) {
    int n;
    cin>>n;
    vector<int> cnt(n+1), idx(n+1);
    for(int i=0;i<n;i++) {
      int x;
      cin>>x;
      cnt[x]++;
      idx[x]=i+1;
    }
    int ans=-1;
    for(int i=0;i<=n;i++) {
      if(cnt[i]==1) {
        ans=idx[x];
        break;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

---

C. Sequence Transform

배열 $a$에서 $a_i$가 등장한 횟수 + 1이 $a_i$를 제외하고 모두 지우기 위한 실행 횟수이다.

예를들어, 배열 $a = [2, 2, 1, 2, 3, 2, 1, 2, 3, 1, 2]$라고 하자.

먼저, 배열에 같은 숫자가 연속으로 나온 경우는 제외해야 하므로 다음과 같이 바꿔주자.

$a = [2,1,2,3,2,1,2,3,1,2]$

이제 배열에 속한 숫자마다 등장한 횟수를 세어보면 다음과 같다.

• $a_i=1$ 일 때 등장 횟수 3 → 필요한 실행 횟수 = 4
• $a_i=2$일 때 등장 횟수 5 → 필요한 실행 횟수 = 6
• $a_i=3$일 때 등장 횟수 2 → 필요한 실행 횟수 = 3

이때, 배열의 맨 앞에 위치한 숫자의 경우 더 앞은 지울 필요가 없고 맨 뒤에 위치한 숫자의 경우도 그 뒤의 숫자를 지울 필요가 없다. 그래서 맨 앞의 숫자와 맨 뒤의 숫자의 실행 횟수를 각각 -1해준다.

• $a_i=1$ 일 때 등장 횟수 3 → 필요한 실행 횟수 = 4
• $a_i=2$일 때 등장 횟수 5 → 필요한 실행 횟수 = 4
• $a_i=3$일 때 등장 횟수 2 → 필요한 실행 횟수 = 3

따라서, 최소 실행 횟수는 3이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int t;
  cin>>t;
  while(t--) {
    int n;
    cin>>n;
    vector<int> a;
    vector<int> res(n+1,1); // n개의 배열로 잡고 1로 초기화
    for(int i=0;i<n;i++) {
      int x;
      cin>>x;
      a.push_back(x);
    }
	
    // 입력 받을 때 연속인 숫자를 제외해서 받아도 된다.
    n=unique(a.begin(),a.end())-a.begin(); 
    a.resize(n);

    for(int i=0;i<n;i++) res[a[i]]++;
    // a배열의 맨 앞 숫자와 맨 뒤 숫자의 실행 횟수 -1
    res[a[0]]--;
    res[a[n-1]]--;

    int ans=1e9; // 충분히 큰 수
    for(int i=0;i<n;i++) ans=min(ans, res[a[i]]);

    cout<<ans<<endl;
  }
  return 0;
}

---

D. Number into Sequence

입력된 정수 $n$에 대해서 다음 조건을 만족하는 $a$배열을 구하는 문제이다.

1. $a_i$는 1보다 커야한다.
2. $a_1 \cdot a_2 \cdot a_3 \cdot…\cdot a_k=n$
3. $a_{i+1}$은 $a_i$로 나눠질 수 있어야 한다.
4. $k$는 최대로 가능한 수여야 한다.

먼저 $n$의 소인수분해를 한 형태는 다음과 같다.

$n = p_1^{b_1} \cdot p_2^{b_2} \cdot … \cdot p_k^{b_k}$

이때, 문제의 정답의 길이는 $b_i$의 최대값을 넘지 못한다. 왜냐하면 문제의 3번 조건때문이다.

예를들어, $n$이 360이라 가정하자. 소인수분해를 한 결과는 다음과 같다.

• $360=2^3\cdot3^2\cdot5$

여기서 4번 조건과 3번 조건으로 인해 2가 가장 많으므로 $a$배열에는 모두 2의 배수여야 한다. 중간에 3이나 5가 나와버리면 3번 조건이 위배되기 때문이다.

그리고 2의 배수는 2가 될 수 있기 때문에 최대한 늘리기 위해서는 2를 연속으로 사용해야 한다.

이런방식으로 다음의 과정을 거칠 수 있다.

• $a=[2,2,2]$
• $a=[2,2,2\cdot3^2]$
• $a=[2,2,2\cdot3^2\cdot5]=[2,2,90]$

따라서, 정답은 [2, 2, 90]이다.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
  int t;
  cin>>t;
  while(t--) {
    ll n;
    cin>>n;
    vector<pair<int,ll> > val;
    for(ll i=2; i*i<=n;i++) { // 소인수분해
      int cnt=0;
      while(n%i==0) {
        cnt++;
        n/=i;
      }
      if(cnt>0) val.push_back({cnt, i}); // (지수, 약수)
    }
    if(n>1) val.push_back({1, n});

    sort(val.rbegin(), val.rend()); // 가장 많은 약수가 앞으로 정렬

    vector<ll> ans(val[0].first, val[0].second);
    for(int i=1;i<val.size();i++) {
      for(int j=0;j<val[i].first;j++) ans.back()*=val[i].second;
    }

    cout<<ans.size()<<endl;
    for(auto it : ans) cout<<it<<' ';
    cout<<endl;
  }
  return 0;
}