ABC 257
Table of Contents
https://atcoder.jp/contests/abc257
A. A to Z String 2
https://atcoder.jp/contests/abc257/tasks/abc257_a
B. 1D Pawn
https://atcoder.jp/contests/abc257/tasks/abc257_b
C. Robot Takahashi
https://atcoder.jp/contests/abc257/tasks/abc257_c
D. Jumping Takahashi 2
https://atcoder.jp/contests/abc257/tasks/abc257_d
自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<tuple<ll, ll, ll>> nodes;
rep(i, N) {
ll x, y, P;
cin >> x >> y >> P;
nodes.emplace_back(x, y, P);
}
auto f = [&](ll x) -> bool {
rep(s, N) {
vector<bool> used(N);
used[s] = true;
queue<int> que;
que.push(s);
while (que.size()) {
int now = que.front();
que.pop();
rep(nx, N) {
if (nx == now) continue;
if (used[nx]) continue;
auto [xi, yi, pi] = nodes[now];
auto [xj, yj, pj] = nodes[nx];
if (pi * x >= abs(xi - xj) + abs(yi - yj)) {
used[nx] = true;
que.push(nx);
}
}
}
ll sum = accumulate(all(used), 0);
if (sum == N) return true;
}
return false;
};
ll ac = 0;
rep(i, N) rep(j, N) {
auto [xi, yi, pi] = nodes[i];
auto [xj, yj, pj] = nodes[j];
chmax(ac, abs(xi - xj) + abs(yi - yj));
}
ll wa = -1;
while (ac - wa > 1) {
ll wj = (ac + wa) / 2;
if (f(wj))
ac = wj;
else
wa = wj;
}
cout << ac << endl;
}
E. Addition and Multiplication 2
https://atcoder.jp/contests/abc257/tasks/abc257_e
F. Teleporter Setting
https://atcoder.jp/contests/abc257/tasks/abc257_f
G. Prefix Concatenation
https://atcoder.jp/contests/abc257/tasks/abc257_g
2026/2/9 Z algorithm 使うとわかった状態で自力 AC
z algorithm と https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ee で使ったような segment tree を組み合わせて解けた。
$S + \text{"\$"} + T$ を連結した文字列の Z algorithm を求めて、$T$ の各接頭辞が $S$ とどれだけ一致するかを調べる。 $T$ の部分だけを取り出して配列 $Z$ に格納する。("\$" を挟むことで $T$ の区間に長さ $|S|$ 以上の数値が出ないようにしている)
こうすると問題は次のように言い換えることができる。
位置 $i$ から $i + 1 \sim i + Z[i]$ までコスト 1 で遷移可能である。 位置 0 から出発し、位置 $N$ に到達する最小コストを求めよ。
後ろの位置から初めて、その位置から遷移可能な範囲の最小コストを segment tree で管理する。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string S, T;
cin >> S >> T;
int n = T.size();
vint Z;
{
vint tmp = z_algorithm(S + "$" + T); // T の区間に |S| 以上の長さが出ないように $ を挟む
rep(i, n) Z.push_back(tmp[S.size() + i + 1]);
}
// reachable, cost
using P = pair<ll, ll>;
auto op = [](P a, P b) -> P {
return {max(a.first, b.first), min(a.second, b.second)};
};
auto e = []() -> P {
return {0, INF};
};
segtree<P, op, e> seg(n + 1);
seg.set(n, {1, 0});
for (int i = n - 1; i >= 0; i--) {
if (!Z[i]) continue;
P p = seg.prod(i + 1, min(i + Z[i] + 1, n + 1));
seg.set(i, {p.first, p.second + 1});
}
P x = seg.get(0);
ll ans = -1;
if (x.first) ans = x.second;
cout << ans << endl;
}