跳到主要内容

AtCoder Beginner Contest 190

视频题解

Problem A - Very Very Primitive Game​

先动的人必须有更多的糖果才能赢，所以我们只要检查这一条件是否满足即可。

  • 时间复杂度O(1)\mathcal{O}(1)
  • 空间复杂度O(1)\mathcal{O}(1)
参考代码（Rust）
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");
        }
    }
}

Problem B - Magic 3​

我们检查是否存在满足Xi<SX_i<S且Yi>DY_i>D的咒语。

  • 时间复杂度O(N)\mathcal{O}(N)
  • 空间复杂度O(1)\mathcal{O}(1)
参考代码（Rust）
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");
}

Problem C - Bowls and Dishes​

枚举所有的选择情况（一共2K2^K种），从中找到最大结果即可。

  • 时间复杂度O(2K(K+M))\mathcal{O}(2^K(K+M))
  • 空间复杂度O(N)\mathcal{O}(N)
参考代码（Rust）
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);
}

Problem D - Staircase Sequences​

假设数列首元素为aa，一共有nn个元素，则总和为(a+a+n−1)n2=N\frac{(a+a+n-1)n}{2}=N。所以我们可以枚举2N2N的所有因子，检查其是否可以作为NN。判断的条件是2Nn+1−n=2a\frac{2N}{n}+1-n=2a必须是偶数。

  • 时间复杂度O(N)\mathcal{O}(\sqrt{N})
  • 空间复杂度O(M)\mathcal{O}(M)，其中MM是2N2N的因子数。
参考代码（Rust）
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);
}
参考代码（C++）
#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;
}

Problem E - Magical Ornament​

我们可以把邻接对看成边，然后通过BFS找出所有关键宝石之间的最短路径，这些最短路径构成一个最短路径矩阵。

接下来我们进行状态压缩动态规划。状态为dp[mask][last]dp[mask][last]，其中maskmask表示我们已经获取到的关键宝石，lastlast表示当前序列的最后一个宝石（一定是一个关键宝石）。对于每一个状态，我们枚举nextnext，也即下一个选取的关键宝石来进行转移。

最后的答案就是min⁡idp[2K−1][i]\min_i{dp[2^K-1][i]}。

  • 时间复杂度O(KN+K2⋅2K)\mathcal{O}(KN+K^2\cdot2^K)
  • 空间复杂度O(N+M+K⋅2K)\mathcal{O}(N+M+K\cdot2^K)
参考代码（Rust）
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() {
        adj[u].push(v);
        adj[v].push(u);
    }

    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;
            }
            for v in adj[u].clone() {
                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);
    }
}
参考代码（C++）
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  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;
}

Problem F - Shift and Inversions​

我们可以用树状数组或类似归并排序的方法（实际上是CDQ分治）来求出原序列的逆序数。接下来，我们注意到当把KK（从11开始的）从序列开始移动到序列结尾时，减少了K−1K-1个逆序对，同时新增了N−KN-K个逆序对，因此变化量为N+1−2KN+1-2K。这样我们就可以逐个求出所有序列的逆序数了。

  • 时间复杂度O(Nlog⁡N)\mathcal{O}(N\log N)
  • 空间复杂度O(N)\mathcal{O}(N)
参考代码（Rust）
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]);
    }
}
参考代码（C++）
#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);
    ft.add(a[i], 1);
  }
  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;
  }
}