けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

箱とボール

AOJ ???? Many Parentheses (KUPC 2020 M)

形式的冪級数の pow で通せた! 問題へのリンク editorial 問題概要 個の箱それぞれに正しい括弧列を入れる。ただし、次の2つの条件をともに満たすように入れる必要がある。 個の箱に含まれる '(' の個数の合計が 長さが である括弧列はどの箱にも入れてはな…

yukicoder No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)

(x - a)(x - b) ... (x - z) みたいなやつの計算 問題へのリンク 問題概要 個の箱がある。箱 には色 のボールが入っている。以下の 個のクエリに答えよ。 各クエリは 以下の整数 が与えられる 各箱から 個ずつボールを取り出す方法であって、取り出されたボ…

AtCoder ABC 132 D - Blue and Red Balls (緑色, 400 点)

二項係数が吹き荒れる!!!!!!!!! そして、重複組み合わせに関する理解がすごく問われる問題!!!!!!! 問題へのリンク 問題概要 個のボールがあって、そのうちの 個が青で、残りの 個が赤である。同じ色のボールは互いに区別できない。 各 に対…

AtCoder AGC 002 B - Box and Ball (緑色, 400 点)

うまくシミュレーションする系 問題へのリンク 問題概要 N 個の箱があります。 箱は 1 から N まで番号が振られています。 最初、1 番目の箱には赤いボールが 1 個入っています。 また、2~N 番目の箱には白いボールが 1 個ずつ入っています。 高橋君は M 回…

yukicoder No.391 CODING WAR

写像12相の 玉は区別する 箱も区別する 各箱の玉は 1 個以上 という場合の問題!!! 問題へのリンク 問題概要 個の互いに区別できる玉を、 個の互いに区別できる箱に入れる。 ただし、どの箱についても玉が 1 個以上入るようにするな方法が何通りあるか、10…

AtCoder World Tour Finals 2019 A - Magic (1000 点)

世界大会で注意力を問う罠枠だったのかな 問題へのリンク 問題概要 個の箱があってそのうちの一つに財宝が入っている。箱を 1 個 1 個開けて行くことで財宝を見つけたい。ただし、財宝が入っている箱を開けようとすると最大 回、財宝が他の箱に瞬間移動して…

AtCoder ARC 067 E - Grouping (黄色, 600 点)

slack 勉強会で 600 点の DP として話題になってやってみたん。 DP 自体は素朴だけど、計算量解析含めると 700 点でもいい気はする。 Grouping 問題へのリンク 問題概要 (ARC 067 E) 人をグループ分けしたい。 人は互いに区別される。 どのグループの人数も …