ARC 197
Table of Contents
A. Union of Grid Paths
https://atcoder.jp/contests/arc197/tasks/arc197_a
条件より $X$ は左上から右下への経路になる。考えうる経路で1度でも通るマスの数を求める問題。
到達するマスの下限となる経路は ? において D が選択できるならば選択し、そうでなければ R を選択した経路である。
上限となる経路は ? において R が選択できるならば選択し、そうでなければ D を選択した経路である。
左上から 1 step ずつ上限・下限の経路で進めていたときの座標をそれぞれ $(h_u, w_u)$, $(h_l, w_l)$ とすると $h_l - h_u = w_u - w_l$ となっている。
$d = h_l - h_u$ とすると、途中の ? の選択の仕方で $(h_l, w_l), (h_{l}-1, w_{l}+1), \cdots, (h_{l}-d, w_{l}+d) = (h_u, w_u)$ の $d+1$ 個のマスを黒く塗ることができる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
int H, W;
string S;
cin >> H >> W >> S;
int ld = 0, rr = 0;
for (char c : S) {
if (c == 'D')
ld++;
if (c == 'R')
rr++;
}
ll ans = 1;
int l = 0, r = 0;
for (char c : S) {
if (c == 'D') {
l++;
r++;
}
if (c == '?') {
if (ld < H - 1) {
ld++;
l++;
}
if (rr < W - 1) {
rr++;
} else {
r++;
}
}
ans += l - r + 1;
}
cout << ans << endl;
};
int t;
cin >> t;
rep(i, t) {
cal();
}
}
B. Greater Than Average
https://atcoder.jp/contests/arc197/tasks/arc197_b
要素を追加したときに平均値が下がるか上がるかということに着目すると、小さい順に要素を追加していって平均以上の数の個数を二分探索すれば良さそうだと気づけた。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
int N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
sort(all(A));
ll sum = 0;
ll ans = 0;
vll track;
rep(i, N) {
sum += A[i];
auto it = upper_bound(A.begin(), A.begin() + i + 1, sum / (i + 1));
ll num = distance(it, A.begin() + i + 1);
chmax(ans, num);
}
cout << ans << endl;
};
int t;
cin >> t;
rep(i, t) {
cal();
}
}
模範解答は尺取り方で平均以上の個数を求めていた。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
int N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
sort(all(A));
ll sum = 0;
ll ans = 0;
ll k = 0;
rep(i, N) {
sum += A[i];
ll n = i + 1;
while (k < N && A[k] * n <= sum) {
// 平均以下の A[k]
k++;
}
chmax(ans, n - k);
}
cout << ans << endl;
};
int t;
cin >> t;
rep(i, t) {
cal();
}
}
C. Removal of Multiples
https://atcoder.jp/contests/arc197/tasks/arc197_c
D. Ancestor Relation
https://atcoder.jp/contests/arc197/tasks/arc197_d