問題 1〜6の数字をもつダイスがある。 これを振ると、出た目の数だけキャンディが貰える。 n個のキャンディを貰えるまでダイスを振り続けるとき、ダイスを振る回数の期待値を求めよ。 制約条件 n≦1000000

問題 1番からn番の生徒n人が輪になって次のようなゲームをする。 最初は1番の人のターン。ターンは時計まわりに進む ターンの人は、だれか一人を選んでボールを投げる。 それが命中する確率はprobability[i]% 命中したら、当たった人は輪から抜ける これを最…

嫌がらせかよこれ 問題 N個の箱と、それぞれの箱の鍵がある。 それぞれの箱の中に、鍵がランダムに一つ入っている。 鍵の入れ方は、全ての入れ方の中から等しい確率で一つが選ばれる。 爆弾をM個持っていて、爆弾を一つ使うと、箱を一つ壊して開けることがで…

問題 N個のビルが一列に並んでいて、それぞれの高さは1,2,3,...,Nである。 ビルiが左側から見えるとは、すべてのjiなるjについてh[j] 制約条件 N≦100

問題 rxcマスの格子がある。 (1,1)のマスを出発して(r,c)のマスへ最短距離で移動する。 一回の移動では(x,y)から(x+1,y)または(x,y+1)へ移動できる。 マスのなかには特別なものがあり、それぞれの座標は(fieldRow[i],fieldCow[i])により与えられる。 経路上…

問題 n枚のカードがある。 このカードを、次のような機械を使ってシャッフルする。 機械を一度通すと、i番目のカードがshuffle[i]番目に来るよう並び替えられる 1〜maxShuffleの整数を等確率で一つ選び、その回数だけデッキを機械に通す その後、cardsReceiv…

問題 英小文字からなる、長さがn文字以下で、使われているアルファベットがk種類以下であるような回文の数をmod 1234567891で求めよ。 制約条件 n≦10^9 k≦26

問題 文字列がlucky stringであるとは、 連続するどの二文字も同じでないような文字列のことを言う。 与えられた文字列の文字を並べ替えた文字列で、lucky stringであるものはいくつあるか求めよ。 制約条件 文字列の長さ≦10

問題 正三角形の辺をn等分し、等分した点同士を線分で結び六角形のグリッドを作る。 グリッド上に六角形は何通り書くことが出来るか、mod 10^9+7で求めよ。 制約条件 n≦500000

問題 A B C D E F G六角形が7個ならんだ図形に、以下の条件を満たすように数字を書き入れる。（上のA〜Gに数字を入れる） それぞれの数字は1〜2*nの整数であり、 全て互いに異なり、かつ任意の隣合う数字a,bについてa%n≠b%nが成り立つ。 ただし、回転して重…

問題 N行5列に1〜5Nまでの数字がランダムに書かれたくじがある。 当選番号が、5つ1〜5Nの中から相異なるように選ばれる。 くじに、当選番号が3つ以上書かれた行があればくじは当たりである。 くじが当たりである確率を求めよ。

問題 上側にn個の点1,2,...,nがあり、下側にn個の点1,2,...,nがある。 上側の点startDot[i]と下側の点startDot[i]が線で結ばれている。 まだ線で結ばれていない上側の点と下側の点を、ランダムに選び線で結ぶ。 全ての点を線で結んだあと、出来ている線の交…

問題 n枚のカードがある。 i枚目のカードの表にはtaro[i]の数字が書かれており、裏にはhanako[i]の数字が書かれている。 これらのカードを全て一列に並べたときに現れる数字の列は何通りあるか。 制約条件 n≦50 taro[i],hanako[i]は1〜nの整数が一度ずつ現れ…

問題 'W','B'または'?'からなるhxwのグリッドが与えられる。 '?'には'W'または'B'を任意に入れることが出来る。 以下の条件を満たすグリッドは何通りあるか、求めよ。 グリッドからどのように長方形(x1,y1),(x1,y2),(x2,y1),(x2,y2)を選んでもこの頂点が同じ…

問題 NxMの方眼紙がある（縦線がN+1本、横線がM+1本） ここに、全ての頂点が方眼紙の交点であるようなひし形は何通り書くことができるか求めよ。 制約条件 N,M≦100

