ABC417

A - A Substring

こういうのはPythonが楽。末尾の指定を-でやるとうまく行かないらしいですが、僕はよく知らないので引っかからずに済みました。提出

n, a, b = map(int, input().split())
s = input()
print(s[a:n-b])

B - Search and Delete

雑にmultisetで追加しておいて、あとから削除していけばよいです。Rustにはmultisetはないですが、それらしく使えるmapのラッパーを用意しているので問題なし。提出

use std::iter::repeat;

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

fn solve(ip: &mut    
    

    
        

C - Distance Indicators

条件式を整理すると、$A_i + i = j - A_j$となるので、$A_i + i$の数を前計算しておけば、に対応するものの個数がで取れるようになります。前計算、答えの計算がそれぞれでできるので、全体で時間で解くことができます。

use std::collections::BTreeMap;

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

fn solve(ip: &mut Input) {
    let n 
    

D - Takahashi's Expectation (upsolve)

これ難しすぎませんか？水diffなの驚きです。

$\text{dp}_{i,j} :=i$番目の要素からテンション$j$で始めたときの、最終的なテンションの値、というdpを考えると、問題設定から後ろから順にテーブルが埋まっていきます。与えられた制約全てに対してこのテーブルを埋めるのは時間が足りませんが、$A_i, P_i$が500以下であることから、としてまでを考えてあげれば十分です。

よって、このdpを前計算しておき、初期時点でテンションが1000を超えている場合はそれを下回るまで減少させてからテーブルを参照することによってこの問題を解けます。ただこれも一筋縄とは行かず、累積和+二分探索を用いて「始めて1000を下回るインデックス」を調べる必要があります。結局、全体で$O(N (\max A_i + \max P_i) + \log N)$時間など？計算量解析はあまり自信がありませんが、とにかくACを得ることができます。

use library::{cumulative_sum::CumulativeSum, utils::input::Input};

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

    

    

        

E - A Path in A Dictionary

「ある頂点に到達したときに、その後ゴールの頂点に到達できるか？」を判定すればよいです。できるだけ辞書順が小さい方に移動していって、採用できるならば採用する貪欲でOKです。ただし、一度確認してゴールに行けないことがわかった頂点は2度目以降は確認しないなどの枝狩りが必要となることに注意。提出

use library::{data_structure::unionfind::UnionFind, utils::input::Input};

fn ch(n: usize, s: usize, t: usize,    
    

    
        g
    

    

F - Random Gathering (upsolve)

え、簡単すぎないですか？これ。区間変更区間和取得の遅延セグ木を持って、その区間の和/区間長で全体を変更していくだけです。提出

use ac_library::{LazySegtree, MapMonoid, Monoid};
use ac_library::ModInt998244353 as Mint;
use library::{utils::input::Input}




        





        res