Codeforces Round #687 (Div.2)
어제 있었던 코드포스 라운드 687 풀이이다. 3솔브를 했고, D를 업솔브했다.
\(max( r + c - 2, m - r + c - 1,n - c + r - 1,m - r + n - c )\)가 답이다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while (T--) {
long long m, n, r, c;
cin >> m >> n >> r >> c;
long long mx = max({ r + c - 2, m - r + c - 1,n - c + r - 1,m - r + n - c });
cout << mx << '\n';
}
}
\(c_i \le 100\)이라는 점에 착안해, 답을 \([1, 100]\)의 한 정수로 고정하고, 모든 답에 대해 다 칠해보는 전략을 생각해볼 수 있다. 칠하는 것은 앞에서부터 탐색하며 칠하는 간단한 그리디로 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while (T--) {
long long N, K;
cin >> N >> K;
vector<long long> v(N);
for (auto &i : v)cin >> i;
int ans = 210000000;
for (int i = 1; i <= 100; i++) {
auto temp = v;
int cnt = 0;
for (int j = 0; j < N; j++) {
if (temp[j] != i) {
for (int k = 0; k < K; k++) {
if (j + k < N)temp[j + k] = i;
}
cnt++;
}
}
ans = min(ans, cnt);
}
cout << ans << '\n';
}
}
먼저, 맨 앞 블록을 삭제하고 뒤의 블록을 한 칸 씩 당겨오는 행동은 단순히 \(p\)를 \(1\) 증가시키는 것과 같다는 점을 관찰한다. 또한, \(p\)를 \(k\)번 증가시키면 설치해야 하는 블록의 개수는 증가시키기 전에서 맨 앞 블록을 신경쓰지 않는 것과 같다는 점도 관찰할 수 있다. 따라서, \(p_0 + ck\)인 모든 수에 대해 Prefix Sum을 이용하면 각 케이스를 \(O(1)\)에 판별 가능하다(단, \(c\)는 임의의 정수). 이것을, \(p \le p_0 < p+k\)에 대해서 반복하면 된다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while (T--) {
long long n, p, k, x, y;
cin >> n >> p >> k;
string s; cin >> s;
cin >> x >> y;
long long mn = 21000000000000000;
for (int i = 0; i < k; i++) {
long long init = i * y;
vector<int> psum0;
psum0.push_back(0);
for (int q = p + i - 1; q < n; q += k) {
psum0.push_back(psum0.back() + (s[q] == '0'));
}
for (int ind = 1; ind < psum0.size(); ind++) {
long long cost = init + (psum0.back() - psum0[ind - 1]) * x + y*k*(ind - 1);
mn = min(mn, cost);
}
}
cout << mn << '\n';
}
}
먼저, 두 가지 사실을 관찰할 수 있다.
1. 2진수의 자리수가 같은 두 수를 XOR하면 무조건 자리수가 줄어든다.
2. 답은 무조건 \([x, y], [y+1,z]\)의 연속된 두 구간을 각각 XOR했을 때 두 수가 대소관계가 바뀔 때만 나온다.
1번 조건으로부터, 같은 자리수가 3개 이상일 때 답이 무조건 \(1\)임을 알 수 있다. 따라서 \(N>30\)인 모든 케이스의 답은 무조건 \(1\)이다. 또한 2번 조건으로부터, \(N \le 30\)일 때 \(O(N^3)\) 또는 \(O(N^4)\) 솔루션을 얻을 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
long long N; cin >> N;
vector<long long>v(N), pw2(33);
long long k = 1;
for (int i = 0; i < 32; i++) {
pw2[i] = k; k <<= 1;
}
for (auto &i : v)cin >> i;
auto fd = [&](long long val)->long long {
for (int i = 31; i >= 0; i--) {
if (val >= pw2[i]) {
return i;
}
}
};
long long prev = fd(v[1]);
long long prev2 = fd(v[0]);
for (int i = 2; i < N; i++) {
long long cur = fd(v[i]);
if (prev == prev2 && prev == cur) {
cout << 1;
return 0;
}
prev2 = prev;
prev = cur;
}
long long ans = 2100000000;
for (int i = 0; i < N; i++) {
long long one = v[i];
for (int j = i; j < N; j++) {
for (int p = i + 1; p <= j; p++) {
one ^= v[p];
}
for (int k = j + 1; k < N; k++) {
long long two = v[k];
for (int p = k - 1; p >= j + 1; p--) {
two ^= v[p];
}
if (one > two) {
ans = min(ans, (long long)k - i - 1);
}
}
}
}
cout << (ans == 2100000000 ? -1 : ans);
}
여담.
D 풀이에 되게 근접했는데 틀려서 너무 아쉽다. 하지만 부계정도 블루에 안착시키는 데에 성공했다.
