Codeforces Round #686 (Div.3)

A. Special Permutation

pi=ip i=ipi=iの出力順序問題(111≦iiii≦nnn)
2からnnnまで出力し、最後に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

ユニークと最小の番号を選択したiii番目の参加者のインデックスを印刷する問題

#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

配列aaaにおいて、aia iaiが出現した回数+1は、aia iaiを除く全クリアの実行回数である.
例えば配列a=[2,2,3,2,1,2,3,1,2]a=[2,2,1,3,2,3,1,2,3,2,2,2,2,3,3,2,2,3,2,3,2,3,2,3,2,2,3,1,2,3,1,2,3,1,2,3,2,2,3,2,2,3,
まず、配列に同じ数値が連続して表示されている場合は除外する必要があります.したがって、次のように変更します.
a=[2,1,2,3,2,1,2,3,1,2]a = [2,1,2,3,2,1,2,3,1,2]a=[2,1,2,3,2,1,2,3,1,2]
次に、配列の各数値の出現回数を集計します.

ai=1 a i=1 ai=1で出現回数3→所要実行回数=4

ai=2 a i=2 ai=2で出現回数5→所要実行回数=6

ai=3 a i=3 ai=3の場合出現回数2→所要実行回数=3

この場合、一番前の数字は前に移動する必要はなく、一番後ろの数字も後ろの数字を削除する必要はありません.したがって、先頭の数字と先頭の数字の実行回数をそれぞれ−1に設定する.

ai=1 a i=1 ai=1で出現回数3→所要実行回数=4

ai=2 a i=2 ai=2で出現回数5→所要実行回数=4

ai=3 a i=3 ai=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

入力された整数nnnについて,以下の条件を満たすaaaアレイの問題を解く.

aia iaiは1より大きくなければなりません.

a1⋅a2⋅a3⋅...⋅ak=na_1\cdot a_2\cdot a_3\cdot...\cdot a_k=na1​⋅a2​⋅a3​⋅...⋅ak​=n

ai+1 a{i+1}ai+1はaia iaiに分けることができる必要があります.

kkkは最大限に付与しなければならない.

まずnnnの素数分解の形式は以下の通りである.
n=p1b1⋅p2b2⋅...⋅pkbkn = p_1^{b_1}\cdot p_2^{b_2}\cdot ...\cdot p_k^{b_k}n=p1b1​​⋅p2b2​​⋅...⋅pkbk​​
この場合,問題の正解長はbib ibiの最大値を超えてはならない.問題の3番目の条件のためです.
例えば、nnnは360であると仮定する.素数分解を行った結果は以下の通りである.

360=23⋅32⋅5360=2^3\cdot3^2\cdot5360=23⋅32⋅5

ここでは,4番条件と3番条件で2が最も多いため,aaa配列ではいずれも2の倍数である.中間に3か5が現れると、3番の条件は違反するからだ.
また、2の倍数は2でもよいので、最大限に増やすためには、2を連続して使うべきです.
このようにして、以下の過程を経験することができる.

a=[2,2,2]a=[2,2,2]a=[2,2,2]

a=[2,2,2⋅32]a=[2,2,2\cdot3^2]a=[2,2,2⋅32]

a=[2,2,2⋅32⋅5]=[2,2,90]a=[2,2,2\cdot3^2\cdot5]=[2,2,90]a=[2,2,2⋅32⋅5]=[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;
}