ABC339を解き直しました。
コンテスト時はA～Eの5完でした。Dで遅くなりすぎてFを解けなかったのが悔しいです。
今回から、復習したときのメモを動画にして提出したもののみブログに載せることにします。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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 mut idx=0; for i in 0..s.len() { if s[i]=='.' { idx=i; } } for i in idx+1..s.len() { print!("{}",s[i]); } println!(); }
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use regex::Regex; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(s:String); outputln!(&Regex::new(r"\.([^.]*)$").unwrap().captures(&s).unwrap()[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!(h:usize,w:usize,n:usize); let mut grid=vec![vec!['.';w];h]; let i_dir=[0,1,0,h-1]; let j_dir=[1,0,w-1,0]; let mut dir=3; let mut i=0; let mut j=0; for _ in 0..n { if grid[i][j]=='.' { grid[i][j]='#'; dir+=1; } else { grid[i][j]='.'; dir+=3; } dir%=4; i+=i_dir[dir]; i%=h; j+=j_dir[dir]; j%=w; } for i in 0..h { for j in 0..w { print!("{}",grid[i][j]); } println!(); } }
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,a:[isize;n]); let mut cur=0; let mut min=0; for a in a { cur+=a; min.chmin(cur); } outputln!(cur-min); }
D問題
use std::collections::{BTreeSet, VecDeque}; #[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;n]); let mut seen_p1=false; let mut p1_i=0; let mut p1_j=0; let mut p2_i=0; let mut p2_j=0; let i_dir=[0,1,0,n-1]; let i_min=[0,0,0,1]; let i_max=[n,n-1,n,n]; let j_dir=[1,0,n-1,0]; let j_min=[0,0,1,0]; let j_max=[n-1,n,n,n]; for i in 0..n { for j in 0..n { if s[i][j]=='P' { if !seen_p1 { p1_i=i; p1_j=j; seen_p1=true; } else { p2_i=i; p2_j=j; } } } } let mut seen=BTreeSet::<(usize,usize,usize,usize)>::new(); let mut q=VecDeque::<(usize,usize,usize,usize,usize)>::new(); seen.insert((p1_i,p1_j,p2_i,p2_j)); q.push_front((p1_i,p1_j,p2_i,p2_j,0)); while let Some((p1_i,p1_j,p2_i,p2_j,cnt))=q.pop_back() { if p1_i==p2_i && p1_j==p2_j { outputln!(cnt); return; } for i in 0..4 { let mut new_p1_i=0; let mut new_p1_j=0; let mut new_p2_i=0; let mut new_p2_j=0; for (p_i,p_j,new_p_i,new_p_j) in [(p1_i,p1_j,&mut new_p1_i,&mut new_p1_j),(p2_i,p2_j,&mut new_p2_i,&mut new_p2_j)] { if i_min[i]<=p_i && p_i<i_max[i] && j_min[i]<=p_j && p_j<j_max[i] { *new_p_i=p_i+i_dir[i]; *new_p_i%=n; *new_p_j=p_j+j_dir[i]; *new_p_j%=n; if s[*new_p_i][*new_p_j]=='#' { *new_p_i=p_i; *new_p_j=p_j; } } else { *new_p_i=p_i; *new_p_j=p_j; } } if !seen.contains(&(new_p1_i,new_p1_j,new_p2_i,new_p2_j)) { seen.insert((new_p1_i,new_p1_j,new_p2_i,new_p2_j)); q.push_front((new_p1_i,new_p1_j,new_p2_i,new_p2_j,cnt+1)); } } } outputln!(-1); }
E問題
use ac_library::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,d:usize,a:[Usize1;n]); let mut st=DynamicSegtree::<Max<usize>>::new(0, 5*E[5]+d); st.set(a[0], 1); for i in 1..n { let tmp=st.prod(a[i].saturating_sub(d)..=a[i]+d)+1; if st.get(a[i])<tmp { st.set(a[i], tmp); } } outputln!(st.all_prod()); }
F問題
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num_bigint::BigUint; use num_traits::ToPrimitive; const PRIMES:[usize;3]=[1430733433,2207147981,2917238459]; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,mut a:[BigUint;n]); let mut maps=[MultiSet::<usize>::new(),MultiSet::<usize>::new(),MultiSet::<usize>::new()]; let mut mods=vec![[0,0,0];n]; for k in 0..3 { for i in 0..n { mods[i][k]=(&a[i]%PRIMES[k]).to_usize().unwrap(); maps[k].insert_one(mods[i][k]); } } let mut ans=0; for i in 0..n { for j in 0..n { let mut cnt=usize::MAX; for k in 0..3 { if let Some(&c)=maps[k].get(&((mods[i][k]*mods[j][k])%PRIMES[k]).to_usize().unwrap()) { cnt.chmin(c); } else { cnt=0; } } ans+=cnt; } } outputln!(ans); }
G問題
use std::collections::{BTreeMap, BTreeSet}; use ac_library::Additive; #[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],q:usize,alpha_beta_gamma:[(usize,usize,usize);q]); let mut set=BTreeSet::<(usize,usize)>::new(); for i in 0..n { set.insert((a[i],i)); } let mut nums=BTreeMap::<usize,usize>::new(); let mut st=PersistentSegtree::<Additive<usize>>::new(0, n-1); for &(a,i) in &set { st.set(i, a); nums.insert(a, st.current_number()); } let mut b=0; for (alpha,beta,gamma) in alpha_beta_gamma { let l=alpha^b; let r=beta^b; let x=gamma^b; let ans=if let Some((_,&num))=nums.range(..=x).last() { st.past_prod(num, l-1..r) } else { 0 }; outputln!(ans); b=ans; } }
