ABC341を解き直しました。
コンテスト時はA～Eの5完でした。苦しかったです。
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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); for _ in 0..n { print!("10"); } println!("1"); }
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!(n:usize,mut a:[usize;n],st:[(usize,usize);n-1]); for i in 0..n-1 { a[i+1]=a[i+1]+a[i]/st[i].0*st[i].1; } outputln!(a[n-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!(h:usize,w:usize,_:usize,t:Chars,s:[Chars;h]); let mut ans=0; for i in 1..h-1 { for j in 1..w-1 { if s[i][j]=='#' { continue; } let mut cur_i=i; let mut cur_j=j; let mut ok=true; for &c in t.iter().rev() { macro_rules! matches { ($cond:expr,$next_i:expr,$next_j:expr) => { if $cond && s[$next_i][$next_j]=='.' { cur_i=$next_i; cur_j=$next_j; } else { ok=false; break; } }; } match c { 'L' => matches!(cur_j<w-1,cur_i,cur_j+1), 'R' => matches!(cur_j>0,cur_i,cur_j-1), 'U' => matches!(cur_i<h-1,cur_i+1,cur_j), 'D' => matches!(cur_i>0,cur_i-1,cur_j), _ => () }; } if ok { ans+=1; } } } outputln!(ans); }
D問題
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num_integer::lcm; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,m:usize,k:usize); outputln!(binary_search(E[18], 0, |mid| { mid/n+mid/m-mid/lcm(n, m)*2>=k })); }
E問題
use ac_library::LazySegtree; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::marker::{Chars, Usize1}; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,q:usize,s:Chars); let mut lst=LazySegtree::<RangeAffineRangeSum<Add<isize>>>::new(n); for i in 0..n { if (s[i]=='1') ^ (i%2>0) { lst.set(i, (1,1)); } else { lst.set(i, (0,1)); } } for _ in 0..q { input!(q:usize,l:Usize1,r:usize); if q==1 { lst.apply_range(l..r, (-1,1)); } else { let prod=lst.prod(l..r); output_yes_or_no(prod.0==0 || prod.0==prod.1 as isize); } } }
F問題
#[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,uv:[(Usize1,Usize1);m],w:[usize;n],a:[usize;n]); let g=VecGraph::construct_graph(n, m, &uv); let mut dp=vec![0;n]; let mut ws=vec_range(0, n, |i| (w[i],i)); ws.sort(); for (weight,idx) in ws { let list=&g.get()[idx]; let l=list.len(); let mut knapsack=vec![vec![0;weight];l+1]; for i in 0..l { for j in 0..weight { let tmp=knapsack[i][j]; knapsack[i+1][j].chmax(tmp); if j>=w[list[i].0] { let tmp=knapsack[i][j-w[list[i].0]]+dp[list[i].0]; knapsack[i+1][j].chmax(tmp); } } } dp[idx]=1+knapsack[l].iter().max().unwrap(); } let mut ans=0; for i in 0..n { ans+=dp[i]*a[i]; } outputln!(ans); }
G問題
#[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 stack=vec![(0.,0.)]; let mut ans=vec![0.;n]; let mut cnt=0.; let mut sum=0.; for i in (0..n).rev() { cnt+=1.; sum-=a[i] as f64; while stack.len()>1 && intersection(stack.get_from_last(2), &(cnt,sum))<intersection(stack.get_from_last(2), stack.get_from_last(1)) { stack.pop(); } stack.push((cnt,sum)); ans[i]=intersection(stack.get_from_last(2), stack.get_from_last(1)); } for ans in ans { outputln!(ans); } } fn intersection(l1: &(f64,f64), l2: &(f64,f64)) -> f64 { (l2.1-l1.1)/(l1.0-l2.0) }
