AtCoder Beginner Contest 305

A - Water Station

5で割った切り上げ・切り捨てを計算して、5をかけると前後の補給所の場所が分かるので、それのうち近い方を出力する。

fn main() {
    input! {
        n: usize,
    }

    let a1 = (n + 4) / 5 * 5;
    let a2 = n / 5 * 5;

    let f = |a:usize,b:usize| { a.max(b) - a.min(b) };

    if f(a1, n) < f(a2, n) {
        println!("{}", a1);
    } else {
        println!("{}", a2);
    }
}

提出

B - ABCDEFG

問題文

A,B,C,D,E,F,G の間の距離が分かっているので、与えられている2つのアルファベットの距離を求める問題。適当にそれぞれの位置を入れておいて引けば良い。

fn main() {
    input! {
        p : char,
        q : char,
    }

    let d = vec![0, 3, 4, 8, 9, 14, 23];
    let i = (p as u8 - b'A') as usize;
    let j = (q as u8 - b'A') as usize;

    println!("{}", d[i.max(j)] - d[i.min(j)]);
}

提出

問題文

長方形になるようにクッキーが置かれていて、1個なくなっているクッキーの場所を求める問題。 $2 \times 2$ 以上なので、最小・最大の座標を求めておけば長方形の4つ端が分かるので、その間でクッキーが置かれていないところが答え。

fn main() {
    input! {
        h : usize,
        w : usize,
        s : [Chars; h]
    }

    let mut minx = 1000;
    let mut miny = 1000;
    let mut maxx = 0;
    let mut maxy = 0;

    for i in 0..h { for j in 0..w {
        if s[i][j] == '#' {
            minx = minx.min(i);
            miny = miny.min(j);
            maxx = maxx.max(i);
            maxy = maxy.max(j);
        }
    }}

    let mut ans = (0,0);
    for i in minx..=maxx { for j in miny..=maxy {
        if s[i][j] == '.' {
            ans = (i,j);
        }
    }}

    println!("{} {}", ans.0+1, ans.1+1)
}

提出

D - Sleep Log

問題文

累積和で大まかに求めておく。累積和で求められなかったはみ出ている分を後出て足してあげる。

fn main() {
    input! {
        n : usize,
        a : [usize; n],
        q : usize,
        queries : [(usize, usize); q]
    }

    let mut b = vec![0; n - 1];
    for i in 0..n-1 {
        if i % 2 == 1 {
            b[i] = a[i+1] - a[i];
        }
    }

    let mut csum = vec![0; n];
    for i in 0..n-1 {
        csum[i+1] = csum[i] + b[i];
    }

    for (l, r) in queries {
        let lindex = a.lower_bound(&l);
        let rindex = a.upper_bound(&r);

        let mut ans = csum[rindex - 1] - csum[lindex];

        if lindex % 2 == 0 {
            ans += a[lindex] - l;
        }

        if rindex % 2 == 0 {
            ans += r - a[rindex - 1];
        }

        println!("{}", ans);
    }
}

提出

E - Art Gallery on Graph

問題文

なんか沼った。最初の提出に $=$ が抜けているだけだった。

グラフ上に警備員がいて、それぞれ体力が決まっていて、体力分離れたところまで警備できる。警備されている頂点を昇順に出力して下さいという問題。

スタート地点をいくつか持って、最大値から更新していくダイクストラをすると良い。

fn main() {
    input! {
        n : usize,
        m : usize,
        k : usize,
        edges : [(Usize1, Usize1); m],
        ph : [(Usize1, usize); k]
    }

    let mut g = vec![vec![]; n];
    for (a, b) in edges { g[a].push(b); g[b].push(a); }

    let mut que = BinaryHeap::new();
    let mut dist = vec![None; n];
    for (p, h) in ph {
        que.push((h, p));
        dist[p] = Some(h);
    }

    while let Some((h, p)) = que.pop() {
        if dist[p].unwrap() != h { continue; }
        if h == 0 { continue; }
        for &q in &g[p] {
            if dist[q].is_none() || dist[q].unwrap_or(0) < h - 1 {
                dist[q] = Some(h - 1);
                que.push((h - 1, q));
            }
        }
    }

    let ans = (0..n).filter(|&i| dist[i].is_some()).collect_vec();
    println!("{}\n{}", ans.len(), ans.iter().map(|a| a + 1).join(" "));
}

