ABC419

久しぶりに酷い負け方をした。A~Dの4完で、Eで思考ロックに陥ってしまって嘘だろうなと思いながらその解法を捨てられなかった。かなしい。

A - AtCoder Language

この手の場合分けは2個ぐらいで済むならif-elseを使ったほうが楽がちですが、これぐらいの量になるとmatch式を使うときれいに書けていいですね。Unknownの綴りが不安でめちゃくちゃ丁寧に確認しましたが、よく考えるとコピペで良かった。 提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let s = ip.next::<String>();
    let ans = match s.as_str() {
        "red" => "SSS",
        "blue" => "FFF",
        "green" => "MMM",
        _ => "Unknown",
    };
    println!("{}", ans);
}

B - Get Min

Bなのでだいたい何やっても良いシリーズです。multisetを使いましたが、解説はpriority queueなんですね～。確かに。提出

use library::{data_structure::multiset::MultiSet, utils::input::Input};

fn solve(ip: &mut Input) {
    let mut set = MultiSet::new();
    let q = ip.next::<usize>();
    
    for _ in 0..q {
        let t = ip.next::<usize>();
        if t == 1 {
            let x = ip.next::<u64>();
            set.add(x, 1);
        } else {
            if let Some((&k, &_)) = set.min_key() {
                set.remove(k, 1);
                println!("{}", k);
            }
        }
    }
}

C - King's Summit

ちょっと難しい？8近傍に動けるので、集合地点を$P_x, P_y$とすると人$i$は集合するのに$\max(|P_x - R_i|, |P_y- C_i|)$時間かかります。答えはこれの最大値、つまり$\max_{i=1}^N \max(|P_x - R_i|, |P_y- C_i|)$ですから、この値を最小にするような$P_x, P_y$の組がどのようになるか？を考えればよいです。

これはすでにx座標とy座標に分離できていて、それぞれについて考えればよいです。どこに集合地点を置くか？と考えると、どう考えても$R, C$のそれぞれ最大値と最小値の平均(つまり、数直線上で一番左と一番右の、ちょうど真ん中)に置くのが良いですね。

この問題の設定では平均が小数になるのでどちらを選ぶ～みたいなことを気にする必要もなく、決めた$P_x, P_y$を使って冒頭の式を愚直に計算すれば$O(N)$時間でこの問題が解けます。提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let n = ip.next::<usize>();
    let v = (0..n).map(|_|ip.pair::<u64,u64>()).collect::<Vec<_>>();
    
    let x = v.iter().map(|v| v.0).collect::<Vec<_>>();
    let y = v.iter().map(|v| v.1).collect::<Vec<_>>();
    
    let px = (*x.iter().max().unwrap() + *x.iter().min().unwrap()) / 2;
    let py = (*y.iter().max().unwrap() + *y.iter().min().unwrap()) / 2;
    
    let ans = v.iter()
        .map(|v| v.0.abs_diff(px).max(v.1.abs_diff(py)))
        .max()
        .unwrap();
    
    println!("{}", ans);
}

始め8近傍ではなく4近傍で動くものだと思っており、「難しくないですか？」と唸っていました。誤読には気をつけよう。

D - Substr Swap

これは簡単。文字のインデックスが変わることはなくて、位置$i$の文字が元通りか逆転したかがわかればよいです。また、操作された回数が偶数回なら元通り、奇数回なら逆転です。

よって、問題は区間への加算ですが、これはimos法で出来ます。ということで、解けました。提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let (n, m) = ip.pair::<usize,usize>();
    let s = ip.next::<String>().chars().collect::<Vec<_>>();
    let t = ip.next::<String>().chars().collect::<Vec<_>>();

    let mut imos = vec![0i64; n+1];
    
    for _ in 0..m {
        let (l, r) = ip.pair::<usize, usize>();
        imos[l-1] += 1;
        imos[r] -= 1;
    }

    let mut ans = vec![];
    let mut cur = 0;
    
    for (i, imos_i) in imos[..n].iter().enumerate() {
        cur += *imos_i;
        if cur % 2 == 0 {
            ans.push(s[i]);
        } else {
            ans.push(t[i]);
        }
    }
    println!("{}", ans.iter().collect::<String>());
}

