# # AtCoder Beginner Contest 190 题解

## # Problem A - Very Very Primitive Game (opens new window)

• 时间复杂度$\mathcal{O}(1)$
• 空间复杂度$\mathcal{O}(1)$

use proconio::input;

fn main() {
input! {
a: usize,
b: usize,
c: usize,
}

if c == 0 {
if a > b {
println!("Takahashi");
} else {
println!("Aoki");
}
} else {
if b > a {
println!("Aoki");
} else {
println!("Takahashi");
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

## # Problem B - Magic 3 (opens new window)

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

use proconio::input;

fn main() {
input! {
n: usize,
s: usize,
d: usize,
spells: [(usize, usize); n],
}

for (x, y) in spells {
if x < s && y > d {
println!("Yes");
return;
}
}

println!("No");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem C - Bowls and Dishes (opens new window)

• 时间复杂度$\mathcal{O}(2^K(K+M))$
• 空间复杂度$\mathcal{O}(N)$

use proconio::input;
use proconio::marker::Usize1;

fn main() {
input! {
n: usize,
m: usize,
dishes: [(Usize1, Usize1); m],
k: usize,
people: [(Usize1, Usize1); k],
}

let mut ans = 0;

for i in 0..(1 << k) {
let mut cnt = vec![0; n];
for j in 0..k {
if i & (1 << j) > 0 {
cnt[people[j].1] += 1;
} else {
cnt[people[j].0] += 1;
}
}

let mut tot = 0;

for j in 0..m {
if cnt[dishes[j].0] > 0 && cnt[dishes[j].1] > 0 {
tot += 1;
}
}

ans = ans.max(tot);
}

println!("{}", ans);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

## # Problem D - Staircase Sequences (opens new window)

• 时间复杂度$\mathcal{O}(\sqrt{N})$
• 空间复杂度$\mathcal{O}(M)$，其中$M$$2N$的因子数。

use proconio::input;
use std::collections::HashSet;

fn main() {
input! {
n: i64,
}

let mut factors = HashSet::new();
let x = n * 2;

let mut i = 1i64;
while i * i <= x {
if x % i == 0 {
factors.insert(i.clone());
factors.insert((x / i).clone());
}
i += 1;
}

let mut ans = 0;
for k in factors {
let rem = x / k;
if (rem + 1 - k) % 2 == 0 {
ans += 1;
}
}

println!("{}", ans);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <unordered_set>

using namespace std;
using ll = long long;

int main() {
ll n;
cin >> n;
unordered_set<ll> factors;
ll x = n * 2;
for (int i = 1; 1LL * i * i <= x; ++i) {
if (x % i == 0) {
factors.insert(i);
factors.insert(x / i);
}
}

int ans = 0;
for (ll factor : factors)
if ((x / factor + 1 - factor) % 2 == 0)
ans++;

cout << ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

## # Problem E - Magical Ornament (opens new window)

• 时间复杂度$\mathcal{O}(KN+K^2\cdot2^K)$
• 空间复杂度$\mathcal{O}(N+M+K\cdot2^K)$

use proconio::input;
use proconio::marker::Usize1;
use std::collections::VecDeque;

const INF: usize = 1_000_000_000;

fn main() {
input! {
n: usize,
m: usize,
pairs: [(Usize1, Usize1); m],
k: usize,
c: [Usize1; k],
}

let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
for (u, v) in pairs.clone() {
}

let mut mapping = vec![k; n];
for (i, u) in c.clone().into_iter().enumerate() {
mapping[u] = i;
}

let mut dist: Vec<Vec<usize>> = vec![vec![INF; k]; k];
for i in 0..k {
let mut dq: VecDeque<(usize, usize)> = VecDeque::new();
dq.push_back((c[i], 0));
let mut vis = vec![false; n];
vis[c[i]] = true;
while !dq.is_empty() {
let (u, steps) = dq.pop_front().unwrap();
if mapping[u] != k {
dist[i][mapping[u]] = steps;
}
if !vis[v] {
vis[v] = true;
dq.push_back((v, steps + 1));
}
}
}
}

let mut ans = INF;

let mut dp = vec![vec![INF; k]; 1 << k];
for i in 0..k {
dp[1 << i][i] = 1;
}

for state in 0..(1 << k) {
for last in 0..k {
if dp[state][last] < INF {
for next in 0..k {
if state & (1 << next) == 0 {
dp[state ^ (1 << next)][next] = dp[state ^ (1 << next)][next].min(dp[state][last] + dist[last][next]);
}
}
}
}
}

for i in 0..k {
ans = ans.min(dp[(1 << k) - 1][i]);
}

if ans == INF {
println!("-1");
} else {
println!("{}", ans);
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;

int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
u--, v--;
}

int k;
cin >> k;
vector<int> c(k);
map<int, int> mp;
for (int i = 0; i < k; ++i)
cin >> c[i], c[i]--, mp[c[i]] = i;

vector<vector<int>> d(k, vector<int>(k, INF));
for (int i = 0; i < k; ++i) {
queue<pair<int, int>> q;
vector<bool> vis(n);
q.emplace(c[i], 0);
vis[c[i]] = true;
while (!q.empty()) {
auto [u, steps] = q.front();
q.pop();
if (mp.count(u))
d[i][mp[u]] = steps;
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
q.emplace(v, steps + 1);
}
}
}
}

vector<vector<int>> dp(1 << k, vector<int>(k, INF));
for (int i = 0; i < k; ++i)
dp[1 << i][i] = 1;
for (int state = 1; state < (1 << k); ++state)
for (int last = 0; last < k; ++last) {
if (state & (1 << last)) {
for (int nxt = 0; nxt < k; ++nxt) {
if (!(state & (1 << nxt))) {
dp[state ^ (1 << nxt)][nxt] = min(dp[state ^ (1 << nxt)][nxt],
dp[state][last] + d[last][nxt]);
}
}
}
}

int ans = INF;
for (int i = 0; i < k; ++i)
ans = min(ans, dp[(1 << k) - 1][i]);

if (ans == INF)
cout << "-1";
else
cout << ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

## # Problem F - Shift and Inversions (opens new window)

• 时间复杂度$\mathcal{O}(N\log N)$
• 空间复杂度$\mathcal{O}(N)$

use proconio::input;

fn low_bit(x: i32) -> i32 {
x & (-x)
}

struct FenwickTree {
v: Vec<i32>
}

impl FenwickTree {
fn new(n: usize) -> Self {
FenwickTree {
v: vec![0; n + 1],
}
}

fn update(&mut self, mut x: usize, val: i32) {
while x < self.v.len() {
self.v[x as usize] += val;
x += low_bit(x as i32) as usize;
}
}

fn query(&mut self, mut x: usize) -> i32 {
let mut ans = 0;
while x > 0 {
ans += self.v[x as usize];
x -= low_bit(x as i32) as usize;
}
ans
}
}

fn main() {
input! {
n: usize,
a: [usize; n],
}

let mut ft = FenwickTree::new(n);
let mut ans = vec![0i64; n];
for i in 0..n {
let larger = (i as i32) - ft.query(a[i] + 1);
ans[0] += larger as i64;
ft.update(a[i] + 1, 1);
}

println!("{}", ans[0]);
for i in 1..n {
ans[i] = ans[i - 1] - a[i - 1] as i64 + (n as i64 - 1 - a[i - 1] as i64);
println!("{}", ans[i]);
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <atcoder/fenwicktree>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
vector<ll> ans(n);
atcoder::fenwick_tree<int> ft(n);
for (int i = 0; i < n; ++i) {
ans[0] += ft.sum(a[i] + 1, n);
}
cout << ans[0] << endl;
for (int i = 1; i < n; ++i) {
ans[i] = ans[i - 1] + n - 1 - 2 * a[i - 1];
cout << ans[i] << endl;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24