AtCoder Regular Contest 175 (ARC175) 復習の提出

ARC175を解き直しました。
コンテスト時はBの1完でした。
6連敗です…そして、ARCは2連続で1完早解きしてから2完できず冷えるという、後味の悪い結果に…

復習したときのメモを動画にして提出したもののみ載せます。
www.youtube.com
www.nicovideo.jp

自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com

A問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::{Chars, Usize1};

#[allow(unstable_name_collisions)]
fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,p:[Usize1;n],s:Chars);
    let mut ans=Mint::new(0);
    let mut cnt=Mint::new(1);
    let mut exists=vec![true;n];
    for i in 0..n {
        if exists[(p[i]+1)%n] {
            if s[p[i]]=='R' {
                cnt*=0;
            }
        } else {
            if s[p[i]]=='?' {
                cnt*=2;
            }
        }
        exists[p[i]]=false;
    }
    ans+=cnt;
    let mut cnt=Mint::new(1);
    let mut exists=vec![true;n];
    for i in 0..n {
        if exists[p[i]] {
            if s[p[i]]=='L' {
                cnt*=0;
            }
        } else {
            if s[p[i]]=='?' {
                cnt*=2;
            }
        }
        exists[(p[i]+1)%n]=false;
    }
    ans+=cnt;
    outputln!(ans);
}

B問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use num::Integer;
use proconio::marker::Chars;

#[allow(unstable_name_collisions)]
fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(_:usize,a:usize,b:usize,mut s:Chars);
    let mut lcnt=0usize;
    let mut rcnt=0;
    for &c in &s {
        if c=='(' {
            lcnt+=1;
        } else {
            rcnt+=1;
        }
    }
    let mut ans=0;
    if lcnt<rcnt {
        for c in &mut s {
            if lcnt==rcnt {
                break;
            }
            if *c==')' {
                *c='(';
                rcnt-=1;
                lcnt+=1;
                ans+=b;
            }
        }
    } else if lcnt>rcnt {
        for c in s.iter_mut().rev() {
            if lcnt==rcnt {
                break;
            }
            if *c=='(' {
                *c=')';
                lcnt-=1;
                rcnt+=1;
                ans+=b;
            }
        }
    }
    let mut cnt=0;
    let mut cnt_min=0;
    for &c in &s {
        if c=='(' {
            cnt+=1;
        } else {
            cnt-=1;
        }
        cnt_min.chmin(cnt);
    }
    if cnt_min<0 {
        ans+=(-cnt_min).div_ceil(&2) as usize*min(a,2*b);
    }
    outputln!(ans);
}

C問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use num::clamp;

#[allow(unstable_name_collisions)]
fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,lr:[(usize,usize);n]);
    let mut a=vec![0;n];
    let cost=|a0:usize| {
        let mut ret=0;
        let mut a=a0;
        for i in 1..n {
            let next=clamp(a, lr[i].0, lr[i].1);
            ret+=a.abs_diff(next);
            a=next;
        }
        ret
    };
    a[0]=binary_search(lr[0].0, lr[0].1+1, |mid| {
        cost(mid)<cost(mid-1)
    });
    let mut is_decreased=vec![false;n];
    let mut idx=0;
    for i in 1..n {
        a[i]=clamp(a[i-1], lr[i].0, lr[i].1);
        if a[i-1]>a[i] {
            for j in idx..i {
                is_decreased[j]=true;
            }
        }
        if a[i-1]!=a[i] {
            idx=i;
        }
    }
    for i in (0..n-1).rev() {
        if !is_decreased[i] {
            continue;
        }
        a[i]=max(a[i+1], lr[i].0);
    }
    a.outputln();
}

D問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Usize1;

