ABC345を解き直しました。
コンテスト時はA～Cの3完でした。DかEかFのどれか1問はせめて解けただろう…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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 srle=s.rle(); output_yes_or_no(srle.len()==3 && srle==vec![('<',1),('=',s.len()-2),('>',1)]); }
B問題
#[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!(x:isize); outputln!(x.div_ceil(&10)); }
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!(s:Chars); let l=s.len(); let mut cnt=vec![0;26]; for i in 0..l { cnt[s[i].from_lowercase()]+=1; } let mut ans=0usize; let mut same=0; for i in 0..26 { ans+=cnt[i]*(l-cnt[i]); if cnt[i]>1 { same=1; } } ans/=2; ans+=same; outputln!(ans); }
D問題
use itertools::Itertools; #[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use superslice::Ext; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,h:usize,w:usize,ab:[[usize;2];n]); for s in 0..1<<n { let mut p=(0..n).filter(|&k| s&(1<<k)>0).collect_vec(); do_while!(p.next_permutation(), { if dfs(h, w, &ab, p.len(), &p, 0, 0, 0) || dfs(h, w, &ab, p.len(), &p, 0, 1, 0) { outputln!("Yes"); return; } }) } outputln!("No"); } fn dfs(h:usize,w:usize,ab:&Vec<Vec<usize>>,l:usize,p:&Vec<usize>,k:usize,dir:usize,mut tile:u128) -> bool { let min=tile.trailing_ones() as usize; if k==l { return min==h*w; } let (m_i,m_j)=(min/w,min%w); for i in m_i..m_i+ab[p[k]][dir] { if i>=h { return false; } for j in m_j..m_j+ab[p[k]][1-dir] { if j>=w { return false; } if tile&(1<<(i*w+j))>0 { return false; } tile+=1<<(i*w+j); } } dfs(h, w, ab, l, p, k+1, 0, tile) || dfs(h, w, ab, l, p, k+1, 1, tile) }
E問題
use std::collections::VecDeque; #[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,cv:[(Usize1,usize);n]); let mut dp=VecDeque::from(vec![vec![];k+1]); dp[0]=vec![(0,n)]; for i in 0..n { let (c,v)=cv[i]; dp.push_front(vec![]); for j in 0..=k { if dp[j+1].len()>0 { if c!=dp[j+1][0].1 { let tmp=dp[j+1][0].0+v; let mut c_exists=false; for vc in &mut dp[j] { if vc.1==c { vc.0.chmax(tmp); c_exists=true; break; } } if !c_exists { dp[j].push((tmp,c)); } } else { if dp[j+1].len()>1 { let tmp=dp[j+1][1].0+v; let mut c_exists=false; for vc in &mut dp[j] { if vc.1==c { vc.0.chmax(tmp); c_exists=true; break; } } if !c_exists { dp[j].push((tmp,c)); } } } } dp[j].sort_by(|l,r| r.cmp(l)); if dp[j].len()>2 { dp[j].pop(); } } dp.pop_back(); } if dp[k].len()>0 { outputln!(dp[k][0].0); } else { outputln!(-1); } }
F問題
use std::collections::BTreeSet; #[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,k:usize,uv:[(Usize1,Usize1);m]); let mut ans=vec![]; if k==0 { outputln!("Yes"); outputln!(0); ans.outputln(); return; } let uvi=vec_range(0..m, |i| (uv[i].0,uv[i].1,i+1)); let g=VecGraph::construct_weighted_graph(n, m, &uvi); let mut yet=BTreeSet::new(); for v in 0..n { yet.insert(v); } let mut par=vec![0;n]; let mut num=vec![0;n]; let mut lamp=vec![false;n]; let mut cnt=0; while let Some(start)=yet.pop_first() { par[start]=start; num[start]=m; for gs in g.dfs_postorder(start) { match gs { GraphSearch::Vertex(true, v) => { yet.remove(&v); }, GraphSearch::VertexEdgeWeight(v, u, w) => { par[u]=v; num[u]=w; }, GraphSearch::Vertex(false, v) => { if par[v]==v { continue; } if !lamp[v] { lamp[v]=true; cnt+=1; cnt-=lamp[par[v]] as usize; lamp[par[v]]=!lamp[par[v]]; cnt+=lamp[par[v]] as usize; ans.push(num[v]); } if cnt==k { outputln!("Yes"); outputln!(ans.len()); ans.outputln(); return; } } } } } outputln!("No"); }
G問題
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*; use num_integer::Roots; fn main() { /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更） macro_rules! input { ($($tt:tt)*) => { proconio::input!($($tt)*); // proconio::input_interactive!($($tt)*); }; } input!(n:usize,k:usize); let mut a=vec![Mint::new(0);n+1]; let kinv=Mint::new(1)/k; if k>n.sqrt()/(n+1).ilog2() as usize { a[0]+=1; let invs=Mint::construct_modint_inverses(2*n+1); let facts=Mint::construct_modint_facts(2*n+1); let factinvs=Mint::construct_modint_fact_inverses(2*n+1, &invs); let sgn=|r:usize| if r%2>0 { -1 } else { 1 }; let binom=|n:usize,r:usize| if n>=r { facts[n]*factinvs[r]*factinvs[n-r] } else { Mint::new(0) }; let neg_binom=|n:usize,r:usize| { binom(n+r-1,n-1)*sgn(r) }; let mut kinvpow=kinv; for i in 1..n { let d=n-1-i; for j in 0..=d/k { a[i]+=binom(i,j)*sgn(j)*neg_binom(i+1,d-j*k)*sgn(d-j*k); } a[i]*=kinvpow; kinvpow*=kinv; } } else { let mut f=vec![kinv;k+1]; f[0]*=0; dc(n, k, &f, &mut a, 0, n+1, vec![Mint::new(1);n]); } let p=vec_range(1..=n, |i| a[i-1]-a[i]); p.outputlns(); } fn dc(n:usize,k:usize,f:&Vec<Mint>,a:&mut Vec<Mint>,l:usize,r:usize,mut g:Vec<Mint>) -> Vec<Mint> { if l+1==r { a[l]=*g.last().unwrap(); return f.clone(); } let len=min(n, (r-l-1)*k+1); g.drain(0..(g.len()-len)); let m=(l+r)/2; let mut fpow=dc(n, k, f, a, l, m, g.clone()); g.fps_mul_assign(&fpow, len-1); let fpow2=dc(n, k, f, a, m, r, g.clone()); fpow.fps_mul_assign(&fpow2, min(n-1, fpow.len()+fpow2.len()-2)); fpow }
#[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,k:usize); let kinv=Mint::new(1)/k; let mut f=vec![kinv;k+1]; f[0]*=0; let mut p=f.fps_pow_coefficients(n+1, n); for i in 1..=n { p[i]*=Mint::new(k)+1-Mint::new(n)/i; } p[1..].outputlns(); }
