ABC342を解き直しました。
コンテスト時はA～Dの4完でした。Fが合ってたのに合っていないと思い込んで提出しなかったのが痛恨すぎる…（レート+300のパフォだったはずがレート-300のパフォになりました…）
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
A問題
#[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 majority=if s[0]==s[1] { s[0] } else { s[2] }; for i in 0..s.len() { if s[i]!=majority { outputln!(i+1); } } }
B問題
#[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],q:usize,ab:[(Usize1,Usize1);q]); let mut pinv=vec![0;n]; for i in 0..n { pinv[p[i]]=i; } for i in 0..q { if pinv[ab[i].0]<pinv[ab[i].1] { outputln!(ab[i].0+1); } else { outputln!(ab[i].1+1); } } }
C問題
#[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,s:Chars,q:usize,cd:[(char,char);q]); let mut results=['a';26]; for i in 0..26 { results[i]=i.to_lowercase(); for &(c,d) in &cd { if results[i]==c { results[i]=d; } } } for i in 0..n { print!("{}",results[s[i].from_lowercase()]); } println!(); }
D問題
#[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]); let mut zeros=0usize; let mut cnts=vec![0usize;2*E[5]+1]; for &a in &a { if a==0 { zeros+=1; continue; } let mut aa=a; while aa%4==0 { aa/=4; } let mut m=3; while m*m<=a { while aa%(m*m)==0 { aa/=m*m; } m+=2; } cnts[aa]+=1; } let mut ans=0usize; for cnt in cnts { ans+=(cnt)*(cnt.saturating_sub(1))/2; } ans+=(zeros)*(zeros.saturating_sub(1))/2; ans+=zeros*(n-zeros); outputln!(ans); }
E問題
#[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,ldkcab:[(usize,usize,usize,usize,Usize1,Usize1);m]); let mut g=vec![vec![];n]; for &(l,d,k,c,a,b) in &ldkcab { g[b].push((a,c,l,d,k)); } let inf=E[19]; let mut dist=vec![usize::MAX;n]; dist[n-1]=0; let mut pq=RevBinaryHeap::<(usize,usize)>::new(); pq.push((dist[n-1],n-1)); while let Some((d,v))=pq.pop() { if dist[v]<d { continue; } for &(u,c,l,d,k) in &g[v] { if inf-dist[v]<l+c { continue; } let w=if (inf-dist[v]-c-l)/d<k { c+inf-dist[v]-(l+(inf-dist[v]-c-l)/d*d+c) } else { c+inf-dist[v]-(l+(k-1)*d+c) }; if dist[v].saturating_add(w)<dist[u] { dist[u]=dist[v].saturating_add(w); pq.push((dist[u],u)); } } } for v in 0..n-1 { outputif(dist[v]<usize::MAX, inf.saturating_sub(dist[v]), "Unreachable"); } }
F問題
use ac_library::Segtree; #[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,l:usize,d:usize); let mut dp_y=Segtree::<Add<f64>>::new(2*n+1); dp_y.set(0, 1.); for i in 1..l { dp_y.set(i, dp_y.prod(i.saturating_sub(d)..i)/d as f64); } for i in l..l+d { dp_y.set(i, dp_y.prod(i.saturating_sub(d)..l)/d as f64); } let mut dp=Segtree::<Add<f64>>::new(2*n+1); let mut ans=0.; for i in (0..=n).rev() { dp.set(i, max(1.-dp_y.prod(max(i,l)..=n),dp.prod(i+1..=i+d)/d as f64)); ans.chmax(dp.get(i)); } outputln!(dp.get(0)); }
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:[usize;n],q:usize); let mut t=RangeBinaryHeap::<MultiSet<usize>>::new(n); for i in 0..n { t.get_mut(i).insert_one(a[i]); } let mut queries=vec![(0,0,0);q]; for i in 0..q { input!(q:usize); if q==1 { input!(l:Usize1,r:usize,x:usize); queries[i]=(l,r,x); for (idx,_) in t.ranges(l..r) { t[idx].insert_one(x); } } else if q==2 { input!(i:Usize1); let (l,r,x)=queries[i]; for (idx,_) in t.ranges(l..r) { t[idx].remove_one(x); } } else { input!(i:Usize1); let mut ans=0; for i in t.indices(i) { if let Some((&val,_))=t[i].last_key_value() { ans.chmax(val); } } outputln!(ans); } } }
