ABC 422
Table of Contents
https://atcoder.jp/contests/abc422
A. Stage Clear
https://atcoder.jp/contests/abc422/tasks/abc422_a
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int i, j;
char c;
cin >> i >> c >> j;
if (j == 8) {
i++;
j = 1;
} else {
j++;
}
cout << i << '-' << j << endl;
}
B. Looped Rope
https://atcoder.jp/contests/abc422/tasks/abc422_b
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int H, W;
cin >> H >> W;
vector<string> grid(H);
rep(i, H) cin >> grid[i];
vint di = {0, 1, 0, -1};
vint dj = {1, 0, -1, 0};
int ok = 1;
rep(i, H) rep(j, W) {
if (grid[i][j] == '.') continue;
int cnt = 0;
rep(d, 4) {
int ni = i + di[d], nj = j + dj[d];
if (clamp(ni, 0, H - 1) != ni || clamp(nj, 0, W - 1) != nj) continue;
if (grid[ni][nj] == '#') cnt++;
}
if (cnt == 2 || cnt == 4) continue;
ok = 0;
}
yesno(ok);
}
C. AtCoder AAC Contest
https://atcoder.jp/contests/abc422/tasks/abc422_c
二分探索で解ける。
はじめ $m = \min(n_A, n_C)$ としたとき、$\min(m, n_A + n_B + n_C - 2m)$ で良いと思ったが (3, 1, 3) のとき答えは2であるが(ABC, AAC など)、1となってしまった。
二分探索で作れる上限の探索すれば良かった。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
ll na, nb, nc;
cin >> na >> nb >> nc;
ll ac = 0, wa = min(na, nc) + 1;
while (wa - ac > 1) {
ll wj = (wa + ac) / 2;
ll ta = na, tb = nb, tc = nc;
ta -= wj, tc -= wj;
if (ta >= 0 && tb >= 0 && tc >= 0 && ta + tb + tc >= wj) {
ac = wj;
} else {
wa = wj;
}
}
cout << ac << endl;
};
int t;
cin >> t;
rep(i, t) cal();
}
D. Least Unbalanced
https://atcoder.jp/contests/abc422/tasks/abc422_d
アンバランスさは 0 または 1 である。 $K$ が $2^N$ の倍数のときは各要素を $K/2^N$ にすればアンバランスさ 0 を達成できる。
それ以外のときは下記のセグメント木のように $K$ を左右に分割していけば良い。
-----------------
| |
-----------------
| | |
-----------------
| | | | |
-----------------
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, K;
cin >> N >> K;
ll twop = 1ll << N;
vll A(twop);
auto f = [&](auto f, ll l, ll r, ll rem) -> void {
if (r - l == 1) {
A[l] = rem;
return;
}
ll m = (l + r) / 2;
f(f, l, m, rem / 2);
f(f, m, r, rem - rem / 2);
};
f(f, 0, twop, K);
ll mx = *max_element(all(A));
ll mi = *min_element(all(A));
cout << mx - mi << endl;
print(A);
}
E. Colinear
https://atcoder.jp/contests/abc422/tasks/abc422_e
解説 AC
解析的に解くのかと思ったらまさかの乱択アルゴリズムだった。
class XorShift32 {
public:
explicit XorShift32(uint32_t seed = 2463534242U) : state(seed) {}
uint32_t next() {
uint32_t x = state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
state = x;
return x;
}
private:
uint32_t state;
};
struct Point {
ll x, y;
};
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vector<Point> pts;
rep(i, N) {
ll x, y;
cin >> x >> y;
pts.push_back({x, y});
}
auto f = [](Point p, Point q) -> tuple<ll, ll, ll> {
ll a = q.y - p.y;
ll b = p.x - q.x;
ll c = -p.x * q.y + q.x * p.y;
return {a, b, c};
};
XorShift32 rng;
ll m = 100;
rep(_, m) {
ll p, q;
do {
p = rng.next() % N;
q = rng.next() % N;
} while (p == q);
auto [a, b, c] = f(pts[p], pts[q]);
ll cnt = 0;
rep(i, N) {
auto [x, y] = pts[i];
if (a * x + b * y + c == 0) cnt++;
}
if (cnt * 2 > N) {
Yes();
cout << a << ' ' << b << ' ' << c << endl;
return;
}
}
No();
}
F. Eat and Ride
https://atcoder.jp/contests/abc422/tasks/abc422_f