AtCoderのABC301以降のコンテスト(ABC, ARC, AGC)について、典型といえる部分を抜き出した記事になります。
立ち位置としては、1人で更新することで全ての問題について何かしら載っているAtCoder Tagsだと思っています。
投稿者の手動更新で、明確な判断基準があるわけではないので、あくまで参考程度にご使用ください。
1つ目の表の「問題」のリンクからは、AtCoderの問題のページに飛びます。
1つ目の表の「典型要素」のリンクからは、2つ目の表に飛びます。
2つ目の表の「問題」のリンクからは、1つ目の表に飛びます。
ARC175を解き直しました。
コンテスト時はBの1完でした。
6連敗です…そして、ARCは2連続で1完早解きしてから2完できず冷えるという、後味の悪い結果に…
復習したときのメモを動画にして提出したもののみ載せます。
www.youtube.com
www.nicovideo.jp
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::{Chars, Usize1}; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,p:[Usize1;n],s:Chars); let mut ans=Mint::new(0); let mut cnt=Mint::new(1); let mut exists=vec![true;n]; for i in 0..n { if exists[(p[i]+1)%n] { if s[p[i]]=='R' { cnt*=0; } } else { if s[p[i]]=='?' { cnt*=2; } } exists[p[i]]=false; } ans+=cnt; let mut cnt=Mint::new(1); let mut exists=vec![true;n]; for i in 0..n { if exists[p[i]] { if s[p[i]]=='L' { cnt*=0; } } else { if s[p[i]]=='?' { cnt*=2; } } exists[(p[i]+1)%n]=false; } ans+=cnt; outputln!(ans); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num::Integer; use proconio::marker::Chars; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(_:usize,a:usize,b:usize,mut s:Chars); let mut lcnt=0usize; let mut rcnt=0; for &c in &s { if c=='(' { lcnt+=1; } else { rcnt+=1; } } let mut ans=0; if lcnt<rcnt { for c in &mut s { if lcnt==rcnt { break; } if *c==')' { *c='('; rcnt-=1; lcnt+=1; ans+=b; } } } else if lcnt>rcnt { for c in s.iter_mut().rev() { if lcnt==rcnt { break; } if *c=='(' { *c=')'; lcnt-=1; rcnt+=1; ans+=b; } } } let mut cnt=0; let mut cnt_min=0; for &c in &s { if c=='(' { cnt+=1; } else { cnt-=1; } cnt_min.chmin(cnt); } if cnt_min<0 { ans+=(-cnt_min).div_ceil(&2) as usize*min(a,2*b); } outputln!(ans); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num::clamp; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,lr:[(usize,usize);n]); let mut a=vec![0;n]; let cost=|a0:usize| { let mut ret=0; let mut a=a0; for i in 1..n { let next=clamp(a, lr[i].0, lr[i].1); ret+=a.abs_diff(next); a=next; } ret }; a[0]=binary_search(lr[0].0, lr[0].1+1, |mid| { cost(mid)<cost(mid-1) }); let mut is_decreased=vec![false;n]; let mut idx=0; for i in 1..n { a[i]=clamp(a[i-1], lr[i].0, lr[i].1); if a[i-1]>a[i] { for j in idx..i { is_decreased[j]=true; } } if a[i-1]!=a[i] { idx=i; } } for i in (0..n-1).rev() { if !is_decreased[i] { continue; } a[i]=max(a[i+1], lr[i].0); } a.outputln(); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize,uv:[(Usize1,Usize1);n-1]); let g=VecGraph::construct_graph(n, n-1, &uv); let dist=g.dist_of_shortest_paths(0, false); if k<n || k>n+dist.sum() { return output_no(); } let sizes=g.sizes_of_subtrees(0); let mut sz_idx=vec_range(1..n, |i| (sizes[i],i)); sz_idx.reverse_sort(); let mut sum=k-n; let mut sgn_dist=vec_range(0..n, |i| (-(dist[i] as isize),i)); for (s,i) in sz_idx { if sum>=s { sum-=s; sgn_dist[i].0*=-1; } } sgn_dist.sort(); let mut ans=vec![0;n]; for p in 0..n { ans[sgn_dist[p].1]=p+1; } output_yes(); ans.outputln(); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize); let mut ans=vec![]; if n%3==0 { ans.push([0,0,0]); if ans.len()%3!=k%3 { ans.push([n/3,n/3,n/3]); } if ans.len()%3!=k%3 { ans.push([n/3*2,n/3*2,n/3*2]); } } else { if k%3>0 { ans.push([0,0,0]); } if k%3==2 { ans.push([1,1,1]); } } for x in 0..n { if ans.len()==k { break; } for y in x..n { let z=(2*n-x-y)%n; if ans.len()==k { break; } if z<y { continue; } if x==y && y==z { continue; } if n%3>0 && k%3==2 && (x,y)==(1,1) { continue; } ans.push([x,y,z]); ans.push([y,z,x]); ans.push([z,x,y]); if ans.len()==k { break; } if x==y || y==z { continue; } ans.push([y,x,z]); ans.push([x,z,y]); ans.push([z,y,x]); } } ans.outputlns(); }
use std::cmp::Ordering; use ac_library::FenwickTree; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Chars; use superslice::Ext; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,s:[Chars;n]); let mut ssort=vec_range(0..n, |i| s[i].clone()); ssort.sort_and_dedup(); let mut inv_num=0; let mut ft=FenwickTree::new(n, 0); for i in 0..n { let s_num=ssort.lower_bound(&s[i]); inv_num+=ft.sum(s_num+1..); ft.add(s_num, 1); } let mut nmax=0; for i in 0..n { nmax.chmax(s[i].len()); } let b=RollingHashBases::<2>::gen(nmax, 26); let rh=vec_range(0..n, |i| s[i].calculate_rolling_hashes('a', &b)); let mut diffs=vec![vec![];n]; let mut suffixes=vec![]; for i in 0..n { diffs[i].resize(s[i].len(), 0); for j in 0..s[i].len() { suffixes.push((i,j)); } } let mut left_set=MultiSet::new(); let mut right_set=MultiSet::new(); for i in 0..n { right_set.insert_one(rh[i].rolling_hash_of_subsequence(0, s[i].len(), &b)); } for i in 0..n { right_set.remove_one(rh[i].rolling_hash_of_subsequence(0, s[i].len(), &b)); for j in 1..s[i].len() { let hash=rh[i].rolling_hash_of_subsequence(0, j, &b); if let Some(&cnt)=left_set.get(&hash) { diffs[i][j]+=cnt as isize; } if let Some(&cnt)=right_set.get(&hash) { diffs[i][j]-=cnt as isize; } } left_set.insert_one(rh[i].rolling_hash_of_subsequence(0, s[i].len(), &b)); } let lcp=|(l_i,l_j):(usize,usize),(r_i,r_j):(usize,usize)| { let l_len=s[l_i].len()-l_j; let r_len=s[r_i].len()-r_j; binary_search(0, l_len+r_len+1, |mid| { if mid<=min(l_len,r_len) { rh[l_i].rolling_hash_of_subsequence(l_j, l_j+mid, &b)==rh[r_i].rolling_hash_of_subsequence(r_j, r_j+mid, &b) } else if mid<=max(l_len,r_len) { if l_len>r_len { rh[l_i].rolling_hash_of_subsequence(l_j, l_j+r_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j, s[r_i].len(), &b) && rh[l_i].rolling_hash_of_subsequence(l_j+r_len, l_j+mid, &b)==rh[l_i].rolling_hash_of_subsequence(l_j, l_j+mid-r_len, &b) } else { rh[l_i].rolling_hash_of_subsequence(l_j, s[l_i].len(), &b)==rh[r_i].rolling_hash_of_subsequence(r_j, r_j+l_len, &b) && rh[r_i].rolling_hash_of_subsequence(r_j, r_j+mid-l_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j+l_len, r_j+mid, &b) } } else { if l_len>r_len { rh[l_i].rolling_hash_of_subsequence(l_j, l_j+r_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j, s[r_i].len(), &b) && rh[l_i].rolling_hash_of_subsequence(l_j+r_len, l_j+l_len, &b)==rh[l_i].rolling_hash_of_subsequence(l_j, l_j+l_len-r_len, &b) && rh[r_i].rolling_hash_of_subsequence(r_j, r_j+mid-l_len, &b)==rh[l_i].rolling_hash_of_subsequence(l_j+l_len-r_len, l_j+mid-r_len, &b) } else { rh[l_i].rolling_hash_of_subsequence(l_j, s[l_i].len(), &b)==rh[r_i].rolling_hash_of_subsequence(r_j, r_j+l_len, &b) && rh[r_i].rolling_hash_of_subsequence(r_j, r_j+r_len-l_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j+l_len, r_j+r_len, &b) && rh[r_i].rolling_hash_of_subsequence(r_j+r_len-l_len, r_j+mid-l_len, &b)==rh[l_i].rolling_hash_of_subsequence(l_j, l_j+mid-r_len, &b) } } }) }; suffixes.sort_by(|&(l_i,l_j),&(r_i,r_j)| { let l_len=s[l_i].len()-l_j; let r_len=s[r_i].len()-r_j; let lcp=lcp((l_i,l_j),(r_i,r_j)); if lcp==l_len+r_len { Ordering::Equal } else { s[l_i][l_j+lcp%l_len].cmp(&s[r_i][r_j+lcp%r_len]) } }); let mut ans=inv_num; let mut inv_diff_sum=0; for i in 0..suffixes.len()-1 { let (l_i,l_j)=suffixes[i]; let (r_i,r_j)=suffixes[i+1]; let l_len=s[l_i].len()-l_j; let r_len=s[r_i].len()-r_j; inv_diff_sum+=diffs[l_i][l_j]; let lcp=lcp((l_i,l_j),(r_i,r_j)); if lcp!=l_len+r_len { ans.chmin((inv_num as isize+inv_diff_sum) as usize+lcp+1); } } let (l_i,l_j)=suffixes[suffixes.len()-1]; let z=vec!['z']; inv_diff_sum+=diffs[l_i][l_j]; let xy=s[l_i][l_j..].iter().chain(z.iter()).collect::<String>(); let yx=z.iter().chain(s[l_i][l_j..].iter()).collect::<String>(); let xy_rh=xy.calculate_rolling_hashes('a', &b); let yx_rh=yx.calculate_rolling_hashes('a', &b); let lcp=binary_search(0, xy.len()+1, |mid| { xy_rh.rolling_hash_of_subsequence(0, mid, &b)==yx_rh.rolling_hash_of_subsequence(0, mid, &b) }); if lcp!=xy.len() { ans.chmin((inv_num as isize+inv_diff_sum) as usize+lcp+1); } outputln!(ans); }
ABC346を解き直しました。
コンテスト時はA～Eの5完でした。5連敗とはいえ、今回は流石に青時代も冷えていたと思います…
復習したときのメモを動画にして提出したもののみ載せます。
www.nicovideo.jp
www.youtube.com
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,a:[usize;n]); vec_range(0..n-1, |i| a[i]*a[i+1]).outputln(); }
use itertools::Itertools; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(w:usize,b:usize); let p="wbwbwwbwbwbwwbwbwwbwbwbw".chars().collect_vec(); let wrem=(w.saturating_sub(1))/7; if b<wrem*5 { return output_no(); } let (w,b)=(w-wrem*7,b-wrem*5); for i in 0..12 { let (mut wcnt,mut bcnt)=(0,0); for j in i..24 { if wcnt>w { break; } if p[j]=='w' { wcnt+=1; } else { bcnt+=1; } if wcnt==w && bcnt==b { return output_yes(); } } } output_no(); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize,mut a:[usize;n]); a.sort_and_dedup(); let mut ans=k*(k+1)/2; for a in a { if a>k { break; } ans-=a; } outputln!(ans); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Chars; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,mut s:Chars,c:[usize;n]); for i in (1..n).step_by(2) { if s[i]=='1' { s[i]='0'; } else { s[i]='1'; } } let zero_cost=vec_range(0..n, |i| c[i]*(s[i]=='1') as usize); let one_cost=vec_range(0..n, |i| c[i]*(s[i]=='0') as usize); let zero_sum=zero_cost.construct_prefix_sum(); let one_sum=one_cost.construct_prefix_sum(); let mut ans=usize::MAX; for i in 1..n { ans.chmin(zero_sum.calculate_partial_sum(0, i)+one_sum.calculate_partial_sum(i, n)); ans.chmin(one_sum.calculate_partial_sum(0, i)+zero_sum.calculate_partial_sum(i, n)); } outputln!(ans); }
use std::collections::BTreeSet; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(h:usize,w:usize,m:usize,tax:[(usize,Usize1,usize);m]); let mut ans=MultiSet::new(); let mut h_set=BTreeSet::new(); let mut w_set=BTreeSet::new(); for &(t,a,x) in tax.iter().rev() { if t==1 { if !h_set.contains(&a) && w>w_set.len() { ans.increase(x, w-w_set.len()); h_set.insert(a); } } else { if !w_set.contains(&a) && h>h_set.len() { ans.increase(x, h-h_set.len()); w_set.insert(a); } } } if h>h_set.len() && w>w_set.len() { ans.increase(0, (h-h_set.len())*(w-w_set.len())); } outputln!(ans.len()); for (&c,&x) in &ans { outputln!(c,x); } }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Chars; use superslice::Ext; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,s:Chars,t:Chars); let s_len=s.len(); let t_len=t.len(); let mut poss=vec![vec![];26]; for i in 0..s_len { poss[s[i].from_lowercase()].push(i); } for i in 0..s_len { poss[s[i].from_lowercase()].push(i+s_len); } outputln!(binary_search(0, E[18], |k| { let mut idx=0; for i in 0..t_len { if let Some(next_idx)=next(s_len, t_len, &poss, t[i].from_lowercase(), idx, k) { if next_idx>=s_len*n { return false; } idx=next_idx+1; } else { return false; } } true })); } fn next(s_len: usize, t_len: usize, poss: &Vec<Vec<usize>>, c: usize, idx: usize, k: usize) -> Option<usize> { let ccnt=poss[c].len()/2; if ccnt==0 { return None; } if k>ccnt { let res=(k-1)/ccnt; return next(s_len, t_len, poss, c, idx+res*s_len, k-res*ccnt); } if idx>=s_len { let res=idx/s_len*s_len; return if let Some(next)=next(s_len, t_len, poss, c, idx-res, k) { Some(next+res) } else { None }; } let pos=poss[c].lower_bound(&idx); if pos+k-1>=poss[c].len() { return None; } Some(poss[c][pos+k-1]) }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,a:[Usize1;n]); let mut idcs=vec![vec![0];n]; for i in 0..n { idcs[a[i]].push(i+1); } for i in 0..n { idcs[i].push(n+1); } let mut pq=RevBinaryHeap::<(usize,usize,usize,bool)>::new(); for i in 0..n { if idcs[i].len()<3 { continue; } for j in 0..idcs[i].len()-2 { pq.push((idcs[i][j],idcs[i][j+1],idcs[i][j+2],true)); pq.push((idcs[i][j+1],idcs[i][j+1],idcs[i][j+2],false)); } } let mut union=SetUnion::new(n+1); let mut ans=0usize; for i in 0..n+1 { while let Some(&(t,left,right,is_insert))=pq.peek() { if t==i { pq.pop(); } else { break; } if is_insert { union.insert_range(left..right); } else { union.remove_range(left..right); } } ans+=union.all_count(); } outputln!(ans); }
ARC174を解き直しました。
コンテスト時はAの1完でした。正直、本当に苦しいです…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,c:isize,a:[isize;n]); let asum=a.sum(); let mut ans=asum; if c>1 { ans.chmax(asum+a.maximum_subarray()*(c-1)); } else if c<1 { ans.chmax(asum+a.minimum_subarray()*(c-1)); } outputln!(ans); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(t:usize); for _ in 0..t { input!(mut a:[usize;5],mut p:[usize;5]); a.move_right(1, 0); p.move_right(1, 0); let top=vec_range(1..=5, |i| i*a[i]).sum(); let bottom=a.sum(); let average=top/bottom; if average>=3 { outputln!(0); continue; } let f=2*a[1]+a[2]-a[4]-2*a[5]; if p[5]>2*p[4] { outputln!(f*p[4]); } else if f%2==0 || p[5]<p[4] { outputln!((f+1)/2*p[5]); } else { outputln!(f/2*p[5]+p[4]); } } }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize); let ninv=Mint::new(1)/n; let mut ans=vec![vec![Mint::new(1),Mint::new(0),Mint::new(0)],vec![Mint::new(0),Mint::new(1),Mint::new(0)]]; for i in 1..=n { let tmp=ans[0][2]; ans[0][2]=ans[1][2]; ans[1][2]=tmp; ans[0][0]=Mint::new(1); ans[0][1]=-Mint::new(n-i)*ninv; ans[0][2]*=Mint::new(i)*ninv; ans[0][2]+=Mint::new(n-i)*ninv; ans[1][0]=-Mint::new(n-i)*ninv; ans[1][1]=Mint::new(1); ans[1][2]*=Mint::new(i)*ninv; ans=ans.gaussian_elimination(); } outputln!(ans[0][2],ans[1][2]); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(t:usize); let mut ranges=RangeSet::<usize>::new(); ranges.insert_number(1); for i in 1..=9 { ranges.insert_number(E[2*i]-2*E[i]); ranges.insert_range(E[2*i]-E[i]..E[2*i]+E[i]); } for _ in 0..t { input!(n:usize); let mut ranges=ranges.clone(); ranges.remove_range(n+1..2*E[18]); let mut ans=0; for (l,r) in ranges.ranges() { ans+=r-l; } outputln!(ans); } }
use ac_library::{FenwickTree, LazySegtree}; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize,p:[Usize1;k]); let mut ans=vec![Mint::new(0);n]; let mut lst=LazySegtree::<RangeAffineTransform<DummyOperation<Mint>>>::new(n); let mut cnt=FenwickTree::new(n, 0); let mut contains=vec![false;n]; let invs=Mint::construct_modint_inverses(n); let facts=Mint::construct_modint_facts(n); let factinvs=Mint::construct_modint_fact_inverses(n, &invs); let npr=|n:usize,r:usize| facts[n]*factinvs[n-r]; for i in 0..n { cnt.add(i, 1); } for i in 0..k { let c=cnt.sum(0..p[i]) as usize; lst.apply_range(0..p[i], (Mint::new(1),npr(n-i-1,k-i-1))); if i<k-1 { lst.apply_range(0..p[i], (Mint::new(1),npr(n-i-1,k-i-1)*c.saturating_sub(1)*(k-i-1)*invs[n-i-1])); lst.apply_range(p[i]..n, (Mint::new(1),npr(n-i-1,k-i-1)*c*(k-i-1)*invs[n-i-1])); } ans[p[i]]=lst.get(p[i]); cnt.add(p[i], -1); contains[p[i]]=true; } let mut sum=Mint::new(1); for i in (0..k).rev() { cnt.add(p[i], 1); let c=cnt.sum(0..p[i]) as usize; ans[p[i]]+=sum; sum+=npr(n-i-1,k-i-1)*c; } for i in 0..n { if !contains[i] { ans[i]=lst.get(i); } } ans.outputlns(); }
use std::collections::BTreeMap; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,lr:[(isize,isize);n],q:usize); let lens=DoublyLinkedList::<(isize,usize,usize)>::new(); let mut offset=[0,0]; let mut m=[BTreeMap::<(isize,usize),RcRefCellDoublyLinkedListNode<(isize,usize,usize)>>::new(),BTreeMap::<(isize,usize),RcRefCellDoublyLinkedListNode<(isize,usize,usize)>>::new()]; for i in (0..n).rev() { let (l,r)=lr[i]; let me=i%2; let you=1-me; offset[me]+=r-l; offset[you]-=r-l; m[you].insert((l-offset[you],i), lens.push_front((l-offset[you],you,i)).unwrap()); let mut inserts=BTreeMap::<(isize,usize),RcRefCellDoublyLinkedListNode<(isize,usize,usize)>>::new(); let mut removes=[vec![],vec![]]; for (&(len,idx),node) in m[you].range((isize::MIN,0)..=(-offset[you],n-1)) { removes[you].push((len,idx)); if node.borrow().get().is_none() { continue; } let (m_len,r_len)=if let Some((next_len,_,next_idx))=node.borrow_mut().remove_next() { if inserts.contains_key(&(next_len,next_idx)) { inserts.remove(&(next_len,next_idx)); } removes[me].push((next_len,next_idx)); (len+offset[you],next_len+offset[me]) } else { (0,0) }; let (l_len,_,l_idx)=node.borrow().prev().unwrap().borrow().get().unwrap(); if inserts.contains_key(&(l_len,l_idx)) { inserts.remove(&(l_len,l_idx)); } removes[me].push((l_len,l_idx)); node.borrow().prev().unwrap().borrow_mut().set((l_len+m_len+r_len,me,l_idx)); inserts.insert((l_len+m_len+r_len,l_idx), node.borrow().prev().unwrap()); node.borrow_mut().remove(); } for player in 0..2 { for key in &removes[player] { m[player].remove(key); } } for (key,val) in &inserts { m[me].insert(*key, val.clone()); } } let mut ranges=[RangeSet::<isize>::new(),RangeSet::<isize>::new()]; let mut cur=0; for node in &lens { let (len,player,_)=node.borrow().get().unwrap(); if len+offset[player]<=0 { eoutputln!(cur,len,player,len+offset[player]); } ranges[player].insert_range(cur..cur+(len+offset[player])); cur+=len+offset[player]; } for _ in 0..q { input!(c:isize); outputln!(match (ranges[0].contains(c),ranges[1].contains(c)) { (true,false) => "Alice", (false,true) => "Bob", _ => "Draw" }); } }
ABC345を解き直しました。
コンテスト時はA～Cの3完でした。DかEかFのどれか1問はせめて解けただろう…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Chars; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(s:Chars); let srle=s.rle(); output_yes_or_no(srle.len()==3 && srle==vec![('<',1),('=',s.len()-2),('>',1)]); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num::Integer; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(x:isize); outputln!(x.div_ceil(&10)); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Chars; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(s:Chars); let l=s.len(); let mut cnt=vec![0;26]; for i in 0..l { cnt[s[i].from_lowercase()]+=1; } let mut ans=0usize; let mut same=0; for i in 0..26 { ans+=cnt[i]*(l-cnt[i]); if cnt[i]>1 { same=1; } } ans/=2; ans+=same; outputln!(ans); }
use itertools::Itertools; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use superslice::Ext; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,h:usize,w:usize,ab:[[usize;2];n]); for s in 0..1<<n { let mut p=(0..n).filter(|&k| s&(1<<k)>0).collect_vec(); do_while!(p.next_permutation(), { if dfs(h, w, &ab, p.len(), &p, 0, 0, 0) || dfs(h, w, &ab, p.len(), &p, 0, 1, 0) { outputln!("Yes"); return; } }) } outputln!("No"); } fn dfs(h:usize,w:usize,ab:&Vec<Vec<usize>>,l:usize,p:&Vec<usize>,k:usize,dir:usize,mut tile:u128) -> bool { let min=tile.trailing_ones() as usize; if k==l { return min==h*w; } let (m_i,m_j)=(min/w,min%w); for i in m_i..m_i+ab[p[k]][dir] { if i>=h { return false; } for j in m_j..m_j+ab[p[k]][1-dir] { if j>=w { return false; } if tile&(1<<(i*w+j))>0 { return false; } tile+=1<<(i*w+j); } } dfs(h, w, ab, l, p, k+1, 0, tile) || dfs(h, w, ab, l, p, k+1, 1, tile) }
use std::collections::VecDeque; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize,cv:[(Usize1,usize);n]); let mut dp=VecDeque::from(vec![vec![];k+1]); dp[0]=vec![(0,n)]; for i in 0..n { let (c,v)=cv[i]; dp.push_front(vec![]); for j in 0..=k { if dp[j+1].len()>0 { if c!=dp[j+1][0].1 { let tmp=dp[j+1][0].0+v; let mut c_exists=false; for vc in &mut dp[j] { if vc.1==c { vc.0.chmax(tmp); c_exists=true; break; } } if !c_exists { dp[j].push((tmp,c)); } } else { if dp[j+1].len()>1 { let tmp=dp[j+1][1].0+v; let mut c_exists=false; for vc in &mut dp[j] { if vc.1==c { vc.0.chmax(tmp); c_exists=true; break; } } if !c_exists { dp[j].push((tmp,c)); } } } } dp[j].sort_by(|l,r| r.cmp(l)); if dp[j].len()>2 { dp[j].pop(); } } dp.pop_back(); } if dp[k].len()>0 { outputln!(dp[k][0].0); } else { outputln!(-1); } }
use std::collections::BTreeSet; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,m:usize,k:usize,uv:[(Usize1,Usize1);m]); let mut ans=vec![]; if k==0 { outputln!("Yes"); outputln!(0); ans.outputln(); return; } let uvi=vec_range(0..m, |i| (uv[i].0,uv[i].1,i+1)); let g=VecGraph::construct_weighted_graph(n, m, &uvi); let mut yet=BTreeSet::new(); for v in 0..n { yet.insert(v); } let mut par=vec![0;n]; let mut num=vec![0;n]; let mut lamp=vec![false;n]; let mut cnt=0; while let Some(start)=yet.pop_first() { par[start]=start; num[start]=m; for gs in g.dfs_postorder(start) { match gs { GraphSearch::Vertex(true, v) => { yet.remove(&v); }, GraphSearch::VertexEdgeWeight(v, u, w) => { par[u]=v; num[u]=w; }, GraphSearch::Vertex(false, v) => { if par[v]==v { continue; } if !lamp[v] { lamp[v]=true; cnt+=1; cnt-=lamp[par[v]] as usize; lamp[par[v]]=!lamp[par[v]]; cnt+=lamp[par[v]] as usize; ans.push(num[v]); } if cnt==k { outputln!("Yes"); outputln!(ans.len()); ans.outputln(); return; } } } } } outputln!("No"); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num_integer::Roots; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize); let mut a=vec![Mint::new(0);n+1]; let kinv=Mint::new(1)/k; if k>n.sqrt()/(n+1).ilog2() as usize { a[0]+=1; let invs=Mint::construct_modint_inverses(2*n+1); let facts=Mint::construct_modint_facts(2*n+1); let factinvs=Mint::construct_modint_fact_inverses(2*n+1, &invs); let sgn=|r:usize| if r%2>0 { -1 } else { 1 }; let binom=|n:usize,r:usize| if n>=r { facts[n]*factinvs[r]*factinvs[n-r] } else { Mint::new(0) }; let neg_binom=|n:usize,r:usize| { binom(n+r-1,n-1)*sgn(r) }; let mut kinvpow=kinv; for i in 1..n { let d=n-1-i; for j in 0..=d/k { a[i]+=binom(i,j)*sgn(j)*neg_binom(i+1,d-j*k)*sgn(d-j*k); } a[i]*=kinvpow; kinvpow*=kinv; } } else { let mut f=vec![kinv;k+1]; f[0]*=0; dc(n, k, &f, &mut a, 0, n+1, vec![Mint::new(1);n]); } let p=vec_range(1..=n, |i| a[i-1]-a[i]); p.outputlns(); } fn dc(n:usize,k:usize,f:&Vec<Mint>,a:&mut Vec<Mint>,l:usize,r:usize,mut g:Vec<Mint>) -> Vec<Mint> { if l+1==r { a[l]=*g.last().unwrap(); return f.clone(); } let len=min(n, (r-l-1)*k+1); g.drain(0..(g.len()-len)); let m=(l+r)/2; let mut fpow=dc(n, k, f, a, l, m, g.clone()); g.fps_mul_assign(&fpow, len-1); let fpow2=dc(n, k, f, a, m, r, g.clone()); fpow.fps_mul_assign(&fpow2, min(n-1, fpow.len()+fpow2.len()-2)); fpow }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize); let kinv=Mint::new(1)/k; let mut f=vec![kinv;k+1]; f[0]*=0; let mut p=f.fps_pow_coefficients(n+1, n); for i in 1..=n { p[i]*=Mint::new(k)+1-Mint::new(n)/i; } p[1..].outputlns(); }
ARC173を解き直しました。
コンテスト時はAの1完でした。
落水しました。Bの予想が完全に正しかったようなのでダメ元で提出すべきでした。
やっぱり、ある程度時間を使ってしまったらペナ上等でいくべきですね…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(t:usize); for _ in 0..t { input!(k:usize); outputln!(usize_binary_search(E[18], false, |mid| { let mut m=mid; let mut cnt=0; let mut p=1; let mut s=vec![]; while m>0 { s.push((m%10,p)); m/=10; if p>1 { cnt+=p; } p*=9; } let mut prev_c=0; while let Some((c,p))=s.pop() { cnt+=if c==0 || prev_c>=c { c*p } else { (c-1)*p }; if prev_c==c { break; } if p==1 { cnt+=1; } prev_c=c; } cnt>=k })); } }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,mut xy:[(isize,isize);n]); xy.sort(); let mut ans=n/3; for i in 0..n { for j in i+1..n { let mut cnt=0; for k in 0..n { if (xy[j].0-xy[i].0)*(xy[k].1-xy[j].1)!=(xy[j].1-xy[i].1)*(xy[k].0-xy[j].0) { cnt+=1; } } ans.chmin(cnt); } } outputln!(ans); }
use std::collections::BTreeSet; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,p:[Usize1;n]); let mut ans=vec![usize::MAX;n]; let mut gcnt=0; let mut lcnt=0; for i in 1..n { if p[i]>p[0] { gcnt+=1; } else { lcnt+=1; } if i%2==0 && gcnt!=lcnt { ans[0]=i+1; break; } } let mut gcnt=0; let mut lcnt=0; for i in (0..n-1).rev() { if p[i]>p[n-1] { gcnt+=1; } else { lcnt+=1; } if (n-1-i)%2==0 && gcnt!=lcnt { ans[n-1]=n-i; break; } } for i in 1..n-1 { if (p[i-1]>p[i])==(p[i+1]>p[i]) { ans[i]=3; } } let mut s=BTreeSet::new(); for i in 0..n-1 { if p[i]>0 && p[i+1]>0 { s.insert(i); } } let mut pinv=vec![0;n]; for i in 0..n { pinv[p[i]]=i; } for cur_p in 0..n { let idx=pinv[cur_p]; if cur_p>0 { if idx>0 { s.remove(&(idx-1)); } if idx<n-1 { s.remove(&idx); } } if idx>0 && idx<n-1 && ans[idx]==usize::MAX { if let Some(&lmax)=s.range(0..idx).last() { ans[idx].chmin(if (idx-lmax+1)%2>0 { idx-lmax+1 } else { idx-lmax+2 }); } if let Some(&rmin)=s.range(idx..n).next() { let rmin=rmin+1; ans[idx].chmin(if (rmin-idx+1)%2>0 { rmin-idx+1 } else { rmin-idx+2 }); } } if cur_p<n-1 { if idx>0 && p[idx-1].cmp(&(cur_p+1))==p[idx].cmp(&(cur_p+1)) { s.insert(idx-1); } if idx<n-1 && p[idx].cmp(&(cur_p+1))==p[idx+1].cmp(&(cur_p+1)) { s.insert(idx); } } } ans.outputln_val_or(usize::MAX); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,p:[Usize1;n]); let mut ans=vec![usize::MAX;n]; let mut gcnt=0; let mut lcnt=0; for i in 1..n { if p[i]>p[0] { gcnt+=1; } else { lcnt+=1; } if i%2==0 && gcnt!=lcnt { ans[0]=i+1; break; } } let mut gcnt=0; let mut lcnt=0; for i in (0..n-1).rev() { if p[i]>p[n-1] { gcnt+=1; } else { lcnt+=1; } if (n-1-i)%2==0 && gcnt!=lcnt { ans[n-1]=n-i; break; } } for i in 1..n-1 { if (p[i-1]>p[i])==(p[i+1]>p[i]) { ans[i]=3; } else { let mut l=i-1; while l>0 { l-=1; if (p[l]>p[i])==(p[l+1]>p[i]) { ans[i].chmin(if (i-l+1)%2>0 { i-l+1 } else { i-l+2 }); break; } } let mut r=i+1; while r<n-1 { r+=1; if (p[r]>p[i])==(p[r-1]>p[i]) { ans[i].chmin(if (r-i+1)%2>0 { r-i+1 } else { r-i+2 }); break; } } } } ans.outputln_val_or(usize::MAX); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::Usize1; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,m:usize,uvc:[(Usize1,Usize1,char);m]); let uvw=vec_range(0, m, |i| (uvc[i].0,uvc[i].1,if uvc[i].2=='(' { -1 } else { 1 })); let g=IsizeGraph::construct_weighted_directed_graph(n, m, &uvw); let exists_1=g.rough_bellman_ford(0).is_none(); let g=IsizeGraph::construct_inversed_weighted_directed_graph(n, m, &uvw); let exists_2=g.rough_bellman_ford(0).is_none(); output_yes_or_no(!(exists_1^exists_2)); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,a:[usize;n]); if n==2 || n%4!=2 { outputln!(vec_range(0, n-1, |i| a[0]^a[i+1]).subset_xor_max()); } else { let mut ans=vec_range(0, n-2, |i| a[1]^a[i+2]).subset_xor_max(); for j in 0..n-1 { ans.chmax(vec_range(0, n-2, |i| a[0]^if i<j { a[i+1] } else { a[i+2] }).subset_xor_max()); } outputln!(ans); } }
こんにちは、ARC173で水落ちした獅子座じゃない人です。
ARC173のE問題が単純な問題設定で一見単純な答えでありつつも、とても非自明な場合分けが必要であると感じました。
また、ARC-Eだけあって解説もとても行間が広く、行間を埋めたり別のアプローチをとって証明を試みたところ、さらに面白く感じたのでまとめます。
atcoder.jp
元の問題文で理解できる問題設定だと思いますが、一応書いておきます。
長さの非負整数列
が入力として与えられます。
非負整数の二項演算で、二進表記の各桁についてXORをとるものを、ビット単位XOR演算と定義しておきます。
という操作を回繰り返した後、
は長さ
の整数列になっています。
その唯一の要素をとしたとき、
としてありえる非負整数の最大値を出力する問題となります。
この問題は、としてありえる非負整数の条件を考察し、条件を満たす非負整数の最大値を求めることで解くことができます。
そして、としてありえる非負整数の条件がとても非自明で面白いと感じました。
操作の前半は、の長さを
、ある
の置換を
として、
という変換を行うと考えることができます。
ここで、が等しい操作を同じ操作であると定義します。
また、長さがともにである非負整数列
と
について、
という演算を定義しておきます。
長さがの
と
、
に同じ操作を行うことを考えます。
まず、操作の前半では、は
、
は
、そして
は
に変換されます。
したがって、という関係は保たれます。
改めて添字をおき直し、操作の後半について考えます。
操作の後半では、は
、
は
、そして
は
に変換されます。
の交換法則より、
という関係は保たれます。
以上より、、
と同じ操作を
に行った結果は、新たな
、
についての
になることがわかりました。
また、の性質より、列の要素は
か
であるとしてしまって問題ありません。
二進の各桁について新たな列を作り、それぞれに同じ操作を行ったと考えることができます。
か
からなる長さ
の列について、第
項のみが
で他の項は全て
であるものを
とします。
操作の性質から、各に同じ
回の操作を行って得られる
の組み合わせについて考えればよいです。
結論を先に述べます。
ある回の操作によって
個の
が
となった場合、
個の
が
となる全ての組み合わせについて、それを得る
回の操作が存在します。
したがって、となる
の個数
についてのみ注目すればよいです。
または
の場合、
は
以上
以下の全ての偶数をとります。
かつ
の場合、
は
以上
以下の全ての偶数をとります。
ある回の操作によって
個の
が
となった場合、
個の
が
となる全ての組み合わせについて、それを得る
回の操作が存在することを、まず証明します。
一回目の操作で並び替えを行うことは、の列を置換したのと同じになります。
したがって、一回目の操作で並び替えを行わなかった場合ととなる
の個数は同じになり、一回目の操作で並び替えを適当に行うことで
個の
が
となる任意の組み合わせに対応する操作を考えることができます。
次に、ありうるが上のようになることを数学的帰納法で証明します。
まず、について、
に操作を行うと
が得られ、
に操作を行うと
が得られることから示されます。
次に、で成り立つことを仮定し、
について考えます。
一回目の操作で並び替えを行わないとします。
すると、から得られる
は
と
に同じ
回の操作を行って得られる
（それぞれ
とします）についての
になります。
第項のみが
で他の項は全て
である長さ
の列に、ある
回の操作を行って得られる
を
とします。以降、この記法を複数用いる場合、全て同じ操作であることを仮定します。
から得られる
は
、
から得られる
は
、
から得られる
は
となります。
これをもとに、となる
の個数としてありえるものを考えることになります。
ここで、先にとなる
の個数の偶奇について先に考えておきます。
和の偶奇のみを求めるのはまさしくXORそのものです。
より、
となる
の個数は偶数であることがわかります。
または
の場合
となる個数は
が考えられます。
したがって、以外の
は自由に決めることができます。ただし、全ての
が
である場合のみ作れません。
つまり、以外から得られる
個の
は自由に決めることができます。ただし、
までから得られる全ての
が
である場合のみ作れません。
また、となる
以外の
の個数が奇数であった場合、必ず
から得られる
の片方のみが
となります。
よって、となる
の個数として、
から
までの全ての偶数がありえることがいえました。
また、となる
の個数を
にすることはできないこともいえるため、
となる
の個数としてありえるのは、
以上
以下の全ての偶数であることがわかりました。
かつ
の場合
となる個数は
が考えられます。
全てのを
にできないことのみ、
の場合と異なります。
しかし、全てのが
である場合の
となる
の個数は
個であり、別の
の組み合わせによって達成できます。
よって、と同様の議論により、
となる
の個数としてありえるのは、
以上
以下の全ての偶数であることがわかりました。
の場合
となる個数は
が考えられます。
したがって、以外の
は自由に決めることができます。
つまり、以外から得られる
個の
は自由に決めることができます。
ほとんどの偶数についてはと同様の議論により、達成できることがいえます。しかし、
と
については別に考える必要があります。
となる
の個数を
にするには、
となる個数が
である必要があり、これは無理です。
一方、となる
の個数を
にするには、
となる個数が
である必要があります。
は偶数であり、問題ありません。
よって、となる
の個数としてありえるのは、
以上
以下の全ての偶数であることがわかりました。
かつ
の場合
となる個数は
が考えられます。
と同様の議論をすることができますが、
の場合と異なり、
は奇数となります。
よって、となる
の個数を
にすることはできないことがいえ、
となる
の個数としてありえるのは、
以上
以下の全ての偶数であることがわかりました。
以上より、ありうるが上のようになることがいえました。
この条件を、一般のに応用します。
の二進での
桁目を
とします。
元の非負整数列の二進の各桁について新たな列を作り、それぞれに同じ操作を行ったと考えます。
すると、各列はを使って、
と表せます。
したがって、からある
回の操作を行って得られる
を
として、各列から得られる
は
と表せます。
XORの単位元がであり、
も
もともに
か
をとることから、
と書き換えられます。
各桁に対してのこの結果を合わせると、から得られる
としてありえるのは
の形であることがわかりました。
結局、長さの
から得られる
として、
から好きに
個とった総ビット単位XOR演算の結果が全てありえることがわかりました。
ここで、または
の場合、
は
以上
以下の全ての偶数をとり、
かつ
の場合、
は
以上
以下の全ての偶数をとります。
まず、を考えると、それから一部をとっての総ビット単位XOR演算は必ず
から偶数個とった総ビット単位XOR演算と同じになります。
より、
から奇数個とっての総ビット単位XOR演算は
を含んで偶数個とった総ビット単位XOR演算となります。
そして、から偶数個とっての総ビット単位XOR演算は
を含まず偶数個とった総ビット単位XOR演算となります。
したがって、この問題はの部分集合の総ビット単位XOR演算の最大値を求める問題に帰着されます。
この問題は有名問題であり、たとえばこのような方法で時間（ただし
は二進での桁数）で求めることができます。
www.geeksforgeeks.org
から一つもとらない場合は
なので気にする必要はないですが、
かつ
の場合は
から全て選んでしまう場合を考慮する必要があります。
を使わない場合を全探索すればよく、この場合でも時間
で求められます。
公式解説では、noshi基底を用いて線形独立でない場合やそもそもから全て選んで最大値にならない場合を先に省いていますが、それをしなくても最悪計算量のオーダーは変わりません。（もちろん最良計算量のオーダーは変わります。）
