むずかしいよ～～。これで冷えるんだなぁ
範囲外アクセスに注意しながら、言われたとおりに実装をしましょう。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\n";
return;
}
}
cout << "No\n";
}シンプルに、言われたとおりに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 << '\n';
}
}
}ちなみにC++の場合はstackを使う理由はあんまりなくて、vectorで事足ります(が、
std::vector
は何故か
push_back
とsuffixに_backを付ける必要がある
)のでstackを使ったほうが文字数で有利です(？)
よくわかってないですが貪欲でごちゃごちゃやると解けます。なんで？ 提出
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
}
}
}\(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}");
}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(" "));
}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
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);
}
}転倒数の更新典型というものがあるみたいです。転倒数が差分計算に強い(更新しやすい)という視点は今まで持ったことがなかったのですが、確かに言われてみればという気持ちになりました。