ABC344を解き直しました。
コンテスト時はA～Eの5完でした。F解きたかった…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
A問題
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!(s:String); let ss=s.split('|').collect_vec(); outputcatln!(ss[0],ss[2]); }
B問題
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use proconio::is_stdin_empty; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } let mut avec=vec![]; while !is_stdin_empty() { input!(a:usize); avec.push(a); } avec.reverse(); avec.outputlns(); }
C問題
use std::collections::BTreeSet; #[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],m:usize,b:[usize;m],l:usize,c:[usize;l],q:usize,x:[usize;q]); let mut s=BTreeSet::new(); for &a in &a { for &b in &b { for &c in &c { s.insert(a+b+c); } } } for x in &x { output_yes_or_no(s.contains(x)); } }
use bitset_fixed::BitSet; #[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],m:usize,b:[usize;m],l:usize,c:[usize;l],q:usize,x:[usize;q]); let mut s=BitSet::new(3*E[8]+1); for &a in &a { for &b in &b { for &c in &c { s.set(a+b+c, true); } } } for &x in &x { output_yes_or_no(s[x]); } }
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!(t:Chars,n:usize); let l=t.len(); let mut a=vec![0;n]; let mut s=vec![vec![vec![]];n]; for i in 0..n { input!(ai:usize,si:[Chars;ai]); a[i]=ai; s[i]=si; } let mut dp=vec![vec![E[18];l+1];n+1]; dp[0][0]=0; for i in 0..n { dp[i+1]=dp[i].clone(); for j in 0..s[i].len() { for k in 0..l { let jl=s[i][j].len(); if k+jl>l { break; } if t[k..k+jl]==s[i][j] { let tmp=dp[i][k]+1; dp[i+1][k+jl].chmin(tmp); } } } } dp[n][l].output_val_or(E[18]); }
E問題
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,a:[usize;n],q:usize); let list=DoublyLinkedList::new(); let mut set=BTreeMap::new(); let mut cur=list.begin_sentinel(); for &a in &a { cur=cur.clone().borrow_mut().insert_next(a).unwrap(); set.insert(a, cur.clone()); } for _ in 0..q { input!(q:usize); if q==1 { input!(x:usize,y:usize); let xnode=set[&x].clone(); let ynode=xnode.borrow_mut().insert_next(y).unwrap(); set.insert(y, ynode); } else { input!(x:usize); let xnode=set[&x].clone(); xnode.borrow_mut().remove(); set.remove(&x); } } let mut ans=vec![]; for node in &list { ans.push(node.borrow().get().unwrap()); } ans.outputln(); }
F問題
use std::{cmp::Reverse, collections::BTreeMap}; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num::Integer; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,p:[[usize;n];n],r:[[usize;n-1];n],d:[[usize;n];n-1]); let mut dp=vec![vec![BTreeMap::<usize,(usize,Reverse<usize>)>::new();n];n]; dp[0][0].insert(p[0][0], (0,Reverse(0))); for i in 0..n { for j in 0..n { if j+1<n { let (left,right)=dp[i].split_at_mut(j+1); for (&pmax,&(cnt,Reverse(m))) in &left[j] { let pcnt=if m>=r[i][j] { 0 } else { (r[i][j]-m).div_ceil(&pmax) }; let new_pmax=max(pmax, p[i][j+1]); let tmp=(cnt+1+pcnt,Reverse(m+pcnt*pmax-r[i][j])); if !right[0].contains_key(&new_pmax) || right[0][&new_pmax]>tmp { right[0].insert(new_pmax, tmp); } } } if i+1<n { let (left,right)=dp.split_at_mut(i+1); for (&pmax,&(cnt,Reverse(m))) in &left[i][j] { let pcnt=if m>=d[i][j] { 0 } else { (d[i][j]-m).div_ceil(&pmax) }; let new_pmax=max(pmax, p[i+1][j]); let tmp=(cnt+1+pcnt,Reverse(m+pcnt*pmax-d[i][j])); if !right[0][j].contains_key(&new_pmax) || right[0][j][&new_pmax]>tmp { right[0][j].insert(new_pmax, tmp); } } } } } let mut ans=(usize::MAX,Reverse(0)); for (_,&tmp) in &dp[n-1][n-1] { ans.chmin(tmp); } outputln!(ans.0); }
use std::cmp::Reverse; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num::Integer; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,p:[[usize;n];n],r:[[usize;n-1];n],d:[[usize;n];n-1]); let mut dist=vec![vec![vec![vec![usize::MAX;n];n];n];n]; for i in 0..n { for j in 0..n { for k in i..n { for l in j..n { if (i,j)==(k,l) { dist[i][j][k][l]=0; } if l+1<n { let tmp=dist[i][j][k][l]+r[k][l]; dist[i][j][k][l+1].chmin(tmp); } if k+1<n { let tmp=dist[i][j][k][l]+d[k][l]; dist[i][j][k+1][l].chmin(tmp); } } } } } let mut dp=vec![vec![(usize::MAX,Reverse(0));n];n]; dp[0][0]=(0,Reverse(0)); for i in 0..n { for j in 0..n { for k in i..n { for l in j..n { if (i,j)==(k,l) { continue; } if (k,l)!=(n-1,n-1) && p[i][j]>=p[k][l] { continue; } let (cnt,Reverse(m))=dp[i][j]; if cnt==usize::MAX { continue; } let pcnt=if m>=dist[i][j][k][l] { 0 } else { (dist[i][j][k][l]-m).div_ceil(&p[i][j]) }; let tmp=(cnt+k-i+l-j+pcnt,Reverse(m+pcnt*p[i][j]-dist[i][j][k][l])); dp[k][l].chmin(tmp); } } } } outputln!(dp[n-1][n-1].0); }
G問題
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num::Integer; #[allow(unstable_name_collisions)] fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,mut xy:[(isize,isize);n],q:usize,g0:isize,ra:isize,rb:isize); xy.sort(); let mut pq=RevBinaryHeap::<(isize,usize)>::new(); for i in 0..n-1 { if xy[i].0!=xy[i+1].0 { pq.push(((xy[i+1].1-xy[i].1).div_ceil(&(xy[i+1].0-xy[i].0)),i)); } } let mut ab=vec![(0,0);q]; let mut g=g0; for i in 0..q { ab[i]=(-ra+gen(&mut g)%(2*ra+1),-rb+(gen(&mut g)*((1<<31)-1)+gen(&mut g))%(2*rb+1)); } ab.sort(); let mut ans=0; for &(a,b) in &ab { while let Some(&(bound,i))=pq.peek() { if bound>a { break; } pq.pop(); if xy[i].0>=xy[i+1].0 || (xy[i+1].1-xy[i].1).div_ceil(&(xy[i+1].0-xy[i].0))!=bound { continue; } xy.swap(i, i+1); if i>0 && xy[i-1].0<xy[i].0 { pq.push(((xy[i].1-xy[i-1].1).div_ceil(&(xy[i].0-xy[i-1].0)),i-1)); } if i+2<n && xy[i+1].0<xy[i+2].0 { pq.push(((xy[i+2].1-xy[i+1].1).div_ceil(&(xy[i+2].0-xy[i+1].0)),i+1)); } } ans+=n-usize_binary_search(n, false, |mid| { xy[mid].1>=a*xy[mid].0+b }); } outputln!(ans); } fn gen(g: &mut isize) -> isize { *g*=48271; *g%=(1<<31)-1; *g }