問題 n個のボールの座標が与えられる。 ボールはそれぞれ、数直線上を左または右に、同じ速さで動いている。 ここにいくつかボールを足し、時間が経った後でのボールの座標が与えられる。 最初と最後のボールの対応の組み合わせとしてありうるものは何通りあ…

問題 整数を要素とする二つの集合S1,S2があったとき、 S2がS1の倍数であるとは、S1のどんな要素xに対しても、 ある整数kおよびS2の要素yが存在して、y=x*kが成り立つことを言う。 Sを、A<=x<=BまたはC<=x<=Dを満たす整数の集合とする。 Sの倍数であるような…

問題 白、黒、赤、黄色の旗を一直線にL個以上R個以下並べる。 次の条件を満たす並べ方はいくつあるか、mod 10^9+7で求めよ。 同じ色が連続しない 白と黄色が並ばない 黒と赤が並ばない 黒白赤がこの順または、この逆順に並ばない ただし、左右反転させて重な…

問題 n個の部屋がm本の通路により結ばれている。 二人が次のように移動する。 最初それぞれa,bの部屋にいる。 部屋ごとに定められている確率p[i]で、その場にとどまり、1-p[i]の確率で、通路を等確率で一つ選び、隣の部屋に移動する 二人の移動先が同じ部屋…

問題 凸多角形および、点Pが与えられる。 凸多角形の頂点からなる三角形で、点Pを含むものはいくつあるか求めよ。 制約条件 多角形の角≦100000

問題 1x1,1x2,...,1xkのブロックが無限にある。 これらのブロックを、1xwのブロックの上に積み上げる。ただし、 座標が整数でなくてはならない 上のブロックは、下のブロックからはみ出てはならない 高さは最大でh（土台は高さに含めない） の条件を満たす必…

問題 高さhの完全二分木がある。これに対してq個の次のようなクエリに答えよ。 add v e 頂点vにeの電荷を加える decay 木のdecay（後述）を求める。 木のdecayとは、次のようにして計算される値である。 木の葉をランダムに一つ選ぶ。木の根から、その葉まで…

問題 nxmマスのグリッドにおいて、「星」とは 1 111 1のような1の並びを言う。星は互いに一部が重なっていてもよい。nxmマス長方形の部分長方形で、星をk個以上含むものはいくつあるか、求めよ。 制約条件 n,m≦500

問題 文字列に対しての条件がc個与えられる。 アルファベットa[i]がちょうどw[i]の整数倍個だけ含まれている ただし、同じアルファベットに対してw[i]が複数個定義されている場合、w[i]のどれかの倍数になっていればよい。 長さnの文字列で条件を満たすもの…

問題 nxmマスのタイルをk色を使って塗る。 ただし以下の条件が満たされなければならない。 どのような縦の直線にそってマスを（空でない）二つに分割したときも、両方で使われている色の数が等しい。 条件を満たすタイルの塗り方は何通りか、mod 10^9+7で求…

問題 N行M列のグリッドがある。 このグリッドのi行j列にロボットがいて、 ロボットは1ターンに1度次の動きのうち、可能なものを等確率で一つ実行する。 その場から動かない 一列下の列に動く（最下段についたら止まる） 左に動く（グリッドからはみでる場合…

問題 10円のチケットをn+m枚販売する。 この国には10円と20円の二つの硬貨しかなく、 10円のみを持った客がn人、20円のみを持った客がm人来るものとする。 手元にはk枚の10円がある。 客がランダムな順番で来るとき、全ての客におつりをきちんと返せる確率は…

問題 重み付き無向木が与えられる。 このグラフの二点を結ぶパス全てについて、 パス上で重みが最も重い辺（複数ある場合全て）に木を一本植えるという操作をする。 全ての操作の後、最も木が植えられている辺に植えられている木の本数および、 その本数の木…

問題 nxmの方眼紙に、各頂点が格子点であるような長方形をk個書く。 i番目の長方形はi-1番目の長方形の真に内部になければならない。長方形の書き方は何通りあるか、mod 10^9+7で求めよ。 制約条件 n,m,k≦1000

問題 1〜nを並べ替えた数列のうち、 転置がちょうどm個あるもので、辞書順最小のものを求めよ。 制約条件 n≦50000 m≦n(n-1)/2