AtCoder Regular Contest 134 - zeronosu77108’s blog

バーチャル参加をしました。ペナ込みで 3完 60:23 でした。

A - Bridge and Sheets

橋に$N$ 枚のシートが敷かれていて、後何枚追加したら橋を全部覆えますか？という問題。

一番端から1枚目のシートの間を覆うには～、1枚目から2枚目の間は～って考えて行ったら良いです。最後に敷いたシートの右端を計算して持っておけば、$a_i$ から引けば間の距離が分かります。後は $w$ で切り上げ除算します。

fn main() {
    input! {
        n : usize,
        l : usize,
        w : usize,
        mut a : [usize; n]
    }

    a.push(l);
    let mut pre = 0;
    let mut ans = 0;

    for a in a {
        let c = (a.saturating_sub(pre)+w-1)/w;
        ans += c;
        pre = a + w;
    }

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

提出

B - Reserve or Reverse

問題文

問題文の理解をするのに時間かかりました… $S_0$ と $S_N$ をスワップ、 $S_1$ と $S_{n-1}$ をスワップみたいな感じで外側からスワップしていって辞書順最小にしてください。という問題。

辞書順最小にするには、最も小さい文字を手前に持ってくるようにしたら良いです。そのためには、各文字の index を先に求めておいて、できるだけ後ろの a を前に持ってきて後ろ側をどこまで使ったか覚えておくみたいなことをしたら良いです。

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

    let mut index = vec![vec![]; 26];
    for (i, &c) in s.iter().enumerate() {
        let c = (c as u8 - b'a') as usize;
        index[c].push(i);
    }


    let mut now = n;
    for (i, c) in s.clone().into_iter().enumerate() {
        let c = (c as u8 - b'a') as usize;
        'e: for j in 0..c {
            while let Some(x) = index[j].pop() {
                if i <= x && x <= now {
                    s.swap(i, x);
                    now = x;
                    break 'e
                }
            }
        }
    }

    println!("{}", s.iter().join(""));
}

提出

C - The Majority

問題文

難しい…

箱に $1$ が 0個では過半数が満たされないため、まず $1$ を箱に1個ずつ入れた状態から考えます。このとき、箱は過半数であるという条件は満たされているので、他の番号が書かれたボールを入れるときに一緒に $1$ のボールを入れたら条件は満たされたままになります。そのため、 $1$ が書かれたボールは、 $1$以外のボールの数 + 箱の数（$K$）以上である必要があります。

次に、$1$ 以外のボールを箱に振り分ける組合せを考えます。これは、それぞれの数字に対して箱に振り分ける組合せを考えたら良いので、良い感じにします（重複組合せ）。

後は、余った $1$ のボールを振り分ける方法をかけたら良いです。

今回は、入力される値が大きく、$K$が小さいので毎回組合せを計算します。

fn main() {
    input! {
        n : usize,
        k : usize,
        a : [usize; n]
    }
    const MOD : usize = 998_244_353;

    let sum = a.iter().skip(1).sum::<usize>();
    if a[0].saturating_sub(k) < sum { println!("0"); return; }

    let mut ans = 1;
    for &a in a.iter().skip(1) {
        ans *= nCr(a + k - 1, k - 1, MOD);
        ans %= MOD;
    }

    ans *= nCr(a[0]-sum-k+k-1, k-1, MOD); ans %= MOD;
    println!("{}", ans);
}