Loading...
12/1/2024
気持ち的にはかなり負けなんですが、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); }
後ろから順に、@
があったら.
に変える操作をすれば良いです。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月なんですねぇ はやい...
各寿司が何番目に流れてくるかは答えに直接影響しないので、寿司の美味しさで降順にソートします。人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(" ")); }
あまり深いことを考えずに再帰で全探索、と行きたいところですがと制約が微妙に怪しいので踏みとどまって枝狩りすることを考えることにします。 あるについて、が取りうる最小値と最大値を考えます。最小値は条件で与えられている通りです。最大値は、「これ以降をすべて10間隔で増やしたときに、となる値」なので、と計算できます。
これらを条件に使って再帰関数を書くことで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(" ")); }
理由は自分でもよくわかっていないのですが、どうもこの手の再帰関数で全列挙するタイプの実装は得意らしく。こういうタイプの実装問題はたくさん出てほしいですね(ポジショントーク)
考察はできたのですが実装で破滅してしまい、解説ACをしました。
1パック開封したときに枚のレアが得られる確率を, 枚以上のレアを手に入れるための期待値をとします。このときは以下のように求められます。
期待値は上記の漸化式を再帰関数あるいは動的計画法を用いることによって求めることができます。動的計画法の場合は空間, 遷移がなのでこのパートはです。
残る問題はに対してを求めることであり、これが解ければこの問題を解くことができます。
さて、は1パックを開封したときに枚のレアが得られる確率でした。これはdp[i][j] := i番目のカードまでみたときにj枚のあたりがある確率
とする確率DPで求めることができます1。空間はカード数の二乗で、遷移はレアが出る・出ないの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]]と似た考えで漸化式を立てられたんですが、実装が弱くて解ききれなかったのはかなり悔やしいです。
序盤が比較的得意なセットだったのでperf 1300弱を得たものの、Eが解ききれないのは辛いです。まぁ実装が苦手がちで、そういう問題から逃げがちなのが浮き彫りになっていると言われたらそうなのですが... いやでも精進で実装問やりたくないな.......
漸化式が立てられるので、そこからDPに帰着するのが自然な発想の流れだと思いますがここで謎のメモ化再帰に走ったせいで実装をバグらせました。 ↩