ARC173を解き直しました。
コンテスト時はAの1完でした。
落水しました。Bの予想が完全に正しかったようなのでダメ元で提出すべきでした。
やっぱり、ある程度時間を使ってしまったらペナ上等でいくべきですね…
復習したときのメモを動画にして提出したもののみ載せます。
自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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!(t:usize); for _ in 0..t { input!(k:usize); outputln!(usize_binary_search(E[18], false, |mid| { let mut m=mid; let mut cnt=0; let mut p=1; let mut s=vec![]; while m>0 { s.push((m%10,p)); m/=10; if p>1 { cnt+=p; } p*=9; } let mut prev_c=0; while let Some((c,p))=s.pop() { cnt+=if c==0 || prev_c>=c { c*p } else { (c-1)*p }; if prev_c==c { break; } if p==1 { cnt+=1; } prev_c=c; } cnt>=k })); } }
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 xy:[(isize,isize);n]); xy.sort(); let mut ans=n/3; for i in 0..n { for j in i+1..n { let mut cnt=0; for k in 0..n { if (xy[j].0-xy[i].0)*(xy[k].1-xy[j].1)!=(xy[j].1-xy[i].1)*(xy[k].0-xy[j].0) { cnt+=1; } } ans.chmin(cnt); } } outputln!(ans); }
C問題
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,p:[Usize1;n]); let mut ans=vec![usize::MAX;n]; let mut gcnt=0; let mut lcnt=0; for i in 1..n { if p[i]>p[0] { gcnt+=1; } else { lcnt+=1; } if i%2==0 && gcnt!=lcnt { ans[0]=i+1; break; } } let mut gcnt=0; let mut lcnt=0; for i in (0..n-1).rev() { if p[i]>p[n-1] { gcnt+=1; } else { lcnt+=1; } if (n-1-i)%2==0 && gcnt!=lcnt { ans[n-1]=n-i; break; } } for i in 1..n-1 { if (p[i-1]>p[i])==(p[i+1]>p[i]) { ans[i]=3; } } let mut s=BTreeSet::new(); for i in 0..n-1 { if p[i]>0 && p[i+1]>0 { s.insert(i); } } let mut pinv=vec![0;n]; for i in 0..n { pinv[p[i]]=i; } for cur_p in 0..n { let idx=pinv[cur_p]; if cur_p>0 { if idx>0 { s.remove(&(idx-1)); } if idx<n-1 { s.remove(&idx); } } if idx>0 && idx<n-1 && ans[idx]==usize::MAX { if let Some(&lmax)=s.range(0..idx).last() { ans[idx].chmin(if (idx-lmax+1)%2>0 { idx-lmax+1 } else { idx-lmax+2 }); } if let Some(&rmin)=s.range(idx..n).next() { let rmin=rmin+1; ans[idx].chmin(if (rmin-idx+1)%2>0 { rmin-idx+1 } else { rmin-idx+2 }); } } if cur_p<n-1 { if idx>0 && p[idx-1].cmp(&(cur_p+1))==p[idx].cmp(&(cur_p+1)) { s.insert(idx-1); } if idx<n-1 && p[idx].cmp(&(cur_p+1))==p[idx+1].cmp(&(cur_p+1)) { s.insert(idx); } } } ans.outputln_val_or(usize::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,p:[Usize1;n]); let mut ans=vec![usize::MAX;n]; let mut gcnt=0; let mut lcnt=0; for i in 1..n { if p[i]>p[0] { gcnt+=1; } else { lcnt+=1; } if i%2==0 && gcnt!=lcnt { ans[0]=i+1; break; } } let mut gcnt=0; let mut lcnt=0; for i in (0..n-1).rev() { if p[i]>p[n-1] { gcnt+=1; } else { lcnt+=1; } if (n-1-i)%2==0 && gcnt!=lcnt { ans[n-1]=n-i; break; } } for i in 1..n-1 { if (p[i-1]>p[i])==(p[i+1]>p[i]) { ans[i]=3; } else { let mut l=i-1; while l>0 { l-=1; if (p[l]>p[i])==(p[l+1]>p[i]) { ans[i].chmin(if (i-l+1)%2>0 { i-l+1 } else { i-l+2 }); break; } } let mut r=i+1; while r<n-1 { r+=1; if (p[r]>p[i])==(p[r-1]>p[i]) { ans[i].chmin(if (r-i+1)%2>0 { r-i+1 } else { r-i+2 }); break; } } } } ans.outputln_val_or(usize::MAX); }
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,m:usize,uvc:[(Usize1,Usize1,char);m]); let uvw=vec_range(0, m, |i| (uvc[i].0,uvc[i].1,if uvc[i].2=='(' { -1 } else { 1 })); let g=IsizeGraph::construct_weighted_directed_graph(n, m, &uvw); let exists_1=g.rough_bellman_ford(0).is_none(); let g=IsizeGraph::construct_inversed_weighted_directed_graph(n, m, &uvw); let exists_2=g.rough_bellman_ford(0).is_none(); output_yes_or_no(!(exists_1^exists_2)); }
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!(n:usize,a:[usize;n]); if n==2 || n%4!=2 { outputln!(vec_range(0, n-1, |i| a[0]^a[i+1]).subset_xor_max()); } else { let mut ans=vec_range(0, n-2, |i| a[1]^a[i+2]).subset_xor_max(); for j in 0..n-1 { ans.chmax(vec_range(0, n-2, |i| a[0]^if i<j { a[i+1] } else { a[i+2] }).subset_xor_max()); } outputln!(ans); } }
