ardririyの足跡
ABC

ABC419

2025/08/20
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近傍に動けるので、集合地点をPx,PyP_x, P_yとすると人iiは集合するのにmax⁡(∣Px−Ri∣,∣Py−Ci∣)\max(|P_x - R_i|, |P_y- C_i|)時間かかります。答えはこれの最大値、つまりmax⁡i=1Nmax⁡(∣Px−Ri∣,∣Py−Ci∣)\max_{i=1}^N \max(|P_x - R_i|, |P_y- C_i|)ですから、この値を最小にするようなPx,PyP_x, P_yの組がどのようになるか？を考えればよいです。

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

この問題の設定では平均が小数になるのでどちらを選ぶ～みたいなことを気にする必要もなく、決めたPx,PyP_x, P_yを使って冒頭の式を愚直に計算すればO(N)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

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

よって、問題は区間への加算ですが、これは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)

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

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

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

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

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)

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

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

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

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>());
}

Footnotes

  1. どの文字列が、どのindexから一致したか ↩

  2. あんまり良くわかってないですが、Aho-Corasick法はオートマトンで、この問題はオートマトン上でDPをするオートマトンDPらしいです。よくわかっていません。 ↩

← 一覧へ