#[allow(unstable_name_collisions)]
fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,k:usize,uv:[(Usize1,Usize1);n-1]);
    let g=VecGraph::construct_graph(n, n-1, &uv);
    let dist=g.dist_of_shortest_paths(0, false);
    if k<n || k>n+dist.sum() {
        return output_no();
    }
    let sizes=g.sizes_of_subtrees(0);
    let mut sz_idx=vec_range(1..n, |i| (sizes[i],i));
    sz_idx.reverse_sort();
    let mut sum=k-n;
    let mut sgn_dist=vec_range(0..n, |i| (-(dist[i] as isize),i));
    for (s,i) in sz_idx {
        if sum>=s {
            sum-=s;
            sgn_dist[i].0*=-1;
        }
    }
    sgn_dist.sort();
    let mut ans=vec![0;n];
    for p in 0..n {
        ans[sgn_dist[p].1]=p+1;
    }
    output_yes();
    ans.outputln();
}

E問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

#[allow(unstable_name_collisions)]
fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,k:usize);
    let mut ans=vec![];
    if n%3==0 {
        ans.push([0,0,0]);
        if ans.len()%3!=k%3 {
            ans.push([n/3,n/3,n/3]);
        }
        if ans.len()%3!=k%3 {
            ans.push([n/3*2,n/3*2,n/3*2]);
        }
    } else {
        if k%3>0 {
            ans.push([0,0,0]);
        }
        if k%3==2 {
            ans.push([1,1,1]);
        }
    }
    for x in 0..n {
        if ans.len()==k {
            break;
        }
        for y in x..n {
            let z=(2*n-x-y)%n;
            if ans.len()==k {
                break;
            }
            if z<y {
                continue;
            }
            if x==y && y==z {
                continue;
            }
            if n%3>0 && k%3==2 && (x,y)==(1,1) {
                continue;
            }
            ans.push([x,y,z]);
            ans.push([y,z,x]);
            ans.push([z,x,y]);
            if ans.len()==k {
                break;
            }
            if x==y || y==z {
                continue;
            }
            ans.push([y,x,z]);
            ans.push([x,z,y]);
            ans.push([z,y,x]);
        }
    }
    ans.outputlns();
}

F問題

atcoder.jp
atcoder.jp

use std::cmp::Ordering;

use ac_library::FenwickTree;
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Chars;
use superslice::Ext;

