ABC343を解き直しました。
コンテスト時はA～Fの6完でした。ひさしぶりに温まったので良かったですが、こういうセットは全完できるようになりたいですね…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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!(a:usize,b:usize); outputif(a+b>0, 0, 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,a:[[usize;n];n]); for i in 0..n { for j in 0..n { if a[i][j]==1 { print!("{} ", j+1); } } println!(); } }
C問題
#[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); for x in (1..=n.cbrt()).rev() { let k=x*x*x; let k=format!("{}",k); let krev=k.chars().rev().collect::<String>(); if k==krev { outputln!(k); return; } } }
D問題
#[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,t:usize,ab:[(Usize1,usize);t]); let mut p=vec![0;n]; let mut ms=MultiSet::new(); ms.insert(0, n); for &(a,b) in &ab { ms.remove_one(p[a]); p[a]+=b; ms.insert_one(p[a]); outputln!(ms.len()); } }
E問題
#[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!(v1:usize,v2:usize,v3:usize); let (a1,b1,c1)=(0,0,0); for a2 in -7..=7 { for b2 in -7..=7 { for c2 in -7..=7 { for a3 in -7..=7 { for b3 in -7..=7 { for c3 in -7..=7 { let v_3=max(min!(a1,a2,a3)+7-max!(a1,a2,a3), 0) as usize*max(min!(b1,b2,b3)+7-max!(b1,b2,b3), 0) as usize*max(min!(c1,c2,c3)+7-max!(c1,c2,c3), 0) as usize; let v_2=max(min(a1,a2)+7-max(a1,a2), 0) as usize*max(min(b1,b2)+7-max(b1,b2), 0) as usize*max(min(c1,c2)+7-max(c1,c2), 0) as usize +max(min(a2,a3)+7-max(a2,a3), 0) as usize*max(min(b2,b3)+7-max(b2,b3), 0) as usize*max(min(c2,c3)+7-max(c2,c3), 0) as usize +max(min(a3,a1)+7-max(a3,a1), 0) as usize*max(min(b3,b1)+7-max(b3,b1), 0) as usize*max(min(c3,c1)+7-max(c3,c1), 0) as usize -3*v_3; let v_1=3*7*7*7-2*v_2-3*v_3; if (v1,v2,v3)==(v_1,v_2,v_3) { outputln!("Yes"); outputln!(a1,b1,c1,a2,b2,c2,a3,b3,c3); return; } } } } } } } outputln!("No"); }
F問題
use ac_library::{Monoid, Segtree}; #[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,q:usize,a:[usize;n]); let mut st=Segtree::<M>::new(n); for i in 0..n { st.set(i, ((a[i],1),(0,0))); } for _ in 0..q { input!(q:usize); if q==1 { input!(p:Usize1,x:usize); st.set(p, ((x,1),(0,0))); } else { input!(l:Usize1,r:usize); outputln!(st.prod(l..r).1.1); } } } struct M; impl Monoid for M { type S = ((usize,usize),(usize,usize)); fn identity() -> Self::S { ((1,0),(0,0)) } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { let mut ms=MultiSet::new(); ms.insert(0, 0); ms.increase(a.0.0, a.0.1); ms.increase(a.1.0, a.1.1); ms.increase(b.0.0, b.0.1); ms.increase(b.1.0, b.1.1); let mut iter=ms.iter().rev(); let c1=iter.next().unwrap(); let c2=iter.next().unwrap(); ((*c1.0,*c1.1),(*c2.0,*c2.1)) } }
G問題
use ac_library::z_algorithm; #[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 s:[String;n]); s.sort_and_dedup(); let (n,s)=(s.len(),s); let mut ss=s.clone(); for i in 0..n { for j in 0..n { if i==j { continue; } ss[i].push('$'); ss[i].push_str(&s[j]); } } let zs=vec_range(0, n, |i| z_algorithm(&ss[i])); let mut is_necessary=vec![true;n]; let mut l=vec![vec![0;n];n]; for i in 0..n { for idx in s[i].len()+1..zs[i].len() { if zs[i][idx]==s[i].len() { is_necessary[i]=false; break; } } if !is_necessary[i] { continue; } let mut cur=s[i].len()+1; for j in 0..n { if i==j { continue; } for idx in cur..cur+s[j].len() { if idx+zs[i][idx]==cur+s[j].len() { l[j][i]=zs[i][idx]; break; } } cur+=s[j].len()+1; } } let mut dp=vec![vec![0;n];1<<n]; for s in 1usize..1<<n { for v in 0..n { if s&(1<<v)==0 { continue; } for u in 0..n { if s&(1<<u)>0 { continue; } let tmp=dp[s][v]+l[v][u]; dp[s+(1<<u)][u].chmax(tmp); } } } let mut ans=0; let mut bits=0; for v in 0..n { if is_necessary[v] { ans+=s[v].len(); bits+=1<<v; } } let mut intersections=0; for v in 0..n { intersections.chmax(dp[bits][v]); } ans-=intersections; outputln!(ans); }
