むずかしいよ～～。これで冷えるんだなぁ

A - Triple Four

範囲外アクセスに注意しながら、言われたとおりに実装をしましょう。pythonとかだとA[0]==A[1]==A[2]と書けてちょっと嬉しい気持ちになるかもしれませんがC++を書き始めてしまったので、まあまぁ悲しいかも。

#define rep(i,n) for (ll i=0;i<n;++i)
void solve() {
    int n; cin >> n;
    int a[n]; rep(i, n) cin >> a[i];
    rep(i, n-2) {
        if(a[i] == a[i+1] && a[i+1] == a[i+2]) {
            cout << "Yes
";
            return;
        }
    }
    cout << "No
";
}

B - Card Pile

シンプルに、言われたとおりにstackを使ってシミュレーションすればよいでしょう。 提出

#define rep(i,n) for (ll i=0;i<n;++i)
void solve() {
    stack<int> stk;
    rep(_, 100) stk.push(0);
    int q; cin >> q;
    rep(_, q) {
        int qi; cin >> qi;
        if(qi==1) {
            int x; cin >> x;
            stk.push(x);
        } else         {
            int ans = stk.top();
            stk.pop();
            cout << ans << '
';
        }
    }
}

ちなみにC++の場合はstackを使う理由はあんまりなくて、vectorで事足ります(が、std::vectorは何故かpush_backとsuffixに_backを付ける必要がある¹)のでstackを使ったほうが文字数で有利です(？)

C - Buy Balls

よくわかってないですが貪欲でごちゃごちゃやると解けます。なんで？提出

use std::cmp::Reverse;
use proconio::input;

fn main() {
    input!{
        n: usize,
        m: usize,
        mut b: [i64; n],
        mut w: [i64; m],
    }
    b.sort_unstable_by_key(|bi| Reverse(*bi));
    w.sort_unstable_by_key(|wi| Reverse(*wi));

    let mut cur = 0;
    let mut cur_sum = 0;
    let mut c_max = vec![];
    for &bi in &w {
        cur_sum += bi;
        cur.chmax(cur_sum);
        c_max.push(cur);
    }

    let mut ans = 0;
    let mut w_sum = 0;
    for (i, &wi) in b.iter().enumerate() {
        w_sum += wi;
        ans.chmax(w_sum+c_max[i.min(c_max.len()-1)]);
    }

    println!("{ans}");
}

pub trait ChLibs<T: std::cmp::Ord> {
    fn chmin(&mut self, elm: T) -> bool;
    fn chmax(&mut self, elm: T) -> bool;
}

impl<T: std::cmp::Ord> ChLibs<T> for T {
    fn chmin(&mut self, elm: T) -> bool {
        if *self > elm {
            *self = elm;
            true
        } else {
            false
        }
    }

    fn chmax(&mut self, elm: T) -> bool {
        if *self < elm {
            *self = elm;
            true
        } else {
            false
        }
    }
}

D - Minimum XOR Path

$N=10$と少し大きいように見えますが、実際には始点と終点が決まっており探索するべき並び順は$(N-2)!2^{N-2}$通り未満となります。これは中間の並べ替えが$(N-2)!$であり、それらの頂点を実際に通るかどうかが$2^{N-2}$通りあること、また実際には重複が多く存在することから分かります。 実際のxor sumの計算に$N$個見て上げる必要があるので、$O(N(N-2)!2^{N-2})$時間でこの問題が解けることが示せました。$N=10$のとき$N(N-2)!2^{N-2}=103219200$であり、大体$\times10^9$ぐらいなのでこれをそのまま実装すればACが得られます²。解の上界を考えずに投げたらinfinityが微妙に足りて無くて1ペナ...提出

use std::u64;

