ABC346を解き直しました。
コンテスト時はA～Eの5完でした。5連敗とはいえ、今回は流石に青時代も冷えていたと思います…
復習したときのメモを動画にして提出したもののみ載せます。
www.nicovideo.jp
www.youtube.com
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
A問題
#[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(); }
B問題
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(); }
C問題
#[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); }
D問題
#[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); }
E問題
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); } }
F問題
#[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]) }
G問題
#[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); }
