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    

C - King's Summit

ちょっと難しい？8近傍に動けるので、集合地点を$P_x, P_y$とすると人$i$は集合するのに$\max (\mathrm{\mid }{P}_x-R_i\mathrm{\mid },\mathrm{\mid }{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>()    
    
    
    

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

D - Substr Swap

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

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

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

fn solve(ip: &mut Input) {
    let (n, m) = ip.pair::
    

    

E - Subarray Sum Divisibility(upsolve)

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

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

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

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

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

fn solve(ip: &mut Input) {
        
    
        

F - All Included(upsolve)

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