Educational Codeforces Round 145 (Rated for Div. 2)
A. Garland (800)
A. Garland
4개가 모두 같으면 끌 수 없고, 3개가 같으면 6번이 필요하다.
그 이외의 경우엔 모두 4번만 써서 전구를 끌 수 있다.
B. Points on Plane (1000)
B. Points on Plane
계속해서 정사각형 모양으로, 혹은 기울어진 정사각형 모양으로 채워나가면
1 ~ 1 => 0
2 ~ 4 => 1
3 ~ 9 => 2
...
처럼 가는것을 알 수 있고, 이건 결국 $\sqrt{N-1}$ 이다.
근데 $\sqrt{10^{18}-1}$ 이 $999,999,999$ 로 계산이 안되는 문제가 있으니 sqrt 내장함수를 써서 구현하면 틀린다.
C. Sum on Subarrays (1500)
C. Sum on Subarrays
무조건 특정 인덱스 $i$ 에서 오른쪽으로 이어지는 구간만 본다고 하자.
$n=10,k=10$ 이면
1000 -1 -1 -1 -1 -1 -1 -1 -1 -1
처럼 하면 $k=10$ 이 된다.
만약 $k=19$ 라면
1000 1000 -1 -1 -1 -1 -1 -1 -1 -1
처럼 된다.
가다가 이제 가장 왼쪽에 붙이는것이 불가능할 때는, 무조건 -1 로 된 부분 안에 양수를 넣을 수 있는 곳이 있다.
$k=0$ 이면 그냥 나머지를 $-1$로 채우고 종료해줘야 한다.
거기에 넣는다고 해보자.
1000 1000 음수 음수 음수 음수 음수 양수 -1 -1
이런식으로 만들어 줄 수 있는데, 음수 6개가 1000 이상이면 왼쪽 1000이랑 합쳤을 때 양수가 안되므로 저 음수의 값은 대략
$\left\lfloor \dfrac {1000-1}6 \right\rfloor=166$ 정도로 잡고 $-166$ 으로 채워주는 것이다.
그럼 이제 양수의 값은 $-166$ 보다 절대값이 작은 $-165$ 정도로 채워주면, 정답을 완성했다.
void solve() {
int n, k;
cin >> n >> k;
vi ans(n + 1);
for (int i = 1; i <= n; i++) {
int right = n - i + 1;
if (k >= right) {
ans[i] = 1000;
k -= right;
} else {
if (k == 0) {
for (int j = i; j <= n; j++) ans[j] = -1;
break;
}
int minus_len = n - k - i + 1;
int minus_num = 999 / minus_len;
for (int j = i; j < min(n - k + 1, n + 1); j++) {
ans[j] = -minus_num;
}
ans[n - k + 1] = minus_num - 1;
for (int j = n - k + 2; j <= n; j++) {
ans[j] = -1;
}
break;
}
}
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
cout << endl;
}
D. Binary String Sorting (1800)
D. Binary String Sorting
연산 자체의 가격이 훨씬 크므로 연산의 횟수를 줄이는데 먼저 집중한다.
swap 연산을 delete 연산 이후로 하는것은 최적이 아니므로, delete 연산부터 한다.
따라서 몇개의 element들을 먼저 지우고 swap으로 sorting을 한다.
$DDDD \to SSSSS$
swap을 해야하는 횟수는 inversion의 개수와 같다.
예를 들어,
일 때, 2번이다.
여기서 inversion의 개수가 1보다 크다면, 최소 2번의 swap이 일어나야 하기 때문에 그 원소를 그냥 지우는게 더 최적이다.
따라서 최적화된 연산의 순서에서 swap은 최대 한 번이 나온다.
나머지는 모두 삭제하는 연산이다.
만약에 모든 연산이 삭제하는 연산이라면, 우리는 $00000\cdots1111$ 중 가장 긴 것을 찾아야 한다.
이걸 위해, 마지막 문자열에 존재할 $0$의 개수들을 모두 순회해본다.
이건 prefix sum을 잘 활용하면 찾을 수 있다.
만약 우리가 swap 연산을 한 번 포함하려고 할 경우, $s_i=1,~s_{i+1}=0$ 인 pair에 있어 한번 swap 해주고 그 지점 좌우로 왼쪽, 오른쪽에 0의 개수와 1의 개수를 세주는 것으로 충분하다.
주의해야 할건, swap을 할 것이라면 무조건 $0000\cdots1111$ 와 같은 형태이지만, 지우기만 할거라면
$11111$ or $00000$ 같은 형태도 고려해주어서 가장 최소값을 찾아주어야 한다는 점이다.
void solve() {
string s;
cin >> s;
if (cntt(s, s[0]) == sz(s)) {
cout << 0 << endl;
return;
}
int n = sz(s);
vi zsum_left(n + 1), osum_right(n + 1);
zsum_left[0] = s[0] == '0' ? 1 : 0;
osum_right[n - 1] = s[n - 1] == '1' ? 1 : 0;
for (int i = 1; i < n; i++) zsum_left[i] = zsum_left[i - 1] + (s[i] == '0');
for (int i = n - 2; i >= 0; i--) osum_right[i] = osum_right[i + 1] + (s[i] == '1');
int ans = 1e9;
int swap_ans = 1e9;
for (int i = 0; i < n; i++) {
int left_len = i + 1;
int left_zero = zsum_left[i];
int left_one = left_len - left_zero;
int right_len = n - left_len;
int right_one = osum_right[i + 1];
int right_zero = right_len - right_one;
int delete_cnt = min({left_one + right_zero, left_zero + right_zero, left_one + right_one});
ans = min(ans, delete_cnt);
}
for (int i = 0; i < n - 1; i++) {
if (s[i] == '1' && s[i + 1] == '0') {
int left_len = i;
int left_zero = i == 0 ? 0 : zsum_left[i - 1];
int left_one = left_len - left_zero;
int right_len = n - left_len - 2;
int right_one = osum_right[i + 2];
int right_zero = right_len - right_one;
int delete_cnt = min({left_one + right_zero});
swap_ans = min(swap_ans, delete_cnt);
}
}
const int offset = 1e12;
if (ans <= swap_ans) {
cout << int(ans * offset + ans) << endl;
} else {
cout << int((swap_ans + 1) * offset + swap_ans) << endl;
}
}
E. Two Tanks (2400)
E. Two Tanks
F. Traveling in Berland (2500)
F. Traveling in Berland
G. Prediction (2800)
G. Prediction
Comments