(2021년 1월 14일에 작성한 글입니다.)
Standings - Codeforces Round #553 (Div. 2) - Codeforces
codeforces.com
번개 버추얼을 돌았다
결과는 2솔
A.
그냥 구현하면 된다.
나는 두 알파벳 사이의 거리를 구하는 함수를 만들어서
substring과 ATCG와 비교하여 각각의 거리를 더했고
그 중에 최솟값을 찾았다.
int diff(char a, char b)
{
return min({ abs(a - b), abs(a + 26 - b), abs(b + 26 - a) });
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N;
string s;
int i, j;
int cnt, ans = INT_MAX;
string comp = "ACTG";
cin >> N >> s;
for (i = 0; i + 3 < N; i++) {
cnt = 0;
for (j = 0; j < 4; j++) {
cnt += diff(comp[j], s[i + j]);
}
ans = min(ans, cnt);
}
cout << ans;
return 0;
}
B.
음... 못 풀어서 풀이를 봤다.
처음에는 첫 번째 줄과 비교했을 때
다른 줄에 다른 수가 있으면 그냥 되는 줄 알았다
그런데 반례는
3 1
5
3
6
이런식으로 XOR 연산한 결과와 다른 값을 또 연산했을 때 0이 나올 수 있다.
풀이는 이런식이었는데
모든 행의 최솟값을 다 XOR 연산해보고
만약 그 결과가 0이 아니라면 그 수들의 인덱스를 출력하면 되고,
만약 0이 아니라면, 최솟값 외에 다른 수가 존재하는 행이 하나라도 있으면
그 행은 최솟값이 아니라 그 수로 연산을 하면 결과가 0이 아니게 나오고
만약 그런 행이 없다면 가능한 경우가 없는거다.
어떤 수를 0과 XOR 연산 하면 값이 바뀌지 않는다.
그리고 동일한 두 수를 XOR 연산하면 0이 나온다.
그렇기 때문에, 앞서 말한, 최솟값 외에 다른 수가 존재하는 행을 i번째 행, 그 행의 최솟값을 k라고 할 때
i번째 행을 제외한 모든 행들의 최솟값을 XOR 한 결과는 k일 것이다.
그리고 i 번째 행의 k가 아닌 수와 k를 XOR 하면 0이 아니다...
신기하다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M;
int result = 0;
int i, j;
cin >> N >> M;
vector<map<int, int>> arr(N + 5);
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
int a; cin >> a;
arr[i].insert({ a, j });
}
}
for (i = 1; i <= N; i++) {
result ^= (arr[i].begin())->first;
}
if (result != 0) {
cout << "TAK" << ENDL;
for (i = 1; i <= N; i++) {
cout << arr[i].begin()->second << ' ';
}
cout << ENDL;
return 0;
}
int chk = -1;
for (i = 1; i <= N; i++) {
if (arr[i].size() != 1) {
chk = i;
break;
}
}
if (chk == -1) {
cout << "NIE" << ENDL;
return 0;
}
cout << "TAK" << ENDL;
for (i = 1; i <= N; i++) {
if (i == chk) {
arr[i].erase(arr[i].begin()->first);
}
cout << arr[i].begin()->second << ' ';
}
return 0;
}
C.
이건 뭔가 풀 수 있을 거 같았는데 결국 시간 안에는 못 푼 문제다.
그래서 나중에 풀었다.
근데 되게 복잡하게 구현했다.
홀/짝이 더해지는 구간마다 등차수열의 합 공식((첫 항 + 끝 항) * 항 개수 / 2)을 이용해서
구간의 합을 구하고, 그걸 전체 sum에 더했는데
다른분들의 풀이를 보니까 정말 놀라웠다
합은 나중에 한꺼번에 구하면 되니까,
그냥 홀수/짝수가 각각 몇 번 등장하는지만 구하면 된다.
그리고 마지막에 그걸 이용해서 홀수들끼리/짝수들끼리의 합을 구하면 되니까...
신기가 방기다
ll solve(ll end)
{
ll i, digit;
ll odd_start = 1, even_start = 2;
bool odd_turn = true;
ll ret = 0;
for (i = 1, digit = 1; i + digit <= end; i += digit, digit *= 2)
{
if (odd_turn) {
ret += ((odd_start + digit - 1) % MOD) * (digit % MOD);
ret %= MOD;
odd_start += digit * 2;
}
else {
ret += ((even_start + digit - 1) % MOD) * (digit % MOD);
ret %= MOD;
even_start += digit * 2;
}
odd_turn = !odd_turn;
}
if (odd_turn) {
ret += ((odd_start + end - i) % MOD) * ((end - i + 1) % MOD);
ret %= MOD;
}
else {
ret += ((even_start + end - i) % MOD) * ((end - i + 1) % MOD);
ret %= MOD;
}
return ret % MOD;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll L, R;
cin >> L >> R;
cout << (solve(R) - solve(L - 1) + MOD) % MOD << ENDL;
return 0;
}
D.
a >= b일때 식을 정리하면 (a-b)*(j-1)+b*n 이고
a < b일때는 a*n + (b - a) * (n - j), 정리하면 a * n + (a - b) * (j - n)
이런식으로 해서
ans에 min(a, b) * (n - 1)을 저장해놓고,
a - b를 diff라는 벡터에 저장해놓고
오름차순 정렬해서
i는 0부터 n - 1까지 증가, j는 n부터 1까지 감소할 때
diff[i] < 0이면 ans에 diff[i] * (j - n)를 더하고
아니면 diff[i] * (j - 1)을 더했다...
근데 이것도
a, b간의 대소관계에 따라 케이스를 나눌 필요가 없다.
그냥 식을 정리하면 (a - b) * (j - 1) + b * (n - 1)인걸...
그리고 a - b값을 정렬한 뒤
작은 값에 큰 값을 매치해주면 된다....
신기가 방기다22...
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll N;
ll ans = 0;
int i;
ll j;
cin >> N;
ll a, b;
vector<ll> diff(N + 5);
for (i = 0; i < N; i++) {
cin >> a >> b;
ans += min(a, b) * (N - 1);
diff[i] = a - b;
}
sort(diff.begin(), diff.begin() + N);
for (i = 0, j = N; i < N; i++, j--) {
if (diff[i] < 0) {
ans += diff[i] * (j - N);
}
else {
ans += diff[i] * (j - 1);
}
}
cout << ans << ENDL;
return 0;
}