ABC 361
Table of Contents
https://atcoder.jp/contests/abc361
A. Insert
https://atcoder.jp/contests/abc361/tasks/abc361_a
B. Intersection of Cuboids
https://atcoder.jp/contests/abc361/tasks/abc361_b
C. Make Them Narrow
https://atcoder.jp/contests/abc361/tasks/abc361_c
D. Go Stone Puzzle
https://atcoder.jp/contests/abc361/tasks/abc361_d
8 puzzle のような問題。状態から状態への繊維を考え BFS で最短距離を求める。
ll intpow(ll x, ll n) {
long long ret = 1;
while (n > 0) {
if (n & 1)
ret *= x;
x *= x;
n >>= 1;
}
return ret;
}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
string S, T;
cin >> N >> S >> T;
N += 2;
auto toid = [&](string s) -> ll {
ll ret = 0;
for (char c : s) {
ret *= 3;
if (c == 'B') {
ret += 2;
}
if (c == 'W') { // W
ret += 1;
}
}
return ret;
};
auto idtos = [&](ll id) -> string {
string ret = "";
rep(i, N) {
if (id % 3 == 0) {
ret.push_back('_');
} else if (id % 3 == 1) {
ret.push_back('W');
} else {
ret.push_back('B');
}
id /= 3;
}
reverse(all(ret));
return ret;
};
S += "__";
T += "__";
vll dist(intpow(3, N), INF);
dist[toid(S)] = 0;
ll goal = toid(T);
// cost, id
using P = pair<ll, ll>;
queue<P> que;
que.push({0, toid(S)});
while (que.size()) {
auto [cost, id] = que.front();
que.pop();
if (dist[id] < cost) continue;
string t = idtos(id);
int space_id = -1;
rep(j, N - 1) {
if (t[j] == '_' && t[j + 1] == '_') {
space_id = j;
break;
}
}
if (space_id < 0) continue;
int ok = 0;
rep(i, N - 1) {
if (t[i] != '_' && t[i + 1] != '_') {
string tmp = t;
swap(tmp[space_id], tmp[i]);
swap(tmp[space_id + 1], tmp[i + 1]);
ll nxid = toid(tmp);
if (dist[nxid] > cost + 1) {
dist[nxid] = cost + 1;
que.push({cost + 1, nxid});
if (nxid == goal) {
ok = 1;
break;
}
}
}
}
if (ok) break;
}
ll ans = -1;
if (dist[goal] != INF) ans = dist[goal];
cout << ans << endl;
}
E. Tree and Hamilton Path 2
https://atcoder.jp/contests/abc361/tasks/abc361_e
解説 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<vector<pair<ll, ll>>> graph(N);
vll C;
rep(i, N - 1) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
C.push_back(c);
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
vll dist(N);
auto dfs = [&](auto dfs, int now, int p) -> void {
for (auto [nx, c] : graph[now]) {
if (nx == p) continue;
dist[nx] = dist[now] + c;
dfs(dfs, nx, now);
}
};
dfs(dfs, 0, -1);
int s = -1;
ll d = -1;
rep(i, N) {
if (d < dist[i]) {
d = dist[i];
s = i;
}
}
rep(i, N) dist[i] = 0;
dfs(dfs, s, -1);
d = -1;
rep(i, N) {
if (d < dist[i]) {
d = dist[i];
}
}
ll ans = accumulate(all(C), 0ll);
ans *= 2;
ans -= d;
cout << ans << endl;
}
F. x = a^b
https://atcoder.jp/contests/abc361/tasks/abc361_f
自力 AC
$a = 1$ のとき
$1 \leq N$ かつ $1^1 = 1 \leq N$ より常に成立。
$a \geq 2$ のとき
$10^{18} < 2^{60}$ なので、$b$ として考えなければいけないのは $b \in [2, 60)$ の範囲である。
$a^b \leq N$ となる $a$ の数は $a = \floor{N^{1/b}} - 1$ 個である($a = 1$ 分を 1 引いている) ここまでで包除原理を使って重複分を引きつつ答えが求められそうなことがわかる。
ここで $16 = 2^4 = 4^2$ のように同じ数字でも複数の表現方法があるがこれらは一つとして計上しなければならない。 これより $b$ として考える必要のある値は $b$ を素因数分解したとき、各素因数のべきが1のものだけである。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
using Int = unsigned long long int;
auto kth_root = [](Int x, Int k) -> Int {
assert(k != 0);
if (x == 1 || k == 1) return x;
Int l = 0, r = x;
while (r - l > 1) {
Int m = (r - l) / 2 + l;
Int t = x;
rep(i, k) t /= m;
if (1 > t) {
r = m;
} else {
l = m;
}
}
return l;
};
vll primes;
{
auto is_prime = [](ll x) -> bool {
for (ll i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
};
rep2(i, 2, 60) if (is_prime(i)) primes.push_back(i);
}
ll psz = primes.size();
auto choose = [&](ll n, ll k) -> vvll {
vvll ret;
vint used(n);
auto _choose = [&](auto _choose, vll v) -> void {
if (accumulate(all(used), 0ll) == k) {
ret.push_back(v);
return;
}
{
ll x = 1;
for (ll id : v) {
x = lcm(x, primes[id]);
}
if (x >= 60) return; // べきが 60 以上になるやつは考える必要がない
}
int last_one_id = -1;
rep(i, n) if (used[i]) last_one_id = i;
rep2(i, last_one_id + 1, n) {
used[i] = 1;
v.push_back(i);
_choose(_choose, v);
v.pop_back();
used[i] = 0;
}
};
_choose(_choose, vll());
return ret;
};
ll N;
cin >> N;
ll ans = 1;
for (ll c = 1; c <= psz; c++) {
vvll vs = choose(psz, c);
for (auto& v : vs) {
ll x = 1;
for (ll id : v) x = lcm(x, primes[id]);
ll cnt = kth_root(N, x) - 1;
if (v.size() % 2 == 1) {
ans += cnt;
} else {
ans -= cnt;
}
}
}
cout << ans << endl;
}
解説放送では包除原理をよりスマートに実装していた。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
using Int = unsigned long long int;
auto kth_root = [](Int x, Int k) -> Int {
assert(k != 0);
if (x == 1 || k == 1) return x;
Int l = 0, r = x;
while (r - l > 1) {
Int m = (r - l) / 2 + l;
Int t = x;
rep(i, k) t /= m;
if (1 > t) {
r = m;
} else {
l = m;
}
}
return l;
};
ll N;
cin >> N;
ll M = 60;
ll ans = 1;
vll cnt(M);
for (ll b = M - 1; b >= 2; b--) {
cnt[b] = kth_root(N, b) - 1;
for (ll j = b * 2; j < M; j += b) {
cnt[b] -= cnt[j];
}
ans += cnt[b];
}
cout << ans << endl;
}