Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Code Festival 2018-D Three Letters】真ん中固定と左右ビットマップ

D - Three Letters

問題

文字列がN個与えられる。

文字列Sについて、SiSjSkを略称を呼ぶ。

出来るだけ多くの文字列に対する略称のうち、辞書順最小のものを求めよ

制約: 文字列の数は30000。文字列長の合計は90000

方針

3つということで真ん中固定っぽい空気はある。

各文字列について、各オフセットから見て左に何があるか右に何かのビットマップを持つ。

あとは左右を各52通り、オフセットを90000通り調べて523略称のカウントを調べる。ここで文字列長の合計を活かす。ここで注意することは同じ文字列から同じ略称を2回カウントしないこと。

実装

fn solve() {
    input!{
        N:usize,
        a:[chars; N],
    }
    let mut aa = vec![];
    for s in &a {
        let mut ss = vec![];
        for &c in s {
            ss.push(ctoi(c));
        }
        aa.push(ss);
    }
    let mut left = vec![];
    let mut right = vec![];
    for i in 0..N {
        let ss = &aa[i];
        let mut tmp = vec![0; ss.len()];
        let mut acc: u64 =0;
        for j in 0..ss.len() {
            tmp[j]=acc;
            acc |= (1<<ss[j]);
        }
        left.push(tmp);
    }
    for i in 0..N {
        let ss = &aa[i];
        let mut tmp = vec![0; ss.len()];
        let mut acc: u64 =0;
        for j in (0..ss.len()).rev() {
            tmp[j]=acc;
            acc |= (1<<ss[j]);
        }
        right.push(tmp);
    }
 
    let mut cnt = vec![vec![vec![0;52];52];52];
    let mut last = vec![vec![vec![-1;52];52];52];
    for i in 0..N {
        let mut ss = &aa[i];
        for l in 0..52 {
            for r in 0..52 {
                for k in 0..ss.len() {
                    let m = ss[k] as usize;
                    if (left[i][k] & (1<<l) > 0) && (right[i][k] & (1<<r) > 0) {
                        if last[l][m][r] != i as i64 {
                            cnt[l][m][r] += 1;
                            last[l][m][r] = i as i64;
                        }
                    }
                }
            }
        }
    }
 
    let mut maxv=0;
    let mut maxcomb=None;
    for l in 0..52 {
        for m in 0..52 { 
            for r in 0..52 {
                if cnt[l][m][r]>maxv {
                    maxv = cnt[l][m][r];
                    maxcomb = Some((l,m,r));
                }
            }
        }
    }
 
    let (l,m,r) = maxcomb.unwrap();
    println!("{}{}{}", itoc(l as u64), itoc(m as u64), itoc(r as u64));
}

考察

真ん中固定の考え方はよくある。

数え上げるためにleft,rightの何かを前処理(例: 累積和とか)もよくある。

和が何とかという制約がある場合は大抵の場合それは一番内のループになる。

3乗だとだめなので、うち1つを和に帰着させるという発想が重要。

A-zというのはビットマップ感がある。