確率・場合の数
問題 xor b[i] = nとなるような数列b[i]は何通りあるか求めよ。 (ただし、b[i]はそれぞれ0≦b[i]≦cards[i]を満たす整数) 制約条件 cardsの要素の数≦50 n≦10^9 b[i]≦10^9
問題 全ての要素がA以上B以下の整数であるような集合のうち、 要素を小さい順に並べた列と、要素を辞書順に並べた列が一致するものの個数を、 mod Pで求めよ。 制約条件 A, B, P ≦10^9 B - A ≦ 100000
問題 木が与えられる。 この木と同じ頂点数で、葉以外の頂点の子は必ず一つまたは二つで、 なるべく平衡しているような木で、余った葉はなるべく左側から埋められている木を考える。 この木に、与えられた木を対応させる方法は何通りあるか、求めよ。 制約条…
問題 長さnの順列(1〜nの数の並び替え)を、 4回適用した順列P^4が与えられる。 このとき、Pとしてありうる順列は何通りか、求めよ。 制約条件 n≦700くらい
問題 英大文字からなる長さの等しい文字列a, bが与えられる。 a, bから長さの等しい、空でない連続する部分文字列x, yを取る。 x, yはその全ての候補の中から一つが等しい確率で選ばれる。 f(x, y)を、xi = yi(xのi番目の文字とyのi番目の文字が等しい)な…
問題 二分木を根のノードから書いていく。 二分木がバランスしているとは、 根が2つの子を持ち、それぞれの子を根とする部分木の大きさが等しいことを言う。 ノードを書いた後で、どれかを根とする部分木がバランスしたとき、 スコアに1点を加算する。 (複…
問題 2個のダイスがあり、ダイスの面には数字が書かれている。 数字は以下の条件を満たす。 1以上X以下 書かれている数は全て互いに異なる ただし、一つ目のダイスには0が何回か書かれていることがある。 いま、このダイスを使って次のようなゲームをする 先…
問題 二つの異なる数字が書かれたドミノがいくつかある。 このドミノを全て使って、全体がちょうどいくつかの輪になるように並べる。 ドミノが輪になっているとは、 左右に隣合うドミノの、隣り合う側の数字がすべて等しく、 かつ、最初のドミノと最後のドミ…
問題 中心からn本の通路が伸びた建物がある。 それぞれの通路の長さはcorridors[i]である。 0番の通路の端からスタートして、 「中心へ行き、今来た通路でない通路を等確率で一つ選んでその通路の端まで行く」 ということを繰り返して、全ての通路を一度以上…
問題 同じ色のぷよがL匹くっつくと消える。 筒にぷよぷよを一匹ずつ、合計N匹いれる。 全てのぷよを入れ終えたときに、筒の中が空になっているような、 ぷよの入れ方の場合の数を求めよ。 制約条件 2≦L≦20 N≦1000
問題 power Aのcool numberを以下のような数と定義する。 数字を連続するA個に区切って、 それぞれの区間において、一つ一つの桁の数字が等差数列になっているようにすることができる。 power Aのmega cool numberとは 各桁の数字が非減少列になっていて、 p…
問題 文字列A, B, Cが与えられたとき、 文字列xに対する操作fを、f(x) = A + x + B + x + Cとする。 (+は文字列の結合を表す) fをn回適用する操作(f(f...(f(f(x)))...))をf^nと書く。 f^k(x)に、文字列Fが何回出現するかを求めよ。 制約条件 A, B, C, Fの…
問題 n以上m以下の整数を10進数で全て書いたとき、 書かれる0の数は合計いくつか、求めよ。 制約条件 0≦n, m<2^32
問題 長さ片面のlのベルトコンベアがある。 コンベア上にチョコレートがn個あり、それぞれの位置はa[i]である。 ベルトコンベアはv1で動いている。 片方の端から、ベルトコンベアの移動と同じ向きに、速度v2で走る。 走っている間にチョコレートの上にきたら…
問題 lucky numberとは、全ての桁が4または7のどちらかであるような数をいう。 n個の数が与えられる。 このn個の数の長さkの(必ずしも連続しない)部分列のうち、 同じlucky numberは高々一つしか含まれないようなものはいくつあるか、mod 19^9 + 7で求めよ…
問題 直線上にN個のブイがあり、ブイとブイの間に一匹ずつ魚がいる。 魚にはそれぞれ'O', 'X', '*'の文字が割り振られている。 この魚を次のように網で囲う。 網は自己交差のない閉曲線で表される。 網は直線と、ブイの点のみで交わる。 ブイで直線と網が交…
問題 n段の階段があり、ちょうどn枚の長方形の板でできている。 長方形の板には重なりやはみだしがない。 このようにして作れる階段を全部つくり、階段を(一つの階段は一色で)それぞれk色のどれかで塗る。 このようにして出来上がるものは何通りあるか、mo…
問題 木の棒がN本、環状に並んでいる。 i番目とi+1番目、0番目とN-1番目はそれぞれ隣り合っている。 0番の木の棒を(startR, startG, startB)の色に塗る。 i番目の棒を塗り終えた後、i+1番目の棒を、次のようにして塗る。 i番目の棒の色を(R', G', B')、新し…
問題 無向グラフが与えられる。 それぞれの辺は、独立に確率P(全て等しい)で消滅する。 全ての辺について、消滅の判定が終わった後で、グラフが連結である確率を求めよ。 制約条件 グラフの頂点数≦14 辺の本数≦100 0≦P≦100
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2357) 制約条件 n≦2000 c≦n i≠jならai≠aj
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2360) 制約条件 変数の個数≦1000個 節の個数≦1000個 一つの変数は式中に高々2回しか現れない。
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2356) 制約条件 S ≦40 Sは英小文字からなる 答えは2^63以下に収まる
問題 N曲の曲からP曲を重複を許して、以下の条件を満たすよう選ぶ。 選び方は何通りあるか、mod 10^9 + 7で求めよ。 条件: 全ての曲が少なくとも一度以上選ばれる。 同じ曲は間に少なくともM曲のほかの曲を挟む。 制約条件 N,M,P≦100
問題 nマスが円状につながったすごろくがある。 通常の6面ダイスを振って、出た目だけ進んで、止まったマスに書かれた数字の点数を得る。 ゲームは(ダイスを振る前に)好きなタイミングで止めることができる。 最善の戦略を取るとき、ゲームで得られる点数…
問題 文字列の集合がprefix-freeであるとは、 どの文字列も、他の文字列の接頭辞となっていないことをいう。 空の文字列もprefix-freeである。 文字列の集合が与えられる。 この集合の部分集合(空集合および、元の集合そのものも含む)のうち、prefix-free…
問題 n枚のカードがある。 これらのカードに対して、2枚のカードをランダムに選び、その位置を交換するという操作をswapCount回行う。 操作前にa番目にあったカードが操作後にb番目にある確率を求めよ。 制約条件 n≦1000 swapCount≦100000
問題 nドルを賭け、勝つとnドルがもらえ、負けるとそのnドルを失うギャンブルがある。 次のような方針で賭けをする。 最初は1ドルを賭ける 負けた場合、前のラウンドの倍のお金を賭ける 勝った場合、前のラウンドの掛け金にかかわらず1ドルをかける 最初init…
問題 n個のダイスがあり、それぞれの面の数はsides[i]個である。 それぞれのダイスは1〜sides[i]の面を持つ。 これらのダイスをそれぞれ一度ずつ振り、出た目を順序を無視して扱う。 例えば、{1, 1, 2}と{1, 2, 1}は同じ出目として扱う。 出目は何通りあるか…
問題 ある数字がmirror numberであるとは、 その数字を鏡に映しても意味のある数字になっていることをいう。 数字を鏡に映すと、1は1のまま2は5に、5は2に、8は8に、0は0になり、 数字の順序が逆になる。 反転前または反転後にleading zeroがあることは許さ…
問題 n人がテーブルに座って握手をする。 それぞれの人は他のただ一人と握手する。 全員が握手をしていて、かつ手が一本も交差していないとき、握手の仕方を良いと呼ぶ。 良い握手の仕方は何通りあるか、求めよ。 制約条件 n≦50