ABC382

気持ち的にはかなり負けなんですが、Dまでの早ときしたおかげで勝ちを拾えていたみたい。

A - Daily Cookie

@ が \(D\) 個以上含まれることが保証されているので、 . の個数+ \(D\) が秋箱の個数です。 提出

#[allow(unused_imports)]
use proconio::{input, marker::Chars};

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

    let count = s.iter().filter(|&c| *c == '.').count();
    println!("{}", count + d);
}

B - Daily Cookie 2

後ろから順に、 @ があったら . に変える操作をすれば良いです。Pythonの range で後ろからループする書き方をうろ覚えだったので微妙に手間取りました。 提出

n, d = map(int, input().split())
s = list(input())

cnt = 0
for i in range(n-1, -1, -1):
    if s[i] == '@':
        cnt += 1
        s[i] = '.'
        if cnt == d:
            break

print(''.join(s))

ところで、いま書いていて気づいたのですがこの二問はAdvent Calendarが題材なのかな？もう12月なんですねぇ はやい...

C - Kaiten Sushi

各寿司が何番目に流れてくるかは答えに直接影響しないので、寿司の美味しさで降順にソートします。人1から、並べ替えられた寿司列に対して順に食べられる寿司はすべて食べていき、何番目の寿司まで食べられたかを管理することで解くことができます。
\(N=1\) の場合を考えて、そこから拡張するのが解きやすいかもしれません。 提出

use std::cmp::Reverse;
use itertools::Itertools;
use proconio::input;

fn main() {
    input!{
        n: usize,
        m: usize,
        a: [u64; n],
        b: [u64; m],
    }

    let inf = 1usize << 60;
    let mut ans = vec![inf; m];

    let indicates = (0..m).sorted_by_key(|i| Reverse(b[*i])).collect_vec();

    let mut bi = 0;

    for (i, &ai) in a.iter().enumerate() {
        while bi < m && b[indicates[bi]] >= ai {
            ans[indicates[bi]] = i+1;
            bi += 1;
        }
    }

    println!("{}", ans.iter().map(|&x| if x == inf { -1 } else { x as i64 }).join("\n"));
}

D - Keep Distance

あまり深いことを考えずに再帰で全探索、と行きたいところですが \(N\leq12\) と制約が微妙に怪しいので踏みとどまって枝狩りすることを考えることにします。
ある \(i\) について、 \(A_i\) が取りうる最小値と最大値を考えます。最小値は条件で与えられている通り \(A_{i-1}+10\) です。最大値は、「これ以降をすべて10間隔で増やしたときに、 \(A_N = M\) となる値」なので、 \(M - 10(N - i)\) と計算できます。
これらを条件に使って再帰関数を書くことでACが得られます。 提出

use std::collections::BTreeSet;
use itertools::Itertools;
use proconio::input;

fn dfs(v: &mut Vec<u64>, n: usize, m: u64, ans: &mut BTreeSet<Vec<u64>>) {
    if v.len() == n {
        ans.insert(v.clone());
        return;
    }
    
    let min = if let Some(e) = v.last() {
        *e + 10
    } else {
        1
    };
    let max = m - (n-v.len()-1) as u64 * 10;

    for x in min..=max {
        v.push(x);
        dfs(v, n, m, ans);
        v.pop();
    }
}

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

    let mut ans = BTreeSet::new();
    dfs(&mut vec![], n, m, &mut ans);
    println!("{}", ans.len());
    println!("{}", ans.iter().map(|v| v.iter().join(" ")).join("\n"));
}

理由は自分でもよくわかっていないのですが、どうもこの手の再帰関数で全列挙するタイプの実装は得意らしく。こういうタイプの実装問題はたくさん出てほしいですね(ポジショントーク)

E - Expansion Packs (upsolve)

考察はできたのですが実装で破滅してしまい、解説ACをしました。
1パック開封したときに \(k\) 枚のレアが得られる確率を \(P(k)\) , \(x\) 枚以上のレアを手に入れるための期待値を \(E(x)\) とします。このとき \(E(x)\) は以下のように求められます。

\[\begin{align}E(x) &= 1 + \sum_{i=1}^N P(i)E(\text{max}(x-i, 0)) + P(0)E(x) \\E(x) &= \frac{1 + \sum_{i=1}^N P(i)E(\text{max}(x-i, 0))}{1 - P(0)}\end{align}\]

期待値 \(E(x)\) は上記の漸化式を再帰関数あるいは動的計画法を用いることによって求めることができます。動的計画法の場合は空間 \(O(X)\) , 遷移が \(O(N)\) なのでこのパートは \(O(NX)\) です。
残る問題は \(k=0, 1, \cdots, N\) に対して \(P(k)\) を求めることであり、これが解ければこの問題を解くことができます。
さて、 \(P(k)\) は1パックを開封したときに \(k\) 枚のレアが得られる確率でした。これは dp[i][j] := i番目のカードまでみたときにj枚のあたりがある確率 とする確率DPで求めることができます 。空間はカード数 \(N\) の二乗で、遷移はレアが出る・出ないの2通りなので、 \(P(k)\) は \(O(N^2)\) で求まります。
以上から、全体で \(O(NX+N^2)\) でこの問題が解けます。 提出

use itertools::Itertools;
use proconio::input;

fn main() {
    input!{
        n: usize,
        x: usize,
        p: [u64; n],
    }

    let p = p.iter()
        .map(|&pi| pi as f64 / 100. )
        .collect_vec();

    // Prob(i) := N個からi個のレアを得る確率
    // dp[i][j] := i個中j個のレアを得る確率として確率DP
    let mut dp = vec![vec![0.0; n+1]; n+1];
    dp[0][0] = 1.;
    for i in 0..n {
        for j in 0..=i {
            // レアを取得
            dp[i+1][j+1] += dp[i][j] * p[i];
            // レアを取得できず
            dp[i+1][j] += dp[i][j] * (1. - p[i]);
        }
    }

    let prob = &dp[n];

    // dp[i] := パックからi個以上のレア得たときの、開封したパックの個数の期待値
    let mut dp = vec![0.; x+1];
    for i in 1..=x {
        dp[i] += 1.;
        for j in 1..=n {
            // j枚レアが出た
            let nxt = if i >= j {
                i - j
            } else {
                0
            };
            dp[i] += prob[j] * dp[nxt]; 
        }
        dp[i] /= 1. - prob[0];
    }
    println!("{:10}", dp[x]); 
}

ABC350E - Toward 0と似た考えで漸化式を立てられたんですが、実装が弱くて解ききれなかったのはかなり悔やしいです。

漸化式が立てられるので、そこからDPに帰着するのが自然な発想の流れだと思いますがここで謎のメモ化再帰に走ったせいで実装をバグらせました。

---

序盤が比較的得意なセットだったのでperf 1300弱を得たものの、Eが解ききれないのは辛いです。まぁ実装が苦手がちで、そういう問題から逃げがちなのが浮き彫りになっていると言われたらそうなのですが... いやでも精進で実装問やりたくないな.......