use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        m: usize,
        e: [(Usize1, Usize1, u64); m],
    }
    
    let g = e.iter().fold(vec![vec![]; n], |mut g, &(u, v, w)| {
        g[u].push((v, w));
        g[v].push((u, w));
        g
    });
    let v = (1..n-1).collect_vec();

    let mut ans = u64::MAX;
    'perm: for v in v.iter().copied().permutations(v.len()) {
        'i: for i in 0..1<<v.len() {
            let mut prev = 0;
            let mut cur = 0;
            'j: for j in 0..v.len() {
                if (i>>j)&1 == 0 { continue; }
                if let Some((_, w)) = g[prev].iter().find(|(t, _)| v[j] == *t) {
                    cur ^= *w;
                    prev = v[j];
                } else {
                    continue 'i;
                }
            }
            if let Some((_, w)) = g[prev].iter().find(|(t, _)| n-1 == *t) {
                ans.chmin(cur ^ *w);
            }
        }
    }
    println!("{}", ans);
}

なお、始点を固定して終点は固定せず、終点が見つかった時点で打ち切るように実装を行うと$O(N!)$³時間で解くことができ、こちらのほうが実装が簡潔・速度的にも有利です。提出

use std::u64;

use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        m: usize,
        e: [(Usize1, Usize1, u64); m],
    }
    
    let g = e.iter().fold(vec![vec![]; n], |mut g, &(u, v, w)| {
        g[u].push((v, w));
        g[v].push((u, w));
        g
    });

    let ans = (1..n)
        .into_iter()
        .permutations(n-1)
        .filter_map(|v| {
            let mut prev = 0;
            let mut xorsum = 0;
            for pi in v.iter() {
                if let Some((_, w)) = g[prev].iter().find(|(t, _)| t == pi) {
                    xorsum ^= *w;
                    prev = *pi;
                } else {
                    return None;
                }
                if *pi==n-1 { break; }
            }
            Some(xorsum)
        })
        .min() 
        .unwrap();
    println!("{ans}");
}

E - Min of Restricted Sum

XOR演算なので、bit毎に見ることにします⁴。そして、問題をグラフとしてみる事を考えます。 下から$k(=0, 1, \cdots$)ビット目について、頂点$X_i$と頂点$Y_i$間にラベル($W_i$の下から$k$ビット目)がついた無向辺がある、とみなすこととします。以降は$k$については考慮せず、単に辺に0/1のラベルが付いたグラフのみを考えます。

さてまずは頂点を0/1に矛盾なく塗り分けられるか？を判定することを考えます。これは、適当な頂点を0として決め打ち⁵、(今いる頂点の値)$XOR$(辺についたラベル)として、隣の頂点のラベルを決めていきます。この際、すでにラベルが付いた頂点が隣りにあった際に既存の情報と新しい情報が矛盾した場合は構成不可能となり、そうでない場合は構成可能です。

ラベル付が可能なことを判定しましたが、実際にこれが最小となるかどうかはまだわかりません。ここで、各連結成分について塗り分ける方法については2通りしかありません⁶。このどちらを取るほうがよいかですが、これは明らかに1の数が少ない方をとったほうが良いでしょう。なぜなら、$k$の存在をこのあたりで思い出してもらった上でその連結成分のラベルが1の個数を$M$とすると、その連結成分の答えへの寄与は$M\times 2^k$であり、この式を見れば$M$が小さいほうが良いのは明らかです。

よって、各$k$について求める答えを最小とするようなラベル付の仕方がわかったので、この問題が解けました。復元が微妙に面倒ですが頑張ってやりましょう。提出

use std::collections::VecDeque;