E - Subarray Sum Divisibility(upsolve)

難しい。人類は通し過ぎだと思います。

取り敢えず、$A$の長さ$L$の連続部分列に興味があるので、これを定義することにします。$i=1, 2, \cdots, N-L+1$に対して、$V_i$=$A_i + A_{i+1} + \cdots + A_{i+L-1}$とします。

ここで、$V_i$と$V_{i+1}$の差分に注目します。まず、$V_{i+1} - V_i = A_{i+L} - A_i$です。また、$V_i, V_{i+1}$はそれぞれ$M$で割ったあまりが$0$ですから、その差分である$V_{i+1} - V_i$も$M$で割ったあまりが$0$になる必要があります。よって、$A_{i+L}$と$A_i$が$M$で割ったあまりが同じであればよいです。

以上から、$\text{dp}_{i, j} =$ インデックスを$L$で割ったあまりが$i$であるような$A_i$の値を$M$で割ったあまりが$j$にするのに必要な最小コスト、のようにするような動的計画法で、この問題を解くことが出来ます。提出

use library::utils::{chlibs::ChLibs, consts::INF, input::Input};

fn solve(ip: &mut Input) {
    let (n, m, l) = ip.triple::<usize, usize, usize>();
    let a = ip.vector::<u64>(n);
    
    let mut dp = vec![INF; m];
    dp[0] = 0;
    
    for i in 0..l {
        let mut ndp = vec![INF; m];
        
        let costs = (0..m).map(|k| {
            a.iter()
                .skip(i)
                .step_by(l)
                .map(|ai| if k as u64 >= *ai { k as u64 - *ai} else { k as u64 + (m as u64 - *ai) })
                .sum::<u64>()
            })
            .collect::<Vec<_>>();

        for j in 0..m {
            if dp[j] == INF { continue; }
            for k in 0..m {
                ndp[(j+k)%m].chmin(dp[j] + costs[k]);
            }
        }
        dp = ndp;
    }
    println!("{}", dp[0]);
}

F - All Included(upsolve)

まず最初に思いつく(思いつきたい)のが、$\text{dp}_{i, s, p} := i$文字目まで見て、集合$S$の文字列を作成済みで、今完成した文字列が$p$であるものの個数、とする動的計画法です。ただ、これだけでは不十分で、というのは「今完成した文字列」は$i^{26}$個あるためテーブルが足りません。しかし、実際に知りたいのは文字列$S_i$が完成したかどうかだけで、これは「$S_i$に含まれる文字列のprefix」だけを持っておけば十分です。

そして、遷移をするのにAho-Corasick法を用いることができるらしいです。Aho-Corasick法そのものは、文字列の集合$S$があって、$S$の要素が与えられた文字列$T$の部分文字列であるか¹を高速に判定できるアルゴリズムですが、この問題のsuffixに関する遷移がAho-Corasick法における遷移と一致する²ため遷移先を高速に求めるために利用できます。

少し理解が曖昧なままなのでこれ以上は書かないでおく。とにかく、解けはした。要復習だけど...。提出

use ac_library::ModInt998244353 as Mint;
use library::{algorithm::aho_corasick::AhoCorasick, utils::input::Input};

fn solve(ip: &mut Input) {
    let (n, l) = ip.pair::<usize, usize>();
    let s = (0..n).map(|_| ip.next::<String>()).collect::<Vec<_>>();
    
    let ahocora = AhoCorasick::new(&s);

    let m = ahocora.node_size();
    let mut dp = vec![vec![Mint::new(0); m]; 1<<n];
    
    dp[0][0] = Mint::new(1);
    
    for _i in 0..l {
        let mut ndp = vec![vec![Mint::new(0); m]; 1<<n];
        for st in 0..1<<n {
            for j in 0..m {
                let next_ids = ahocora.destination_node_ids_from_id(j);
                
                for id in next_ids  {
                    let outputs = ahocora.nodes[id].outputs.iter()
                        .map(|i| 1<<i)
                        .sum::<usize>();
                    
                    ndp[st | outputs][id] += dp[st][j];
                }
            }
        }
        dp = ndp;
    }
    println!("{}", dp[(1<<n)-1].iter().sum::<Mint>());
}