確率・場合の数

TopCoder SRM 605 Div1 Medium AlienAndSetDiv1

問題 自然数N, Kが与えられる。 {1, 2, ..., 2*N}の集合を互いに素なN個ずつの集合A, Bにわける。 A, Bの要素を小さい順に並べたとき、どのiについても|A[i] - B[i]| ≧ KとなるようなA, Bの選び方は何通りあるか、mod 10^9 + 7で求めよ。 制約条件 N≦50 K≦10

TopCoder SRM 603 Div1 Hard SumOfArrays

問題 長さn項の二つの数列a[i], b[i]が与えられる。 bの順序を好きに入れ替えて数列b'[i]を作る。 c[i] = a[i] + b'[i]という数列に、なるべく同じ数が出るようにbを並べ替える。 このとき、同じ数の出現回数の最大値と、その数を求めよ。 出現回数の最大値…

TopCoder SRM 603 Div1 Medium PairsOfStrings

問題 n文字でアルファベットの最初のk種類からなる文字列A, Bのうち、 次の条件を満たす(A, B)のペアの総数をmod 10^9 + 7で求めよ。 ある文字列Cが存在し、A + C = C + Bとなる。 (ただし + は文字列の結合を表す) AまたはBが一文字でも違うとき、二つの…

TopCoder SRM 601 Div1 Easy WinterAndPresents

問題 n個のかばんがあって、i番目のかばんにはりんごがapple[i]個とみかんがorange[i]個入っている。 ここから次のようにしてりんごとみかんを取り出す。取り出し方は何通りあるか。 自然数Xを選ぶ。 それぞれのかばんから、りんごとみかんの合計がX個になる…

Typical DP Contest D サイコロ

問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_dice

Typical DP Contest C トーナメント

問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament

TopCoder SRM 425 Div1 Hard RoadsOfKingdom

問題 n頂点からなる無向完全グラフで表される都市と道がある。 ここに雨がふって、それぞれの道がroads[i][j] / 8の確率で残り、 それ以外の確率で破壊される。 残った道が、木になっている確率を求めよ。 制約条件 n≦16

Codeforces 295C Greg and Friends

問題 n人が一隻のボートを使って河を渡りたい。 ボートにはwKgまでの人が乗れる。i番目の人の重さはa[i]で、全て50または100kgのどちらかである。 ボートは一人以上の人間が乗っていないと動かせない。全員が向こう岸に最短回数のボートの移動で移るような移…

Codeforces 261 B Maxim and Restaurant

問題 n人の人がいて、それぞれの人の大きさはa[i]である。 n人はn!通りの並び方を等しい確率で選んで並ぶ。 大きさの和がp以下であるような部分だけ、列の先頭から人がレストランに入れる。 入る人が、入れない人を飛ばすことはできない。 レストランに入れ…

Codeforces 336D Vasily the Bear and Beautiful Strings

問題 01からなる文字列で、0がn個1がm個ちょうど含まれているものを考える。 この文字列に対して、以下の操作を繰り返した後で、最後にgになるものの個数を求めよ。 操作: 文字列が1文字になっていたら終了 末尾が00のとき、1に置き換える 末尾が01のとき、…

Codeforces 314C Sereja and Subsequences

問題 長さnの数列a[i]が与えられる。 a[i]の空でない、(必ずしも連続しない)非減少部分列のうち、異なるものを全て取り出す。 それぞれに対して、それより"小さな"列の個数を求め、足し合わせる。 個数の総和はいくつか。 ただし、列xiよりyiが小さいであ…

Codeforces 213B Numbers

問題 n桁の正整数であって、 0, 1, 2... ,9の数字がそれぞれa[0], a[1], ..., a[9]回以上現れるようなものはいくつあるか、求めよ。 leading zeroは許されない。 制約条件 n≦100

Codeforces 235B Let's Play Osu!

問題 n種類のコインを投げて、出た面を順番に記録する。 i番目のコインが表の確率はp[i]である。このとき、連続する○の大きさの二乗の総和 (たとえば○○×○××だったら、2^2 + 1^2 = 5)の期待値を求めよ。 制約条件 n≦10^5 0≦p≦1

TopCoder SRM 581 Div1 Medium TreeUnion

問題 それぞれn頂点からなる木A, Bが与えられる。 この二つの木を次のようにしてつなぐ。 0, 1, ..., n - 1の順列をP[i]とする。 A[i]とB[P[i]]の間に辺を張る。 出来たグラフに大きさKの単純閉路(同じ点を二度通らない閉路)はいくつできるか。 全ての順列…

AOJ 2434 Audition

問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2434) 制約条件 n≦2000 m≦2000

TCO 2012 Round2C Medium ThreePoints

問題 座標平面上にx座標, y座標がそれぞれ全て互いに異なるN個の点がある。この点のうち、三つを取りそれらをr, g, bとする。 x[r] 制約条件 N≦300000 0≦座標の値<10^9

