ABC 398
Table of Contents
https://atcoder.jp/contests/abc398
A. Doors in the Center
https://atcoder.jp/contests/abc398/tasks/abc398_a
B. Full House 3
https://atcoder.jp/contests/abc398/tasks/abc398_b
C. Uniqueness
https://atcoder.jp/contests/abc398/tasks/abc398_c
D. Bonfire
https://atcoder.jp/contests/abc398/tasks/abc398_d
煙の位置は変えずに焚き火と高橋くんの位置を移動させる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n, row, col;
cin >> n >> row >> col;
string s;
cin >> s;
using P = pair<ll, ll>;
set<P> memo;
memo.insert({0, 0});
int si = 0, sj = 0;
for (char c : s) {
if (c == 'N') {
si++;
row++;
}
if (c == 'W') {
sj++;
col++;
}
if (c == 'S') {
si--;
row--;
}
if (c == 'E') {
sj--;
col--;
}
memo.insert({si, sj});
if (memo.count({row, col})) {
cout << 1;
} else {
cout << 0;
}
}
cout << endl;
}
E. Tree Game
https://atcoder.jp/contests/abc398/tasks/abc398_e
First の後に改行を入れ忘れてコンテスト中 AC できなかった。。。
ただ二部グラフであるということはわからずやっていたので AC できていたとしても実力でなくまぐれ AC だったのでまぁいいかという感じ。
奇閉路がない <=> 二部グラフである という条件があるらしい。言われてみれば確かにと思う。 色が違う頂点の組の数が奇数のときは先手必勝、偶数のときは後手必勝ということがわかる。
奇閉路がない <=> 二部グラフであると言えるのが何故か
ある頂点から同じ色の頂点への距離は2の倍数となる。よって同じ色どうしの頂点を結ぶと閉路の1周の距離は奇数となる。 逆に奇閉路のとき、必ず頂点のうちどこかで同じ色が隣り合わせになってしまう。 よって題意が言える。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
using P = pair<int, int>;
set<P> memo;
int n;
cin >> n;
vvint graph(n);
rep(i, n - 1) {
int u, v;
cin >> u >> v;
u--, v--;
graph[u].push_back(v);
graph[v].push_back(u);
memo.insert({u, v});
memo.insert({v, u});
}
vint depth(n, 0);
auto dfs = [&](auto dfs, int now, int p = -1) -> void {
for (int nx : graph[now]) {
if (nx == p)
continue;
depth[nx] = depth[now] + 1;
dfs(dfs, nx, now);
}
};
dfs(dfs, 0);
set<P> es;
int cnt = 0;
rep(i, n) {
rep2(j, i + 1, n) {
if (memo.count({i, j}))
continue;
if ((depth[i] + depth[j]) % 2 == 1) {
cnt++;
es.insert({i, j});
}
}
}
if (cnt % 2 == 1) {
cout << "First" << endl;
cout << flush;
auto it = es.begin();
cout << it->first + 1 << ' ' << it->second + 1 << endl;
cout << flush;
es.erase(it);
} else {
cout << "Second" << endl;
cout << flush;
}
while (es.size()) {
int u, v;
cin >> u >> v;
u--, v--;
if (u > v)
swap(u, v);
es.erase({u, v});
auto it = es.begin();
auto [nu, nv] = *it;
es.erase(it);
cout << nu + 1 << ' ' << nv + 1 << endl;
cout << flush;
}
int u, v;
cin >> u >> v;
if (u == -1 && v == -1) {
return;
}
}
F. ABCBA
https://atcoder.jp/contests/abc398/tasks/abc398_f
ローリングハッシュを使って解いた。
$S$ を逆転させたものを $T$ とする。 $S$ の suffix $m$ 文字と $T$ の prefix $m$ 文字が一致する最大の $m$ を求める。
ll modpow(ll x, ll n, ll mod) {
long long ret = 1;
while (n > 0) {
if (n & 1)
ret = (ret * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return ret;
}
struct RollingHash {
vll data;
const ll p = 1000000009;
const ll mod = 1000000021;
RollingHash(vll& v) {
int n = v.size();
data.resize(n + 1);
rep(i, n) {
data[i + 1] = (data[i] * p % mod) + v[i];
data[i + 1] %= mod;
}
};
ll sub(ll l, ll r) {
ll m = r - l;
ll x = data[r] - data[l] * modpow(p, m, mod) % mod;
x += mod;
x %= mod;
return x;
}
};
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
string t = s;
reverse(all(t));
int n = s.size();
vll val, rev;
rep(i, n) {
val.push_back(s[i] - 'A');
rev.push_back(t[i] - 'A');
}
RollingHash h(val), hr(rev);
ll common = 0;
rep(i, n) {
if (h.sub(n - 1 - i, n) == hr.sub(0, i + 1)) {
chmax(common, i + 1);
}
}
cout << s;
cout << t.substr(common, n - common);
cout << endl;
}
Z Algorithm というのを使うと簡単に解けたらしい。
Z Algorithm は文字列 $T$ に対して T[0:] と T[i:] の最長共通接頭辞の長さを求めるアルゴリズム。
$S$ を反転させたものを $S'$ とすると $S' + S$ に対して Z Algorithm を適用。 $z = Zalgorithm(S'+S)$ とすると $z_{n+i} = n-i$ となる最大の $n-i$ が $S$ の suffix と $S'$ の prefix の一致する最大の長さとなる。
$z_{n+i} = n-i$ という条件を外して $\displaystyle \max_{i \in [0,n)} z_{n+i}$ とすると誤答する。
例
$S = \text{ABXYBA}$ のときを考える。$Zalgorithm(S' + S) = [12, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 1]$ であり、6番目以降の要素を抜き出してくると $[2, 0, 0, 0, 0, 1]$ である。この範囲での最大値は2であるが、これは $S$ の prefix と $S'$ の prefix の一致する文字数なので今回欲しい値ではない。 $S$ の sufiix と $S'$ の prefix の共通する長さを調べるために $z_{n+i} = n-i$ という条件が必要
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
string t = s;
reverse(all(t));
string concat = t + s;
vint z = z_algorithm(concat);
int common = 0;
rep(i, n) {
if (z[n + i] == n - i)
chmax(common, z[n + i]);
}
cout << s;
cout << t.substr(common, n - common);
cout << endl;
}