Codeforces Round #686 (Div.3)
A. Special Permutation
가 되지 않게 하는 순열을 출력하는 문제 ( ≤ ≤ )
그냥 2부터 까지 출력한 후 마지막에 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
유일하고 가장 작은 번호를 선택한 번째 참가자의 인덱스를 출력하는 문제
#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
배열 에서 가 등장한 횟수 + 1이 를 제외하고 모두 지우기 위한 실행 횟수이다.
예를들어, 배열 라고 하자.
먼저, 배열에 같은 숫자가 연속으로 나온 경우는 제외해야 하므로 다음과 같이 바꿔주자.
이제 배열에 속한 숫자마다 등장한 횟수를 세어보면 다음과 같다.
- 일 때 등장 횟수 3 → 필요한 실행 횟수 = 4
- 일 때 등장 횟수 5 → 필요한 실행 횟수 = 6
- 일 때 등장 횟수 2 → 필요한 실행 횟수 = 3
이때, 배열의 맨 앞에 위치한 숫자의 경우 더 앞은 지울 필요가 없고 맨 뒤에 위치한 숫자의 경우도 그 뒤의 숫자를 지울 필요가 없다. 그래서 맨 앞의 숫자와 맨 뒤의 숫자의 실행 횟수를 각각 -1해준다.
- 일 때 등장 횟수 3 → 필요한 실행 횟수 = 4
- 일 때 등장 횟수 5 → 필요한 실행 횟수 = 4
- 일 때 등장 횟수 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
입력된 정수 에 대해서 다음 조건을 만족하는 배열을 구하는 문제이다.
- 는 1보다 커야한다.
- 은 로 나눠질 수 있어야 한다.
- 는 최대로 가능한 수여야 한다.
먼저 의 소인수분해를 한 형태는 다음과 같다.
이때, 문제의 정답의 길이는 의 최대값을 넘지 못한다. 왜냐하면 문제의 3번 조건때문이다.
예를들어, 이 360이라 가정하자. 소인수분해를 한 결과는 다음과 같다.
여기서 4번 조건과 3번 조건으로 인해 2가 가장 많으므로 배열에는 모두 2의 배수여야 한다. 중간에 3이나 5가 나와버리면 3번 조건이 위배되기 때문이다.
그리고 2의 배수는 2가 될 수 있기 때문에 최대한 늘리기 위해서는 2를 연속으로 사용해야 한다.
이런방식으로 다음의 과정을 거칠 수 있다.
따라서, 정답은 [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;
}
Author And Source
이 문제에 관하여(Codeforces Round #686 (Div.3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@emeraldgoose/cf686div3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)