ARC174を解き直しました。
コンテスト時はAの1完でした。正直、本当に苦しいです…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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,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); }
B問題
#[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]); } } }
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); 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]); }
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!(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); } }
E問題
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(); }
F問題
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" }); } }