立命館合宿2013 1日目 F Balloon Contest

問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/contest_status.jsp?id=RitsCamp13Day1) 制約条件 n≦100 m≦10

TopCoder SRM 550 Div1 Hard ConversionMachine

問題 'a', 'b', 'c'からなる同じ長さの文字列word1, word2が与えられる。 word1の文字一つ選び、 aならbに bならcに cならaに変えるという操作を行う。 aをbに変える操作はcosts[0]が、 bをcに変える操作はcosts[1]が、 cをaに変える操作はcosts[2]がかかる…

TopCoder SRM 548 Div1 Hard KingdomAndCities

問題 n個の都市があり、そのうち0番からm - 1番のm個の都市は特別な都市である。 これらの都市をk本の道で以下の条件を満たすように接続したい。 条件を満たす接続方法をmod 10^9 + 7で求めよ。 一つの道路は異なる二つの都市を結ぶ ひとつの二つの都市のペ…

Codeforces 136D (220D) Little Elephant and Triangle

問題 (x, y)(0≦x≦w, 0≦y≦h)を満たす点3点からなる三角形で、 面積が正の整数であるものの個数を求めよ。ただし、点の順序は区別するものとする。 制約条件 w, h≦4000

TopCoder SRM 568 Div1 Medium EqualSums

問題 nxnの行列がniceであるということを以下のように定義する。 行列のそれぞれの行に対して、列を重複なく一つずつ選ぶ。 このとき、列をどのように選んだとしても、選んだ成分の和が一定であるときその行列はniceである。 行列が与えられる。 いくつかの…

TopCoder SRM 553 Div1 Medium TwoConvexShapes

問題 HxWのグリッドを'B'または'W'の色で塗る。 既に色が塗られているところはB, Wの文字が書かれていて、 そうでないマスには'?'が書かれている。 このグリッドの?のマスを全てBまたはWの色で塗り、以下の条件を満たすようにしたい。 全ての同色のマスは、…

TopCoder SRM 555 Div1 Medium XorBoard

問題 HxWのグリッドがあり、はじめ全てのグリッドは0である。 1行を自由に選んでその0, 1を反転する操作を合計Rcount回行い、 1列を自由に選んでその0, 1を反転する操作を合計Ccount回行う。 操作を行った後で、1の個数がS個になっているような、 操作の選び…

TopCoder SRM 558 Div1 Meidum Ear

問題 座標平面の第一象限に青い点がいくつかあり、 x軸の正の部分に赤い点がいくつかある。 これらの点から青い点P, Qおよび、赤い点A, B, C, Dを選び、 三角形PADが三角形QBCを厳密に含み 角PAD, 角PDA, 角QBC, 角QCBが全て90度より厳密に小さい とき、これ…

Codeforces 229C (142C) Triangles

問題 n頂点m辺からなる無向グラフが与えられる。 n頂点からなる完全グラフのうち、m辺をAliceが、 のこりの辺をBobが取る。 Aliceのグラフ中の三角形の数と、 Bobのグラフ中の三角形の数の和を求めよ。 制約条件 n, m≦10^6

Codeforces 162D (264D) Colorful Stones

問題 R, G, Bの色の石が2列に並んでいる。 ひとつ目の列は文字列sで表され、もうひとつの列はtで表される。 リスがsの最初の石に乗っていて、ネコがtの最初の石に乗っている。 この状態から、以下の動作を好きなだけ繰り返すことができる。 R, G, Bのどれか…

Codeforces 92C (123C) Brackets

問題 各成分が'('または')'であるnxmの行列が、monotonusであるとは、 (1, 1)から右または下に動いて(n, m)へ辿り着いたときにできる括弧文字列が、 どのような動き方をしたとしても対応していることを言う。 monotonusであるような行列を、c[i][j]にしたが…

TopCoder SRM 566 Div1 Medium PenguinEmperor

問題 n個の都市が円上0, 1, 2, ..., n - 1, 0という順に並んでいる。 最初0の都市にいて、 1日目には1個隣の都市のどちらかに、 2日目には2個隣の都市のどちらかに、 ... とm日間移動を繰り返す。 m日の移動が終わった後に都市0にいるような移動ルートは何通…

TopCoder SRM 565 Div1 Medium TheDivisionGame

問題 二人のプレイヤーがn個の山を使って次のようなゲームをする。 手番のプレイヤーは、山をひとつ選ぶ。 この山の石の数をXとする。Xより小さいXの約数Yを選び、この山の石の数をYに変える。 操作のできなくなったプレイヤーの負け 最初の山のうち[A, B]の…

TopCoder SRM 564 Div1 Medium AlternateColors2

問題 r個の赤の球、g個の緑の球、b個の青の球がある。 この球を以下の手順を繰り返して並べる。 赤があれば赤の球を並べる。 緑があれば緑の球を並べる。 青があれば青の球を並べる。 (最初に戻る) r + g + b = nであり、k番目に並べた球は赤い球だったこ…