むずかしいよ～～。これで冷えるんだなぁ # A - Triple Four 範囲外アクセスに注意しながら、言われたとおりに実装をしましょう。pythonとかだと`A[0]==A[1]==A[2]`と書けてちょっと嬉しい気持ちになるかもしれませんがC++を書き始めてしまったので、まあまぁ悲しいかも。 ```cpp #define rep(i,n) for (ll i=0;i> 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を使ってシミュレーションすればよいでしょう。 [提出](https://atcoder.jp/contests/abc396/submissions/63501209) ```cpp #define rep(i,n) for (ll i=0;i 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を付ける必要がある[^7])のでstackを使ったほうが文字数で有利です(？) # C - Buy Balls よくわかってないですが貪欲でごちゃごちゃやると解けます。なんで？[提出](https://atcoder.jp/contests/abc396/submissions/63516262) ```rust 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 { fn chmin(&mut self, elm: T) -> bool; fn chmax(&mut self, elm: T) -> bool; } impl ChLibs 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が得られます[^5]。解の上界を考えずに投げたらinfinityが微妙に足りて無くて1ペナ...[提出](https://atcoder.jp/contests/abc396/submissions/63527910) ```rust 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<>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!)$[^6]時間で解くことができ、こちらのほうが実装が簡潔・速度的にも有利です。[提出](https://atcoder.jp/contests/abc396/submissions/63568736) ```rust 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毎に見ることにします[^2]。そして、問題をグラフとしてみる事を考えます。下から$k(=0, 1, \cdots$)ビット目について、頂点$X_i$と頂点$Y_i$間にラベル($W_i$の下から$k$ビット目)がついた無向辺がある、とみなすこととします。以降は$k$については考慮せず、単に辺に0/1のラベルが付いたグラフのみを考えます。さてまずは頂点を0/1に矛盾なく塗り分けられるか？を判定することを考えます。これは、適当な頂点を0として決め打ち[^3]、(今いる頂点の値)$XOR$(辺についたラベル)として、隣の頂点のラベルを決めていきます。この際、すでにラベルが付いた頂点が隣りにあった際に既存の情報と新しい情報が矛盾した場合は構成不可能となり、そうでない場合は構成可能です。ラベル付が可能なことを判定しましたが、実際にこれが最小となるかどうかはまだわかりません。ここで、各連結成分について塗り分ける方法については2通りしかありません[^4]。このどちらを取るほうがよいかですが、これは明らかに1の数が少ない方をとったほうが良いでしょう。なぜなら、$k$の存在をこのあたりで思い出してもらった上でその連結成分のラベルが1の個数を$M$とすると、その連結成分の答えへの寄与は$M\times 2^k$であり、この式を見れば$M$が小さいほうが良いのは明らかです。よって、各$k$について求める答えを最小とするようなラベル付の仕方がわかったので、この問題が解けました。復元が微妙に面倒ですが頑張ってやりましょう。[提出](https://atcoder.jp/contests/abc396/submissions/63544105) ```rust 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]<0$の場合を求めます。ここで、$k-1$の場合の転倒数が既知であると仮定します。$k$のとき、新たに$0$になる、すなわち転倒数の変化に寄与する値は$M-k$です。これが$M-1$→$0$へと変化したとき、$i>j$なる$j$については、**すべて**転倒していない状態から転倒している状態へと変化します。これは$M-1$が数列$B$における最大値であり、$0$が数列$B$における最小値であることがら分かります。同様の議論によって、$ibit毎に見る、みたいなのは確かに有効ですが、例えば[ARC191B](https://atcoder.jp/contests/arc191/tasks/arc191_b)のような問題ではそうじゃない方針から(実験もなしで)ACを取る、みたいな例も実体験としてあるので、あくまで考察の一助という立ち位置で考えたほうが良い気がしています。 [^3]: べつに1でもいいですが、気持ち悪くないですか？ [^4]: まぁ自明ではないでしょうか。1つの頂点を決めるとその関係が全部決まるので、初めの0/1をどちらにするか、という話になります [^5]: 低速な言語でもこれぐらいは通ってほしい(願望) [^6]: 実際には$O(N\times(N-1)!)$ [^7]: 一生謎で、これ本当になんでなんですか

ABC396