#[allow(unstable_name_collisions)]
fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,s:[Chars;n]);
    let mut ssort=vec_range(0..n, |i| s[i].clone());
    ssort.sort_and_dedup();
    let mut inv_num=0;
    let mut ft=FenwickTree::new(n, 0);
    for i in 0..n {
        let s_num=ssort.lower_bound(&s[i]);
        inv_num+=ft.sum(s_num+1..);
        ft.add(s_num, 1);
    }
    let mut nmax=0;
    for i in 0..n {
        nmax.chmax(s[i].len());
    }
    let b=RollingHashBases::<2>::gen(nmax, 26);
    let rh=vec_range(0..n, |i| s[i].calculate_rolling_hashes('a', &b));
    let mut diffs=vec![vec![];n];
    let mut suffixes=vec![];
    for i in 0..n {
        diffs[i].resize(s[i].len(), 0);
        for j in 0..s[i].len() {
            suffixes.push((i,j));
        }
    }
    let mut left_set=MultiSet::new();
    let mut right_set=MultiSet::new();
    for i in 0..n {
        right_set.insert_one(rh[i].rolling_hash_of_subsequence(0, s[i].len(), &b));
    }
    for i in 0..n {
        right_set.remove_one(rh[i].rolling_hash_of_subsequence(0, s[i].len(), &b));
        for j in 1..s[i].len() {
            let hash=rh[i].rolling_hash_of_subsequence(0, j, &b);
            if let Some(&cnt)=left_set.get(&hash) {
                diffs[i][j]+=cnt as isize;
            }
            if let Some(&cnt)=right_set.get(&hash) {
                diffs[i][j]-=cnt as isize;
            }
        }
        left_set.insert_one(rh[i].rolling_hash_of_subsequence(0, s[i].len(), &b));
    }
    let lcp=|(l_i,l_j):(usize,usize),(r_i,r_j):(usize,usize)| {
        let l_len=s[l_i].len()-l_j;
        let r_len=s[r_i].len()-r_j;
        binary_search(0, l_len+r_len+1, |mid| {
            if mid<=min(l_len,r_len) {
                rh[l_i].rolling_hash_of_subsequence(l_j, l_j+mid, &b)==rh[r_i].rolling_hash_of_subsequence(r_j, r_j+mid, &b)
            } else if mid<=max(l_len,r_len) {
                if l_len>r_len {
                    rh[l_i].rolling_hash_of_subsequence(l_j, l_j+r_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j, s[r_i].len(), &b)
                    && rh[l_i].rolling_hash_of_subsequence(l_j+r_len, l_j+mid, &b)==rh[l_i].rolling_hash_of_subsequence(l_j, l_j+mid-r_len, &b)
                } else {
                    rh[l_i].rolling_hash_of_subsequence(l_j, s[l_i].len(), &b)==rh[r_i].rolling_hash_of_subsequence(r_j, r_j+l_len, &b)
                    && rh[r_i].rolling_hash_of_subsequence(r_j, r_j+mid-l_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j+l_len, r_j+mid, &b)
                }
            } else {
                if l_len>r_len {
                    rh[l_i].rolling_hash_of_subsequence(l_j, l_j+r_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j, s[r_i].len(), &b)
                    && rh[l_i].rolling_hash_of_subsequence(l_j+r_len, l_j+l_len, &b)==rh[l_i].rolling_hash_of_subsequence(l_j, l_j+l_len-r_len, &b)
                    && rh[r_i].rolling_hash_of_subsequence(r_j, r_j+mid-l_len, &b)==rh[l_i].rolling_hash_of_subsequence(l_j+l_len-r_len, l_j+mid-r_len, &b)
                } else {
                    rh[l_i].rolling_hash_of_subsequence(l_j, s[l_i].len(), &b)==rh[r_i].rolling_hash_of_subsequence(r_j, r_j+l_len, &b)
                    && rh[r_i].rolling_hash_of_subsequence(r_j, r_j+r_len-l_len, &b)==rh[r_i].rolling_hash_of_subsequence(r_j+l_len, r_j+r_len, &b)
                    && rh[r_i].rolling_hash_of_subsequence(r_j+r_len-l_len, r_j+mid-l_len, &b)==rh[l_i].rolling_hash_of_subsequence(l_j, l_j+mid-r_len, &b)
                }
            }
        })
    };
    suffixes.sort_by(|&(l_i,l_j),&(r_i,r_j)| {
        let l_len=s[l_i].len()-l_j;
        let r_len=s[r_i].len()-r_j;
        let lcp=lcp((l_i,l_j),(r_i,r_j));
        if lcp==l_len+r_len {
            Ordering::Equal
        } else {
            s[l_i][l_j+lcp%l_len].cmp(&s[r_i][r_j+lcp%r_len])
        }
    });
    let mut ans=inv_num;
    let mut inv_diff_sum=0;
    for i in 0..suffixes.len()-1 {
        let (l_i,l_j)=suffixes[i];
        let (r_i,r_j)=suffixes[i+1];
        let l_len=s[l_i].len()-l_j;
        let r_len=s[r_i].len()-r_j;
        inv_diff_sum+=diffs[l_i][l_j];
        let lcp=lcp((l_i,l_j),(r_i,r_j));
        if lcp!=l_len+r_len {
            ans.chmin((inv_num as isize+inv_diff_sum) as usize+lcp+1);
        }
    }
    let (l_i,l_j)=suffixes[suffixes.len()-1];
    let z=vec!['z'];
    inv_diff_sum+=diffs[l_i][l_j];
    let xy=s[l_i][l_j..].iter().chain(z.iter()).collect::<String>();
    let yx=z.iter().chain(s[l_i][l_j..].iter()).collect::<String>();
    let xy_rh=xy.calculate_rolling_hashes('a', &b);
    let yx_rh=yx.calculate_rolling_hashes('a', &b);
    let lcp=binary_search(0, xy.len()+1, |mid| {
        xy_rh.rolling_hash_of_subsequence(0, mid, &b)==yx_rh.rolling_hash_of_subsequence(0, mid, &b)
    });
    if lcp!=xy.len() {
        ans.chmin((inv_num as isize+inv_diff_sum) as usize+lcp+1);
    }
    outputln!(ans);
}