(2020년 10월 21일에 작성한 글입니다.)
Dashboard - Codeforces Round #677 (Div. 3) - Codeforces
codeforces.com
Div.3여서 너무 안일하게 생각했다
A.
x가 하나의 숫자로만 이루어진 수임이 보장되니까
일단 x % 10 - 1까지는 10번 누른거니까 (x % 10 - 1) * 10를 더해야 한다.
그리고 x가 몇 자리 수인지를 구해서 1 ~ 거기까지 더하면 된다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int ans;
int i;
cin >> T;
while (T--) {
cin >> N;
ans = (N % 10 - 1) * 10;
for (int digit = 1, i = 1; ; i++, digit *= 10) {
if (N / digit) {
ans += i;
}
else {
break;
}
}
cout << ans << '\n';
}
return 0;
}
B.
여기서 시간을 많이 쓴 게 아쉽다.
flag를 막 체크하면 될 것 같았는데 그게 안되서
생각해보니까 1들 사이에 있는 0의 개수를 다 더하는거라서
1의 인덱스를 다 저장해놓고
for(i = 1; i < idx.size(); i++)동안
idx[i] - idx[i - 1] - 1를 더해줬다.
그러면 붙어있는 친구들에 대해서는 계속 0이 더해질테니까
그렇게 처리가 된다...
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int ans;
int temp;
int i;
cin >> T;
while (T--) {
cin >> N;
vector<int> index;
for (i = 0; i < N; i++) {
cin >> temp;
if (temp) {
index.push_back(i);
}
}
ans = 0;
for (i = 1; i < index.size(); i++) {
ans += index[i] - index[i - 1] - 1;
}
cout << ans << '\n';
}
return 0;
}
C.
priority queue의 maxheap에 pair<값, 인덱스>를 넣어뒀다.
근데 지금 보니까 굳이 priority queue일 필요는 없었고 그냥 정렬 했으면 됐다...
여튼
값이 최대일 때 이게 dominant 피라냐가 될 가능성이 크니까
큰 친구부터
다시 생각해보니까
최댓값을 갖는 곳들에서만 확인해보면 된다...
만약
지금 다시 생각해보니까
걍 다 같은 수이지만 않으면
최댓값 중에서 양쪽에 하나라도 작은거 있는 인덱스를 출력하면 된다
ㅎㅎㅎ
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
bool flag;
int i;
cin >> T;
while (T--) {
cin >> N;
vector<int> arr(N + 2, 0);
flag = true;
for (i = 1; i <= N; i++) {
cin >> arr[i];
if (arr[i] != arr[1]) {
flag = false;
}
}
if (flag) {
cout << -1 << '\n';
continue;
}
int max_ = *max_element(arr.begin(), arr.end());
arr[0] = arr[N + 1] = int_inf;
for (i = 1; i <= N; i++) {
if (arr[i] == max_) {
if (arr[i] > arr[i - 1] || arr[i] > arr[i + 1]) {
cout << i << '\n';
break;
}
}
}
}
return 0;
}
D.
개수가 가장 작은 수를 루트로 두고
그것과 다른 수들을 자식으로 두고
그것과 같은 것들 중 남은 건 루트의 자식의 자식으로 두면 된다
다양한 이유로 여러번 틀렸는데
1. 중간에 배열을 정렬하는 부분이 나오는데
답을 출력할 때는 처음 배열에서의 인덱스가 필요하기 때문에
그걸 미리 따로 저장해놓아야 한다.
2. 그래서 그걸 저장하는 배열을 만들었는데
루트와 동일한 수를 자식의 자식으로 연결할 때
cout << forCheck[i].second + 1 << ' ' << forCheck[min_idx].second + 1 + cnt++ << '\n';이렇게 했는데,
방금 말했듯이... 처음 배열에서의 인덱스가 필요하기 때문에
forCheck[min_idx].second + 1 + cnt++가 아니라
forCheck[min_idx + cnt++].second + 1을 출력해야 한다..
E.
D가 막혀서 그 전에 E부터 풀었는데
nC(n/2) * 1/2 * (n/2 - 1)! * (n/2 - 1)!
원순열과 조합을 적절히 섞으면 됐던 문제...
관건은 이걸 long long 범위 안에서 구현하는거였다....
정수론을 잘 몰라서 구현으로 풀었다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
ll N;
ll ans;
ll i;
cin >> N;
ans = 1;
bool flag = false;
for (i = 1; i <= N - 1; i++) {
ans *= i;
if (ans % N == 0 && flag==false) {
ans /= N;
flag = true;
}
}
ans *= 2;
if (flag == false) {
ans /= N;
}
cout << ans << '\n';
return 0;
}