提出

F - Dungeon Explore

問題文

入力がめんどくさいインタラクティブ。 Rust のインタラクティブが下手くそ過ぎて TLE めっちゃ出しちゃった。最初から自作の適宜入力取るやつで書いておけば良かった。

移動回数 $2 \times N$ 以下で頂点 $1$ から頂点 $N$ に移動してくださいという問題。連結かつ単純なので、DFSみたいに探索していったら $2 \times N$ 回以内に $N$ まで移動できる。

fn main() {
    let (n, m) : (usize, usize) = input_t();
    let mut g = vec![vec![]; n];
    let mut used = vec![false; n];

    let mut stack= vec![];
    let mut pref = vec![0; n];

    let e = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec();
    g[0] = e;
    for &u in &g[0] {
        stack.push((false, u));
        stack.push((true, u));
        pref[u] = 0;
    }

    while let Some((f, v)) = stack.pop() {
        if f {
            if used[v] { continue; }
            used[v] = true;
            println!("{} ", v + 1);
            if v + 1 == n { break; }
            stdout().flush().unwrap();
            let e = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec();            g[v] = e;
            for &u in &g[v] {
                if used[u] { continue; }
                stack.push((false, u));
                stack.push((true, u));
                pref[u] = v;
            }
        } else {
            println!("{} ", pref[v] + 1);
            stdout().flush().unwrap();
            let _ = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec();
        }
    }
}

提出

G - Banned Substrings

問題文

圧倒的に時間が足りなかった。

$N$ がある程度小さい場合は、末尾6桁を持って DP したら答えを求めることができる。しかし、大きいので DP 遷移を行列にして行列累乗をしたら良い。 6桁未満は愚直に求めると楽かも。

うーん…解きたかった。

fn main() {
    input! {
        n : usize,
        m : usize,
        s : [String; m]
    }


    let mut dp = FxHashMap::default();
    dp.insert("".to_owned(), Mint::new(1));


    for _ in 0..n.min(6) {
        let mut next = FxHashMap::default();
        for (k, &v) in dp.iter() {
            for i in 0..2 {
                let k = k.chars().rev().take(5).collect::<String>();
                let k = k.chars().rev().collect::<String>();

                let ns = k + if i==0 { "a" } else { "b" };
                if s.iter().any(|s| {
                    let ns = ns.chars().rev().take(s.len()).collect::<String>();
                    let ns = ns.chars().rev().collect::<String>();
                    &ns == s
                }) { continue; }
                *next.entry(ns).or_insert(Mint::new(0)) += v;
            }
        }
        dp = next;
    }

    if n <= 6 {
        println!("{}", dp.iter().fold(Mint::new(0), |acc, (_, x)| acc + x));
        return;
    }

    let mut v = vec![Mint::new(0); 1<<6];
    let mut mat = matrix::Matrix::new(1<<6, 1<<6, Mint::new(0));
    for (k, &val) in dp.iter() {
        let k = k.chars().fold(0, |acc, c| acc * 2 + if c=='a' { 0 } else { 1 });
        v[k] += val;
        for i in 0..2 {
            let l = (k * 2 + i) & 0b111111;
            mat[k][l] += 1;
        }
    }

    let t = mat.pow(n - 6, Mint::new(1));
    let ans = t * &v;
    println!("{}", ans.iter().sum::<Mint>());
}

提出

Ex - Shojin

問題文

見てない

まとめ

途中の問題で沼り過ぎて、勝負のGにあんまり時間かけられなかった…。競プロやらなさすぎて、鈍ってるなぁと思った。

パフォーマンス 1469。レート 1702 → 1680