(2020년 12월 18일에 작성한 글입니다.)
Dashboard - Educational Codeforces Round 100 (Rated for Div. 2) - Codeforces
codeforces.com
A.
7의 배수번째에 올킬하기 때문에
7번의 작업에서 총 9를 죽이게 된다.
그래서 총 합이 9의 배수이면 YES, 아니면 NO 하려 했으나
총 합이 9의 배수라는 건
올킬을 sum / 9번 한다는건데
그러면 모든 값이 최소 sum / 9가 되어야 한다.
그래서 총 합이 9의 배수라도
min_element < sum / 9면 NO, 이것도 만족하면 YES다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int a, b, c;
cin >> T;
while (T--) {
cin >> a >> b >> c;
if ((a + b + c) % 9 != 0) {
cout << "NO" << '\n';
}
else {
if (min(a, min(b, c)) >= (a + b + c) / 9) {
cout << "YES" << '\n';
}
else {
cout << "NO" << '\n';
}
}
}
return 0;
}
B.
진짜......ㅋㅋㅋㅋㅋㅋㅋ
너무 어려워서 약간 멘붕 왔고
어떡하지 막 그랬다...
근데 결과적으로...
풀이는 역시 코포식 사고에서 벗어나지 않았고...
두 가지 풀이가 있는데
일단 내가 한 방법은
여기 절댓값이 거슬려서, 만약 모든 i에 대해
a[i] > b[i]면 어떨까 생각해봤다
식을 정리하면 2S - 2(b[i]의 합) <= S 인거고
S <= 2 * (b[i]의 합) 이다.
여기서 왜 하필이면 2일까에 집중해봤는데...
만약 b[i]가 a[i]보다 작은, 가장 가까운 2의 거듭제곱수면
2 * b[i]는 항상 a[i]보다 크거나 같게 되고
그것들을 다 더하면 S보다 크다....
와 진짜 엄청난 문제다...
(더 엄청난 이유는 뒤에 또 나온다...)
Rebro님께서 쓰신, 블루, 퍼플 가는 방법에 대한 글(rebro.kr/72)에서
숫자에 집중해야 된다고 하신 게 기억에 남았는데
여기서도 왜 하필이면 2일까???!!!
라는 생각을 계속 했고
모든 일엔 다 이유가 있었던거다 역시...
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int i;
cin >> T;
while (T--) {
cin >> N;
vector<ll> arr(N + 5);
for (i = 0; i < N; i++) {
cin >> arr[i];
}
vector<ll> ans(N + 5, 1);
for (i = 0; i < N; i++) {
while (ans[i] * 2 < arr[i]) {
ans[i] *= 2;
}
}
for (i = 0; i < N; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
return 0;
}그리고 두 번째 풀이는
weasell님과 djs100201가 푼 방법
1, a[i]가 한 번씩 나오는 걸 반복하면 된다...
그래서 i가 짝수일 때, 홀수일 때 각각에 대해 a[i]들의 합을 따로 구해놓고
홀수번째 수들의 합 or 짝수번째 수들의 합 중에서 작은 값을 갖는 경우에 대해 b[i] = a[i] or b[i] = 1로 하면 된다.
(홀수번째 수들의 합이 더 작으면 b[i가 홀수] = a[i], b[i가 짝수] = 1
짝수번째 수들의 합이 더 작으면 b[i가 짝수] = a[i], b[i가 홀수] = 1)
왜 이게 성립할까 생각해봤는데
|a[i] - b[i]|가
b[i] == a[i] 인 경우에는 0이고
b[i] == 1인 경우에는 절댓값이 a[i] - 1인데
짝수번째 수들만 고르거나 홀수번째 수들만 고르는 두 가지 경우 중에서 전체 합이 작은 경우를 선택하기 때문에
다 더하면 그 차이의 2배는 S보다 무조건 작다...
와 진짜 엄청난 문제다 이건...
C.
사실 이건 다른 의미로 엄청 문제다
진짜 구현 너무 복잡했다.
맞았으니 다행인 문제.
나는 이거 TLE 날까봐
지금 수행하는 임무가 끝나는 시간을 저장해놓고
lower_bound로 그때까지 내가 무시하는 작업들을 찾고
거기까지 가면서 ans++ 해줘야 되는 부분 있는지 확인했는데
(이 부분이 진짜 너무 복잡했다)
weasell님 코드 보니까
인덱스 i에 대해서
그때 시간의 위치를 저장해놓으면 된다
......
너무 간단해졌다.
물론 구현은 복잡하겠지만
훨씬 간단한 아이디어다.....
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int i, j;
cin >> T;
while (T--) {
cin >> N;
vector<ll> time(N + 5), posi(N + 5);
for (i = 0; i < N; i++) {
cin >> time[i] >> posi[i];
}
ll cur_posi = 0, cur_time = 0;
int ans = 0;
for (i = 0; i < N;) {
if (cur_posi == posi[i]) {
ans++;
i++;
continue;
}
cur_time = time[i];
ll next_time = cur_time + llabs(cur_posi - posi[i]);
ll next_posi, dir;
int idx = lower_bound(time.begin(), time.begin() + N, next_time) - time.begin();
if (cur_posi > posi[i]) {
dir = -1;
}
else {
dir = 1;
}
next_posi = cur_posi;
for (j = i; j < idx - 1; j++) {
next_posi += dir * (time[j + 1] - time[j]);
if (min(cur_posi, next_posi) <= posi[j] && posi[j] <= max(cur_posi, next_posi)) {
ans++;
}
cur_posi = next_posi;
}
next_posi = posi[i];
if (min(cur_posi, next_posi) <= posi[idx - 1] && posi[idx - 1] <= max(cur_posi, next_posi)) {
ans++;
}
cur_posi = posi[i];
i = idx;
}
cout << ans << '\n';
}
return 0;
}