https://atcoder.jp/contests/abc189/tasks/abc189_f 概要 マス目が0からNまであるすごろくが存在していて、あなたは1からMまですべての数が等確率で出るルーレットを持っている。あなたは最初にマス0にいて、マス目Nを目指して、以下のように進む。 マス目$…

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} …

この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな なんで$ 10 ^ 9 + 7 $じゃダメなのか 原始根って何？ とかについてもこれを…

atcoder.jp 概要 以下の問題がTケース与えられるので、それについてT回回答すること。長さNの配列{A_i}が与えられる。そして、もう1つ長さNの文字列Sが与えられ、それは0と1のみに構成される。0さんと1さんの2人はこの数列を使って、次のようなルールでゲー…

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つ以上存在するのなら、…

codeforces.com 概要 n_a, n_b, n_cと長さがn_aのa, n_bのb, n_cのcが与えられる。 aの中の1つの要素をx, bの中の1つの要素をy, cの中の1つの要素をzとする。を最小化せよ。制約： 1 ACするまで 1. 何か裏がありそうな式ではあるが、なんやかんやうまく全探…

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

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

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

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

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

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

atcoder.jp 概要 太郎君は、H時M分S秒に寝ました。起きた時には、C1回秒針と分針が重なり、C2回分針と時針が重なった。この時、寝てる時間としてあり得るのは最低何分、最長何分でしょう？ありえない入力ならば-1と出力すること。 ただし、寝始めや寝起きの…

atcoder.jp 概要 二回のコンテストが行われ、それぞれの参加者は∞人いた。高橋くんは一回目でa位、二回目でb位を取った。 この時、スコアをある参加者の二回のコンテストの順位の積と定義する。 高橋君よりスコアが上の参加者は最大何人いるのだろうか？ AC…

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