use ac_library::Dsu;
use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        m: usize,
        e: [(Usize1, Usize1, u64); m],
    }

    let g = e.iter().fold(vec![vec![]; n], |mut g, &(u, v, w)| {
        g[u].push((v, w));
        g[v].push((u, w));
        g
    });
    let mut ans = vec![0; n];

    static INF: u64 = 100;
    for i in 0..32 {
        // ibit目を決める
        let mut seen = vec![INF; n];
        for j in 0..n {
            if seen[j] != INF { continue; }
            let mut reached = vec![j];

            seen[j] = 0;
            let mut que = VecDeque::new();
            que.push_back(j);

            let mut sum = 0;
            while let Some(p) = que.pop_front() {
                for &(ni, w) in &g[p] {
                    if seen[ni] == INF {
                        if (w>>i) & 1 == 0 {
                            seen[ni] = seen[p];
                        } else {
                            seen[ni] = seen[p] ^ 1;
                        }
                        sum += seen[ni];
                        reached.push(ni);
                        que.push_back(ni);
                    } else {
                        if (w>>i) & 1 == 0 {
                            if seen[ni] != seen[p] {
                                println!("-1");
                                return;
                            }
                        } else {
                            if seen[ni] == seen[p] {
                                println!("-1");
                                return;
                            }
                        }
                    }
                }
            }
            for &p in reached.iter() {
                if sum > reached.len() as u64 - sum {
                    seen[p] ^= 1;
                }
                ans[p] |= seen[p]<<i; 
            }
        }
    }
    println!("{}", ans.iter().join(" "));
}

F - Rotated Inversions

5分間に合わず。

まず、$k=0$のときの転倒数を求めます。これは単に$A$の転倒数であり、FenwickTreeなどを用いることで$O(N\log N)$で求めることができます⁷ 次に、$k>0$の場合を求めます。ここで、$k-1$の場合の転倒数が既知であると仮定します。$k$のとき、新たに$0$になる、すなわち転倒数の変化に寄与する値は$M-k$です。これが$M-1$→$0$へと変化したとき、$i>j$なる$j$については、すべて転倒していない状態から転倒している状態へと変化します。これは$M-1$が数列$B$における最大値であり、$0$が数列$B$における最小値であることがら分かります。同様の議論によって、$i<j$なる$j$についてはすべて転倒している状態から転倒していない状態に変化します。

よって、各$k$について上記の差分計算を適用することでこの問題を解くことができます。提出

use ac_library::FenwickTree;
use itertools::Itertools;
use proconio::input;

fn main() {
    input!{
        n: usize,
        m: i64,
        a: [i64; n],
    }
    let mut bit = FenwickTree::new(n, 0);
    let mut ai_list = vec![vec![]; m as usize];
    for i in 0..n {
        bit.add(i, 1);
        ai_list[a[i] as usize].push(i);
    }
    let mut cur = 0i64;
    for (i, _) in a.iter().enumerate().sorted_by_key(|(_, &ai)| ai) {
        bit.add(i, -1);
        cur += bit.sum(0..i);
    }
    println!("{}", cur);
    for i in (1..m as usize).rev() {
        for (j, &pi) in ai_list[i].iter().enumerate() {
            cur += pi as i64;
            cur -= n as i64 - pi as i64 - 1;
        }
        println!("{}", cur);
    }
}

[[転倒数の更新典型]]というものがあるみたいです。転倒数が差分計算に強い(更新しやすい)という視点は今まで持ったことがなかったのですが、確かに言われてみればという気持ちになりました。

Footnotes

1. 一生謎で、これ本当になんでなんですか ↩

2. 低速な言語でもこれぐらいは通ってほしい(願望) ↩

3. 実際には$O(N\times(N-1)!)$ ↩

4. XOR演算->bit毎に見る、みたいなのは確かに有効ですが、例えばARC191Bのような問題ではそうじゃない方針から(実験もなしで)ACを取る、みたいな例も実体験としてあるので、あくまで考察の一助という立ち位置で考えたほうが良い気がしています。 ↩

5. べつに1でもいいですが、気持ち悪くないですか？ ↩

6. まぁ自明ではないでしょうか。1つの頂点を決めるとその関係が全部決まるので、初めの0/1をどちらにするか、という話になります ↩

7. 転倒数の求め方は典型なので省略 ↩