鼻水・くしゃみ / ABC206 D

鼻水とくしゃみが止まらなくてつらい。

---

ABC206 : AtCoder Beginner Contest 206（Sponsored by Panasonic）

• D - KAIBUNsyo https://atcoder.jp/contests/abc206/tasks/abc206_d
  • 提出: https://atcoder.jp/contests/abc206/submissions/47576319
  • 回文にするためには左右の対応する位置が同じ数字である必要がある
  • 同じ数字を同じグループ (連結成分) と考えると、数字の種類数と最終的な連結成分数の差が必要な操作回数になる
  • 数字を座標圧縮して種類数に抑えた上で Dsu (Union-Find) に入れて連結成分を求めれば良い

use std::collections::{BTreeMap, BTreeSet};

use ac_library::Dsu;
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    };
    let map = a
        .iter()
        .copied()
        .collect::<BTreeSet<_>>()
        .into_iter()
        .enumerate()
        .fold(BTreeMap::new(), |mut m, (i, k)| {
            m.insert(k, i);
            m
        });
    let mut dsu = Dsu::new(map.len());
    for i in 0..n / 2 {
        let (a_i, a_j) = (a[i], a[n - 1 - i]);
        dsu.merge(map[&a_i], map[&a_j]);
    }
    let ans = map.len() - dsu.groups().len();
    println!("{}", ans);
}

---

今日のコミット。

• kireta 1 commit
  • Rename StoreTrait to Store
• rust-atcoder 1 commit
  • abc206 d