https://atcoder.jp/contests/abl/tasks/abl_f 問題概要 $ 2N $人の人がいて、それぞれ身長が$ h[i] $である。 この人たちで、ペアを$ N $組作っていく。(任意の人は1つのペアにしか属してはいけない) ここで、すべてのペアのうちの2人で、お互いの身長が異…

https://atcoder.jp/contests/arc059/tasks/arc059_c 問題概要 N人の子どもがいる。それぞれ、はしゃぎ度という整数値A[i]があるとする。 この時、それぞれの子どもが飴をB[i]個もらっているとき、全体の活発度は以下のように求められる。 $$ \Pi _ {i = 1} …

atcoder.jp 概要 N , Bで、次の条件を満たすようなものが何通りあるかを求めよ。ただし、非常に大きくなる場合があるので、で割ったあまりを求めること。 AとBの要素は、[1, M]の任意の整数 A[i] != B[i] (1 A[i] != A[j] (1 つまり、同じindexでのAとBの要…

atcoder.jp 概要 ある小文字アルファベットから構成される文字列Sが与えられる。これにK文字の任意の小文字を任意の位置にするとき、何通りの文字列が作れるのだろうか？制約：1 今回は自分用をメインに書いてるためかなり雑。わかりづらいかもしれない。

F - Knapsack for All SubsetsABC実質初全完を祝って解説記事。 概要 長さNの数列Aが与えられる。また、{1, 2, ..., N}が含まれる集合Xを考える。Xの空でない部分集合Tについて、次のf(T)を定める。 f(T) := Tの空でない部分集合を{t_1, t_2, ..., t_i}とす…

atcoder.jp 概要 おかずがN種類ある。それぞれのおかずには糖分A[i]、塩分B[i]というパラメータがある。 あなたはおかずを何種類か選んで晩御飯と一緒に食べたい。この時、次の条件を満たすようにする必要がある。 選ばれたおかずが2つ以上存在するのなら、…

atcoder.jp 概要 長さNの文字列Sが与えられる。Q回の質問ごとに与えられるkについて、次の条件を満たすような(a, b, c)のセットの数を答えよ。 S[a]=='D', S[b]=='M', S[c]=='C' a c - a 制約： 1

atcoder.jp 概要 サイズNの木が与えられる。頂点に1~Nの番号が振られている。k=[1, N]として次の条件下で問題を解け。 頂点kに最初に赤色を塗る。次に塗ることができるのは、すでに塗った頂点に隣接する頂点、というルールのもとで色を塗るとき、何通りの塗…

atcoder.jp 概要 長さNの数列A[]が与えられる。次のようにf(l, r)を定める。 l さて、1 制約： 1

www.acmicpc.net 概要 問題文はハングルオンリーなので、僕は機械翻訳で読んだ。グラムの重りそれぞれ1つずつある。あなたはこれらを一度に1つずつ、天秤に載せる。 天秤には左と右、両方の皿が存在する。載せる際、常に左の皿の重さが右の皿の重さ以上であ…

leetcode.com 概要 あなたはN種類の括弧を持っていて、互いに区別可能である。あなたはこれらを一列に並べる。すべての括弧に関しては、閉じる括弧'）'よりも前に開く括弧'（'が先に来る必要がある。 この並び方は何通り存在してるのか？で割ったあまりで答…

つぎのような問題を考える。 サイズNの無向木が与えられる。木の頂点に色を塗っていき、隣あった頂点には同じ色を塗ってはならない。 木をちょうどK色で塗るとき、何通りの塗り分け方があるか？で割ったあまりを答えよ。制約： 2

atcoder.jp 概要 n個の1~nまで番号がついてる部屋があって、それぞれ1人ずついる。ある部屋にいる一人が別の部屋へと行く行動をアクションと呼ぶ。 アクションがちょうどk回行われたときに、それぞれの部屋にいる人の数の組み合わせの数を10^9+7で割ったあま…

atcoder.jp 概要 f(x, y) := 1回の行動でx+1 or y+1しかできないときに、(0, 0)から(x, y)まで行く場合の数 と定める。r1, c1, r2, c2が与えられる。 r1 制約： 1

atcoder.jp 概要 サイズNの木が与えられる。それぞれの辺に黒、白の二色のいずれかで塗る。 次のM個の条件をすべて満たす塗り方の場合の数を求めよ。 ・頂点u~頂点vを結ぶ経路の上に、必ず1つ以上の白く塗られた辺が存在する。制約: 1 min(20, (N-1)*N/2) AC…

atcoder.jp 概要 長さNの相異なるバイナリ列、S, Tを考える。C[]という長さNの配列が与えられる。Sのi(1-idx)桁目を変更するとき、C[i]*(変更直前のS xor Tの立ってるbit数)だけのコストがかかる。次のようにf(S, T)を定める。 SをTと一致させるときにかかる…

atcoder.jp 概要 N個のスライムがあり、それぞれの位置はx[i]である。次の操作をN-1回行う。 残ってるスライムのうち、一番右を除いたのを等確率で1つ選び、それを一つ右に相当するスライムのところまで移動する。そして、その2つのスライムを合体させて1つ…

atcoder.jp 概要 数直線上にN匹のカエルがいて、それぞれx_i(>0)にいる。次の操作を、カエルが残ってる限り好きな回数行える。 数直線上にいる任意のカエルがx_iにいるとき、それを選んで、(x_i)-1 or (x_i)-2に動かす。ただし、動かす先に別のカエルがいる…

前編の読了お疲れさまでした。形式的べき級数でいくつかの数え上げを解決して、残るは数え上げの難関の3つの数(僕呼び)の、スターリング数、ベル数、分割数のみです。この三つの数はいずれも一般的な場合では漸化式を使わない式で表せません。今回の記事では…

先日、競プロやってたらhotmanから「形式的べき級数と数え上げの相性が抜群すぎてつながってて気持ちいい、世の中の眠る真理が目覚めた気がする」といわれて、気になったのでまとめた。 この記事は、数学的厳密性に欠けています。多くの変形が厳密な確認をな…

atcoder.jp 概要 N人の人が並んでいて、それぞれが赤、緑、青の帽子をかぶってる。i番目の人が自分より前で、自分と同じ色の人がそれぞれA_i人いるという。この状況で全体的にありうる並びの場合の数はいくつか？

atcoder.jp 概要 H * W (H, W ハンコも白紙も1*1のサイズに分割されていて、ハンコはそれぞれのマスごとに黒or白がある。 白紙は一度ハンコが押されて、その時点のマスが黒となったのならば、そのマスはずっと黒となる。 左上から右下まで、押せる場所を全部…

atcoder.jp 概要 Nの長さを持つ数列がある。(N

atcoder.jp 概要 最大10万長の数列が与えられる。この数列は和が10^5以下を満たす。 この数列の部分列のうち、XORしたらKになるのはなん通り存在するのか？

atcoder.jp 概要 数直線上にN個(N にあり、昇順で与えられる。 で、を満たすの組み合わせの数を求めよ。

atcoder.jp 概要 100文字までの文字列SをK(1

問題文atcoder.jp 問題概要 長さN、要素が最大10^18の数列がある。あなたはK回、このうちの要素のうちの1つを選んで、それを2で割って商を切り捨てる。 K回操作を終えた時、数列のバリエーションを10^9+7で割ったあまりで求めよ。操作の手順が違っても最終的…